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

Author

Vincent Vatter, Aug 21 2013

Keywords

• nonn
• easy

Comments

Essentially the same as A069778.

Examples

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

Links

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

Crossrefs

Cf. A000027, A002522.

Programs

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

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]