A202850 Number of secondary structures of size n with no stacks of length >=2.

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

Table of n, a(n) for n=0..33.

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

Adjacent sequences: A202847 A202848 A202849 * A202851 A202852 A202853

Keyword

nonn

Author

Emeric Deutsch, Dec 26 2011

Status

approved