OFFSET
1,2
LINKS
Matthew House, Table of n, a(n) for n = 1..10000
D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).
FORMULA
G.f.: -x*(x^8 -8*x^7 +28*x^6 -54*x^5 +78*x^4 -42*x^3 +24*x^2 -7*x +1)/(x-1)^9.
a(n) = 1 + n*(n-1)*(n+1)*(n+2)*(3*n^4-10*n^3-11*n^2+50*n+216)/5760. [Bruno Berselli, Aug 22 2013]
EXAMPLE
The shortest permutations that cannot be sorted by 2 block interchanges are of length 7.
MATHEMATICA
CoefficientList[Series[-(x^8 - 8 x^7 + 28 x^6 - 54 x^5 + 78 x^4 - 42 x^3 + 24 x^2 - 7 x + 1)/(x - 1)^9, {x, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)
LinearRecurrence[{9, -36, 84, -126, 126, -84, 36, -9, 1}, {1, 2, 6, 24, 120, 540, 1996, 6196, 16732}, 40] (* Harvey P. Dale, Dec 31 2019 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved