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

1, 2, 6, 24, 120, 720, 5040, 36757, 223898, 1055479, 3973264, 12530496, 34434065, 84883448, 191729212, 403095882, 798248632, 1502630530, 2708156958, 4700026333, 7891491375, 12868232903, 20444188490, 31730911273, 48222769794, 71900547943

Offset

1,2

Links

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

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.: -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

Example

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

Mathematica

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

Crossrefs

Cf. A060354, A228399.

Sequence in context: A152369 A152387 A152383 * A152380 A152374 A152375

Adjacent sequences: A228397 A228398 A228399 * A228401 A228402 A228403

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved