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,3

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.

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

Example

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

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

Prog

(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

Crossrefs

Sequence in context: A152329 A216716 A192088 * A228907 A209625 A054872

Adjacent sequences: A245230 A245231 A245232 * A245234 A245235 A245236

Keyword

nonn

Author

Murray Elder, Jul 14 2014

Status

approved