A245233 Number of permutations generated by passing an ordered sequence of length n through a stack of depth 2 and an infinite stack in series.

1, 1, 2, 6, 24, 114, 592, 3216, 17904, 101198, 578208, 3332136, 19343408, 113017332, 664168160, 3923729280, 23291913440, 138872375958, 831321465408, 4994806458040, 30111586314800, 182094123983660, 1104331746746208, 6715050373394528, 40931670125150624, 250065092876686924, 1530948705125205952, 9391164635349135184

Offset: 0

Author

Murray Elder, Jul 14 2014

Keywords

• nonn

Examples

			For n=5 all but 6 permutations can be generated: 51234, 51243, 51423, 52134, 52143, 52413.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• M. Elder, Permutations generated by a stack of depth 2 and an infinite stack in series, Electron. J. Combin, 13(1) (2006), R68.
• M. Elder, G. Lee, A. Rechnitzer, Permutations generated by a depth 2 and infinite stack in series are algebraic, arXiv:1407.4248 [math.CO], 2014. Electronic Journal of Combinatorics 22(1) (2015), #P2.16.
• Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.

Programs

Maple

a:= proc(n) option remember; `if`(n<5, n!,
      (8*(n-2)*(10*n^6+21*n^5-455*n^4-1143*n^3+5227*n^2
       +10026*n-1926)*a(n-1) -(400*n^7-1120*n^6-20520*n^5
       +56848*n^4+317984*n^3-1096896*n^2+180600*n+939024)*a(n-2)
       +(320*n^7-3168*n^6-15520*n^5+198432*n^4+74096*n^3
       -3892992*n^2+8591088*n-3756096)*a(n-3) +(2560*n^7
       -13824*n^6-108624*n^5+666320*n^4+1015472*n^3-10736624*n^2
       [phone]*n-2062944)*a(n-4) -32*(4*n-15)*(4*n-17)*
       (2*n-9)*(5*n^4+18*n^3-189*n^2-522*n+2248)*a(n-5)) /
      ((n-1)*(n+3)*(n+1)*(5*n^4-2*n^3-213*n^2-110*n+2568)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 14 2014

Mathematica

q = (1-2*x-Sqrt[1-4*x])/(2*x); gf = ((1+q)*(1+5*q-q^2-q^3-(1-q)*Sqrt[(1-q^2)*(1-4*q-q^2)] ))/(8*q); CoefficientList[Series[gf, {x, 0, 40}], x] (* Jean-François Alcover, Apr 09 2015, after Joerg Arndt *)

PARI

N=66; x='x+O('x^N);
q=(1-2*x-sqrt(1-4*x))/(2*x);
gf=((1+q)*(1+5*q-q^2-q^3-(1-q)*sqrt((1-q^2)*(1-4*q-q^2))))/(8*q);
Vec(gf)
\\ Joerg Arndt, Jul 17 2014

Formula

G.f.: ((1+q)*(1+5*q-q^2-q^3-(1-q)*sqrt((1-q^2)*(1-4*q-q^2))))/(8*q) with q = (1-2*z-sqrt(1-4*z))/(2*z).

a(n) ~ (sqrt(5)+3) * sqrt(85-38*sqrt(5)) * 2^(n-3/2) * (1+sqrt(5))^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 15 2014

Equivalently, a(n) ~ 5^(1/4) * 2^(2*n - 1/2) * phi^(n - 5/2) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 06 2021