OFFSET
0,4
COMMENTS
For "secondary structure" and "stack" see the Hofacker et al. reference, p. 209.
LINKS
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
G.f.: g=g(z) satisfies g = 1 + zg + [z^2/(1 + z^2)]g(g-1).
g(z) = [1-z+2z^2-z^3-sqrt(1-2z+z^2-6z^3+2z^4-4z^5+z^6)]/(2z^2).
The multivariate g.f. H(z, t[1], t[2], ...) of secondary structures with respect to size (marked by z) and number of stacks of length j (marked by t[j]) satisfies H = 1 + zH + (f/(1 + f))H(H-1), where f = t[1]z^2 + t[2]z^4 + t[3]z^6 + ... .
D-finite with recurrence (n+2)*a(n) +(-2*n-1)*a(n-1) +(n-1)*a(n-2) +3*(-2*n+5)*a(n-3) +2 *(n-4)*a(n-4) +2*(-2*n+11)*a(n-5) +(n-7)*a(n-6)=0. - R. J. Mathar, Jun 14 2016
EXAMPLE
a(5)=7: representing unpaired vertices by v and arcs by AA, BB, etc., we have vvvvv, AvAvv, vvAvA, AvvAv, vAvvA, AvvvA, vAvAv. The 2ndary structure ABvBA has a stack of length 2.
MAPLE
eq := g = 1+z*g+z^2*g*(g-1)/(1+z^2): g := RootOf(eq, g): gser := series(g, z = 0, 40): seq(coeff(gser, z, n), n = 0 .. 35);
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 26 2011
STATUS
approved