OFFSET
1,2
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946 [math.CO], 2013-2015.
Index entries for linear recurrences with constant coefficients, signature (13,-78,286,-715,1287,-1716,1716,-1287,715,-286,78,-13,1).
FORMULA
G.f.: -x * (x^12 -12*x^11 +66*x^10 -217*x^9 +567*x^8 -270*x^7 +1608*x^6 -541*x^5 +419*x^4 -184*x^3 +58*x^2 -11*x +1) / (x^13 -13*x^12 +78*x^11 -286*x^10 +715*x^9 -1287*x^8 +1716*x^7 -1716*x^6 +1287*x^5 -715*x^4 +286*x^3 -78*x^2 +13*x -1).
EXAMPLE
The shortest permutations that cannot be sorted by 3 block interchanges are of length 8.
PROG
(PARI) Vec(x*(1-11*x+58*x^2-184*x^3+419*x^4-541*x^5+1608*x^6-270*x^7+567*x^8-217*x^9+66*x^10-12*x^11+x^12)/(1-x)^13 + O(x^30)) \\ Colin Barker, Dec 15 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Apr 03 2015
STATUS
approved