|
%I #24 Apr 03 2015 17:57:13
%S 1,2,6,24,120,577,2208,6768,17469,39603,81272,154225,274802,464985,
%T 753556,1177362,1782687,2626731,3779196,5323979,7360972,10007969,
%U 13402680,17704852,23098497,29794227,38031696,48082149,60251078,74880985,92354252,113096118
%N The number of permutations of length n sortable by 2 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.: -1 + (x^11 - 5*x^10 - 2*x^9 + 44*x^8 - 23*x^7 - 87*x^6 - 22*x^5 - 24*x^4 + 22*x^3 - 16*x^2 + 6*x - 1)/(x - 1)^7.
%F a(n) = n! for 0 < n < 5; for n > 4, a(n) = -18 + n*(107*n^5 -1077*n^4 +2225*n^3 +12345*n^2 -61732*n +80532)/720. [_Bruno Berselli_, Aug 22 2013]
%e The shortest permutations which cannot be sorted by 2 cut-and-paste moves are of length 6.
%t CoefficientList[Series[(1/x) (-1 + (x^11 - 5 x^10 - 2 x^9 + 44 x^8 - 23 x^7 - 87 x^6 - 22 x^5 - 24 x^4 + 22 x^3 - 16 x^2 + 6 x - 1)/(x - 1)^7), {x,
%t 0, 40}], x] (* _Bruno Berselli_, Aug 22 2013 *)
%Y Cf. A060354, A228400.
%K nonn,easy
%O 1,2
%A _Vincent Vatter_, Aug 21 2013
|
