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 (7,-21,35,-35,21,-7,1).
FORMULA
G.f.: -1 -(x^6 - 2*x^5 + 23*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.
EXAMPLE
The shortest permutation which cannot be sorted by 2 block transpositions is of length 4.
PROG
(PARI) Vec(-1-(x^6-2*x^5+23*x^4-22*x^3+16*x^2-6*x+1)/(x-1)^7 + O(x^50)) \\ Michel Marcus, Apr 03 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved