A228396 The number of permutations of length n sortable by 2 reversals.
1, 1, 2, 6, 22, 63, 145, 288, 516, 857, 1343, 2010, 2898, 4051, 5517, 7348, 9600, 12333, 15611, 19502, 24078, 29415, 35593, 42696, 50812, 60033, 70455, 82178, 95306, 109947, 126213, 144220, 164088, 185941, 209907, 236118, 264710, 295823, 329601, 366192, 405748
Offset: 0
Examples
There are 2 permutations of length 4 which cannot be sorted by 2 reversals.
Links
- C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014.
- C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013.
- G. A. Watterson, W. J. Ewens, T. E. Hall, and A. Morgan, The chromosome inversion problem, Journal of Theoretical Biology, 99 (1982), 1-7.
- Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).
Programs
-
Mathematica
CoefficientList[Series[(1/x) (-1 - (x^7 - x^6 - 3 x^5 + 7 x^4 - 4 x^3 + 7 x^2 - 4 x + 1)/(x - 1)^5), {x, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *) LinearRecurrence[{5,-10,10,-5,1},{1,2,6,22,63,145,288},40] (* Harvey P. Dale, Mar 08 2019 *)
Formula
G.f.: -(x^7 - x^6 - 3*x^5 + 7*x^4 - 4*x^3 + 7*x^2 - 4*x + 1)/(x - 1)^5.
a(n) = 8 + n*(n^3 -2*n^2 +2*n -19)/6 for n>2, a(1)=1, a(2)=2. [Bruno Berselli, Aug 22 2013]
Extensions
a(0)=1 prepended by Alois P. Heinz, Mar 31 2025