A228401 The number of permutations of length n sortable by 2 block interchanges.
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
Examples
The shortest permutations that cannot be sorted by 2 block interchanges are of length 7.
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).
Programs
-
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 *)
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]