login
A202850
Number of secondary structures of size n with no stacks of length >=2.
1
1, 1, 1, 2, 4, 7, 14, 30, 63, 135, 297, 658, 1470, 3319, 7547, 17263, 39722, 91863, 213379, 497645, 1164859, 2735602, 6443750, 15220275, 36041685, 85546359, 203486990, 485000849, 1158133257, 2770323361, 6637570675, 15927592520, 38274809136, 92100301893
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
Cf. A004148.
Sequence in context: A199888 A157133 A367462 * A365857 A247295 A120262
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 26 2011
STATUS
approved