OFFSET
0,6
COMMENTS
Number of secondary structures of size n having no stacks of odd length (see Hofacker et al., p. 209). - Emeric Deutsch, Dec 26 2011
a(n) is the number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 4). The a(5) = 2 paths for n=5 are: UDUDUDUDUD, UUUUUDDDDD. - Alois P. Heinz, May 09 2012
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207-237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
FORMULA
a(n) = A202845(n,0). A(x) satisfies A=1+x*A+f*A*(A-1)/(1+f), where f=x^4/(1-x^4). - Emeric Deutsch, Dec 26 2011
G.f.: A(x) = ((1-x+x^4) - sqrt((1-x+x^4)^2 - 4*x^4))/(2*x^4). - Paul D. Hanna, Oct 29 2012
G.f. satisfies: A(x) = 1 + x*A(x)/(1 - x^4*A(x)). - Paul D. Hanna, Oct 29 2012
G.f.: 1 + x*exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} C(n,k)^2 * x^(3*k) ). - Paul D. Hanna, Oct 29 2012
a(n) = A216116(n-1) for n>0.
Recurrence: (n+4)*a(n) = (2*n+5)*a(n-1) - (n+1)*a(n-2) + 2*(n-2)*a(n-4) + (2*n-7)*a(n-5) - (n-8)*a(n-8). - Vaclav Kotesovec, Sep 16 2013
a(n) ~ sqrt(-4*c^2-3*c^3+4-4*c)*(1+2*c-c^3)^n*(-5*c^3-3*c^2+9*c+10) / (2*n^(3/2)*sqrt(Pi)), where c = 1/2*sqrt((4+(155/2-3*sqrt(849)/2)^(1/3) +(155/2+3*sqrt(849)/2)^(1/3))/3) - 1/2*sqrt(8/3-1/3*(155/2-3*sqrt(849)/2)^(1/3) - 1/3*(155/2+3*sqrt(849)/2)^(1/3) + 2*sqrt(3/(4+(155/2-3*sqrt(849)/2)^(1/3) + (155/2+3*sqrt(849)/2)^(1/3)))) = 0.5248885986564... is the root of the equation c^4-2*c^2-c+1=0. - Vaclav Kotesovec, Sep 16 2013
a(n) = Sum_{k=0..(n-1)/3} C(n-3*k,k)*C(n-3*k,k+1)/(n-3*k), n>0, a(0)=1. - Vladimir Kruchinin, Jan 21 2019
EXAMPLE
(5)=2; representing unpaired vertices by v and arcs by AA, BB, etc., the 8 (= A004148(5)) secondary structures of size 5 are vvvvv, AvAvv, vvAvA, AvvAv, vAvvA, AvvvA, vAvAv, ABvBA; they have 0,1,1,1,1,1,1,0 stacks of odd length, respectively. - Emeric Deutsch, Dec 26 2011
MAPLE
f := z^4/(1-z^4): eq := G = 1+z*G+f*G*(G-1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 42)): seq(coeff(Gser, z, n), n = 0 .. 39); # Emeric Deutsch, Dec 26 2011
a:= proc(n) option remember;
`if`(n=0, 1, a(n-1) +add(a(k)*a(n-4-k), k=1..n-4))
end:
seq(a(n), n=0..50); # Alois P. Heinz, May 09 2012
MATHEMATICA
Clear[ a ]; a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-4-k ], {k, 1, n-4} ];
CoefficientList[Series[((1-x+x^4) - Sqrt[(1-x+x^4)^2 - 4*x^4])/(2*x^4), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 16 2013 *)
PROG
(PARI) {a(n)=polcoeff(((1-x+x^4) - sqrt((1-x+x^4)^2 - 4*x^4 +x^5*O(x^n)))/(2*x^4), n)} \\ Paul D. Hanna, Oct 29 2012
(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=1 + x*A/(1-x^4*A+x*O(x^n))); polcoeff(A, n)} \\ Paul D. Hanna, Oct 29 2012
(Maxima)
a(n):=if n=0 then 1 else sum(binomial(n-3*q, ((q)))*binomial((n-3*q), (q+1))/(n-3*q), q, 0, (n-1)/3); /* Vladimir Kruchinin, Jan 21 2019 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
New name, using a comment of Alois P. Heinz, from Peter Luschny, Jan 21 2019
STATUS
approved