|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|