login
A228393
The number of permutations of length n that can be sorted by 3 block transpositions.
1
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
V. Bafna and P.A. Pevzner, Sorting by transpositions, SIAM J. Discrete Math. 11, 2 (1998), 224-240.
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
Sequence in context: A152344 A152340 A152347 * A177526 A214611 A177528
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved