A256181 The number of permutations of length n sortable by 3 block interchanges.

1, 2, 6, 24, 120, 720, 5040, 32256, 169632, 737364, 2731444, 8875868, 25894376, 69053375, 170694383, 395443223, 866147111, 1806459866, 3608498678, 6937282452, 12887902732, 23216767894, 40675018726, 69480583966, 115975600846, 189528370396, 303753983092

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

Cf. A145126, A228401.

Sequence in context: A177278 A173847 A154655 * A293784 A179348 A179353

Adjacent sequences: A256178 A256179 A256180 * A256182 A256183 A256184

Keyword

nonn,easy

Author

Vincent Vatter, Apr 03 2015

Status

approved