A228398 The number of permutations of length n sortable by 3 prefix reversals (in the pancake sorting sense).

1, 2, 6, 21, 52, 105, 186, 301, 456, 657, 910, 1221, 1596, 2041, 2562, 3165, 3856, 4641, 5526, 6517, 7620, 8841, 10186, 11661, 13272, 15025, 16926, 18981, 21196, 23577, 26130, 28861, 31776, 34881, 38182, 41685, 45396, 49321, 53466, 57837, 62440, 67281, 72366

Offset

1,2

Comments

Essentially the same as A069778.

Links

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

H. Dweighter, Elementary problems and solutions, problem E2569. Amer. Math. Monthly 82 (1975), 1010.

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.

Formula

G.f.: -1 + (x^6 - 3*x^5 + 6*x^4 + 4*x^2 - 3*x + 1)/(x - 1)^4.

a(n) = (n-1)*(n^2-3*n+3) for n>2, a(1)=1, a(2)=2. [Bruno Berselli, Aug 22 2013]

Example

There are only 3 permutations of length 4 which cannot be sorted by 3 pancake reversals.

Mathematica

CoefficientList[Series[(1/x) (-1 + (x^6 - 3 x^5 + 6 x^4 + 4 x^2 - 3 x + 1)/(x - 1)^4), {x, 0, 50}], x] (* Bruno Berselli, Aug 22 2013 *)

Crossrefs

Cf. A000027, A002522.

Sequence in context: A004192 A104143 A088812 * A228394 A245749 A342440

Adjacent sequences: A228395 A228396 A228397 * A228399 A228400 A228401

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved