OFFSET
1,2
LINKS
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
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved