A228399 The number of permutations of length n sortable by 2 cut-and-paste moves.
1, 2, 6, 24, 120, 577, 2208, 6768, 17469, 39603, 81272, 154225, 274802, 464985, 753556, 1177362, 1782687, 2626731, 3779196, 5323979, 7360972, 10007969, 13402680, 17704852, 23098497, 29794227, 38031696, 48082149, 60251078, 74880985, 92354252, 113096118
Offset: 1
Examples
The shortest permutations which cannot be sorted by 2 cut-and-paste moves are of length 6.
Links
- D. W. Cranston, I. H. Sudborough, and D. B. West, Short proofs for cut-and-paste sorting of permutations, Discrete Math. 307, 22 (2007), 2866-2870.
- C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014.
- C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013.
Programs
-
Mathematica
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, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)
Formula
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.
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]