A308726 The number of permutations of length n and tier at most 1, that is, the number of permutations of length n sortable by two passes through a stack where outputting the longest prefix matching the identity permutation is prioritized.

1, 1, 2, 6, 24, 112, 556, 2811, 14234, 71808, 360568, 1803100, 8988924, 44719588, 222221416, 1103827306, 5484124128, 27265300504, 135695994964, 676228846370, 3374996253420, 16871826671280, 84488005896720, 423828619074900, 2129868537725916, 10722045181336524

Offset

0,3

Comments

This counts the permutations of length n that avoid the permutations 24153, 24513, 24531, 34251, 35241, 42513, 42531, 45231, 261453, 231564, 523164.

References

Toufik Mansour, Howard Skogman, and Rebecca Smith. "Passing through a stack k times." Discrete Mathematics, Algorithms and Applications 11.01 (2019): 1950003.

Links

Table of n, a(n) for n=0..25.

Toufik Mansour, Howard Skogman, and Rebecca Smith, Passing through a stack k times, arXiv:1704.04288 [math.CO], 2017-2018.

Formula

G.f.: (2 + (2*x-1)/sqrt(1-4*x) - sqrt(2*sqrt(1-4*x) - 1)) / (2*x). - Vaclav Kotesovec, Jun 30 2019

a(n) ~ 2^(4*n + 3/2) / (sqrt(Pi) * n^(3/2) * 3^(n + 1/2)). - Vaclav Kotesovec, Jun 30 2019

Conjecture: D-finite with recurrence: 3*n*(n-1)*(n+1)*a(n) -n*(n-1)*(67*n-101)*a(n-1) +2*(n-1)*(286*n^2-1112*n+1089)*a(n-2) +4*(-580*n^3+4200*n^2-10106*n+8049)*a(n-3) +24*(184*n^3-1784*n^2+5770*n-6221)*a(n-4) -96*(4*n-15)*(2*n-9)*(4*n-17)*a(n-5)=0. - R. J. Mathar, Jan 27 2020

Mathematica

CoefficientList[Series[(2 + (2*x - 1)/Sqrt[1 - 4*x] - Sqrt[2*Sqrt[1 - 4*x] - 1])/(2*x), {x, 0, 25}], x] (* Vaclav Kotesovec, Jun 30 2019 *)

Crossrefs

Cf. A122890 (sum of last two rows), A158830 (sum of first two rows).

Sequence in context: A274378 A177521 A152322 * A168490 A118376 A212884

Adjacent sequences: A308723 A308724 A308725 * A308727 A308728 A308729

Keyword

nonn

Author

Rebecca Smith, Jun 20 2019

Extensions

More terms from Vaclav Kotesovec, Jun 30 2019

Status

approved