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
KEYWORD
nonn
AUTHOR
Murray Elder, Jul 14 2014
STATUS
approved