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,2

Links

Table of n, a(n) for n=1..32.

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.

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]

Example

The shortest permutations which cannot be sorted by 2 cut-and-paste moves are of length 6.

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 *)

Crossrefs

Cf. A060354, A228400.

Sequence in context: A189861 A189570 A293775 * A179340 A179342 A179346

Adjacent sequences: A228396 A228397 A228398 * A228400 A228401 A228402

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved