A228393 The number of permutations of length n that can be sorted by 3 block transpositions.

1, 2, 6, 24, 120, 675, 3527, 15484, 56917, 179719, 500864, 1260117, 2913132, 6274230, 12726573, 24521243, 45190897, 80108200, 137224138, 228026582, 368765112, 581994117, 898492563, 1359625566, 2020220021, 2952034021, 4247907652, 6026690971, 8439053564

Offset

1,2

Links

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

V. Bafna and P.A. Pevzner, Sorting by transpositions, SIAM J. Discrete Math. 11, 2 (1998), 224-240.

Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv:1410.2657 [math.CO], 2014.

C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv:1308.4946 [math.CO], 2013.

Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1).

Formula

G.f.: -x*(x^9 - 9*x^8 - 17*x^7 - 263*x^6 - 3*x^5 - 120*x^4 + 66*x^3 - 31*x^2 + 8*x - 1)/(x - 1)^10.

Example

The shortest permutations which cannot be sorted by 3 block transpositions are of length 6.

Mathematica

CoefficientList[Series[-(x^9 - 9 x^8 - 17 x^7 - 263 x^6 - 3 x^5 - 120 x^4 + 66 x^3 - 31 x^2 + 8 x - 1)/(x - 1)^10, {x, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)

Crossrefs

Cf. A000292, A228392.

Sequence in context: A152344 A152340 A152347 * A177526 A214611 A177528

Adjacent sequences: A228390 A228391 A228392 * A228394 A228395 A228396

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved