login
A228401
The number of permutations of length n sortable by 2 block interchanges.
3
1, 2, 6, 24, 120, 540, 1996, 6196, 16732, 40459, 89519, 184185, 356721, 656475, 1156443, 1961563, 3219019, 5130856, 7969228, 12094622, 17977422, 26223198, 37602126, 53082966, 73872046, 101457721, 137660797, 184691431, 245213039, 322413765, 420086085, 542715141
OFFSET
1,2
LINKS
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
Sequence in context: A258216 A263748 A072856 * A189861 A189570 A293775
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved