A245233 - OEIS

%I #34 Dec 06 2021 09:27:20

%S 1,1,2,6,24,114,592,3216,17904,101198,578208,3332136,19343408,

%T 113017332,664168160,3923729280,23291913440,138872375958,831321465408,

%U 4994806458040,30111586314800,182094123983660,1104331746746208,6715050373394528,40931670125150624,250065092876686924,1530948705125205952,9391164635349135184

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

%H Alois P. Heinz, <a href="/A245233/b245233.txt">Table of n, a(n) for n = 0..1000</a>

%H M. Elder, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r68">Permutations generated by a stack of depth 2 and an infinite stack in series</a>, Electron. J. Combin, 13(1) (2006), R68.

%H M. Elder, G. Lee, A. Rechnitzer, <a href="http://arxiv.org/abs/1407.4248">Permutations generated by a depth 2 and infinite stack in series are algebraic</a>, arXiv:1407.4248 [math.CO], 2014. Electronic Journal of Combinatorics 22(1) (2015), #P2.16.

%H Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.

%F 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).

%F 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

%F 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

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

%p a:= proc(n) option remember; `if`(n<5, n!,

%p       (8*(n-2)*(10*n^6+21*n^5-455*n^4-1143*n^3+5227*n^2

%p        +10026*n-1926)*a(n-1) -(400*n^7-1120*n^6-20520*n^5

%p        +56848*n^4+317984*n^3-1096896*n^2+180600*n+939024)*a(n-2)

%p        +(320*n^7-3168*n^6-15520*n^5+198432*n^4+74096*n^3

%p        -3892992*n^2+8591088*n-3756096)*a(n-3) +(2560*n^7

%p        -13824*n^6-108624*n^5+666320*n^4+1015472*n^3-10736624*n^2

%p        +16022304*n-2062944)*a(n-4) -32*(4*n-15)*(4*n-17)*

%p        (2*n-9)*(5*n^4+18*n^3-189*n^2-522*n+2248)*a(n-5)) /

%p       ((n-1)*(n+3)*(n+1)*(5*n^4-2*n^3-213*n^2-110*n+2568)))

%p     end:

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Jul 14 2014

%t 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_ *)

%o (PARI)

%o N=66; x='x+O('x^N);

%o q=(1-2*x-sqrt(1-4*x))/(2*x);

%o gf=((1+q)*(1+5*q-q^2-q^3-(1-q)*sqrt((1-q^2)*(1-4*q-q^2))))/(8*q);

%o Vec(gf)

%o \\ _Joerg Arndt_, Jul 17 2014

%K nonn

%O 0,3

%A _Murray Elder_, Jul 14 2014