Voozh

VOOZH

URL: https://oeis.org/A228398

⇱ A228398 - OEIS

login

A228398

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

0

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

(list; graph; refs; listen; history; text; internal format)

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