A121703 Number of alternating separable permutations.

1, 2, 4, 8, 20, 48, 132, 344, 996, 2720, 8132, 22888, 69940, 201040, 624132, 1822136, 5725124, 16915008, 53648772, 160012232, 511360340, 1536928624, 4942300804, 14949122328, 48322714020, 146946942688, 477105960772, 1457491035944, 4750171491956, 14568377075344

Offset: 1

Author

Vincent Vatter, Aug 16 2006

Keywords

• nonn

Comments

The separable permutations are those avoiding 2413 and 3142 and are counted by the large Schroeder numbers (A006318). The alternating permutations are counted by the Euler numbers (A000111).

Examples

			a(4)=8 because of the 10 alternating permutations of length 4, 2413 and 3142 are not separable.
		

Links

• Robert Brignall, Sophie Huczynska, and Vincent Vatter, Simple permutations and algebraic generating functions, arXiv:math/0608391 [math.CO], 2006.

Crossrefs

Cf. A121704.

Programs

Mathematica

nmax = 40; aa = ConstantArray[0, nmax]; aa[[1]] = 1; aa[[2]] = 2; Do[f = Sum[aa[[k]]*x^k, {k, 1, j - 1}] + koef*x^j; sol = Solve[SeriesCoefficient[f^3 - (2*x^2 - 5*x + 4)*f^2 - (4*x^3 + x^2 - 8*x)*f - (2*x^4 + 5*x^3 + 4*x^2), {x, 0, j + 2}] == 0, koef][[1]]; aa[[j]] = koef /. sol[[1]], {j, 3, nmax}]; aa (* Vaclav Kotesovec, Jul 07 2024 *)

Formula

G.f. satisfies f^3-(2x^2-5x+4)f^2-(4x^3+x^2-8x)f-(2x^4+5x^3+4x^2)=0.

Extensions

a(13) and beyond corrected by Vaclav Kotesovec, Jul 07 2024