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
Keywords
References
- Toufik Mansour, Howard Skogman, and Rebecca Smith. "Passing through a stack k times." Discrete Mathematics, Algorithms and Applications 11.01 (2019): 1950003.
Links
- Toufik Mansour, Howard Skogman, and Rebecca Smith, Passing through a stack k times, arXiv:1704.04288 [math.CO], 2017-2018.
Programs
-
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 *)
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
Extensions
More terms from Vaclav Kotesovec, Jun 30 2019
Comments