

A202844


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


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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, 207237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261272.


FORMULA

G.f.: G=G(z) satisfies G = 1+zG +fG(G1)/(1+f), where f = z^2*(1z^4+z^6)/(1z^2).
a(n) = A202843(n,0).


EXAMPLE

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.


MAPLE

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


CROSSREFS

Cf. A202838, A202839, A202840, A202841, A202842, A202843
Sequence in context: A002845 A072925 A002955 * A093951 A137255 A247298
Adjacent sequences: A202841 A202842 A202843 * A202845 A202846 A202847


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Dec 25 2011


STATUS

approved



