%I #23 Apr 03 2015 17:57:22

%S 1,2,6,24,120,720,5040,36757,223898,1055479,3973264,12530496,34434065,

%T 84883448,191729212,403095882,798248632,1502630530,2708156958,

%U 4700026333,7891491375,12868232903,20444188490,31730911273,48222769794,71900547943

%N The number of permutations of length n sortable by 3 cut-and-paste moves.

%H D. W. Cranston, I. H. Sudborough, and D. B. West, <a href="http://dx.doi.org/10.1016/j.disc.2007.01.011">Short proofs for cut-and-paste sorting of permutations</a>, Discrete Math. 307, 22 (2007), 2866-2870.

%H C. Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657, 2014.

%H C. Homberger, V. Vatter, <a href="http://arxiv.org/abs/1308.4946">On the effective and automatic enumeration of polynomial permutation classes</a>, arXiv preprint arXiv:1308.4946, 2013.

%F G.f.: -x*(2*x^19 + 28*x^17 - 90*x^16 + 31*x^15 - 329*x^14 + 2874*x^13 - 1487*x^12 - 13363*x^11 + 17425*x^10 + 8876*x^9 - 16945*x^8 - 8185*x^7 - 1326*x^6 - 48*x^5 - 120*x^4 + 66*x^3 - 31*x^2 + 8*x - 1)/(x - 1)^10

%e The shortest permutations that cannot be sorted by 3 cut-and-paste moves are of length 8.

%t CoefficientList[Series[-(2 x^19 + 28 x^17 - 90 x^16 + 31 x^15 - 329 x^14 + 2874 x^13 - 1487 x^12 - 13363 x^11 + 17425 x^10 + 8876 x^9 - 16945*x^8 - 8185 x^7 - 1326 x^6 - 48 x^5 - 120 x^4 + 66 x^3 - 31*x^2 + 8*x - 1)/(x - 1)^10, {x, 0, 40}], x] (* _Bruno Berselli_, Aug 23 2013 *)

%Y Cf. A060354, A228399.

%K nonn,easy

%O 1,2

%A _Vincent Vatter_, Aug 21 2013