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,2

Links

Table of n, a(n) for n=1..33.

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

Cf. A000124, A228396.

Sequence in context: A177518 A369832 A319027 * A164871 A226436 A224318

Adjacent sequences: A228394 A228395 A228396 * A228398 A228399 A228400

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved