A228396 The number of permutations of length n sortable by 2 reversals.

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

Offset

1,2

Links

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

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).

Formula

G.f.: -1 -(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]

Example

There are 2 permutations of length 4 which cannot be sorted by 2 reversals.

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 *)

Crossrefs

Cf. A000124, A228397.

Sequence in context: A027561 A321626 A126171 * A219766 A002839 A109194

Adjacent sequences: A228393 A228394 A228395 * A228397 A228398 A228399

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved