A228400 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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