A202844 Number of secondary structures of size n having no stacks of length 3.

1, 1, 1, 2, 4, 8, 17, 36, 79, 179, 407, 935, 2173, 5089, 12005, 28500, 68022, 163154, 393060, 950652, 2307454, 5618906, 13723145, 33607242, 82507764, 203028034, 500659653, 1237053269, 3062204227, 7593229687, 18858944533, 46909741893, 116848688876, 291449697298

Offset: 0

Author

Emeric Deutsch, Dec 25 2011

Keywords

• nonn

Comments

For "secondary structure" and "stack" see the Hofacker et al. reference, p. 209.

Examples

			a(5)=8; 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; none of them has stacks of length 3.
		

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.

Crossrefs

Cf. A202838, A202839, A202840, A202841, A202842, A202843.

Programs

Maple

f := z^2*(1-z^4+z^6)/(1-z^2): eq := G = 1+z*G+f*G*(G-1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 37)): seq(coeff(Gser, z, n), n = 0 .. 33);

Formula

G.f.: G=G(z) satisfies G = 1+zG +fG(G-1)/(1+f), where f = z^2*(1-z^4+z^6)/(1-z^2).

a(n) = A202843(n,0).