A228397 The number of permutations of length n sortable by 3 reversals.
1, 2, 6, 24, 118, 534, 1851, 5158, 12264, 25943, 50214, 90656, 154758, 252304, 395793, 600894, 886936, 1277433, 1800644, 2490168, 3385574, 4533066, 5986183, 7806534, 10064568, 12840379, 16224546, 20319008, 25237974, 31108868, 38073309, 46288126, 55926408
Offset: 1
Examples
There are 2 permutations of length 5 which cannot be sorted by 3 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.
Programs
-
Mathematica
CoefficientList[Series[(1/x) (-1 - (2 x^10 + 5 x^9 + 12 x^8 - 75 x^7 + 58 x^6 + 20 x^5 + 24 x^4 - 22 x^3 + 16 x^2 - 6 x + 1)/(x - 1)^7), {x, 0, 50}], x] (* Bruno Berselli, Aug 22 2013 *)
Formula
G.f.: -1 -(2*x^10 + 5*x^9 + 12*x^8 - 75*x^7 + 58*x^6 + 20*x^5 + 24*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.
a(n) = n! for 0 < n < 4; for n > 3, a(n) = 318 + n*(7*n^5 -21*n^4 -125*n^3 -819*n^2 +12862*n -42720)/144. [Bruno Berselli, Aug 22 2013]