OFFSET
1,2
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.
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]
EXAMPLE
There are 2 permutations of length 5 which cannot be sorted by 3 reversals.
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 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved