A202842 Number of secondary structures of size n having no stacks of length 2.

1, 1, 1, 2, 4, 7, 14, 31, 66, 142, 316, 708, 1593, 3625, 8314, 19165, 44433, 103557, 242376, 569514, 1343099, 3177766, 7540845, 17943506, 42804078, 102345017, 245233366, 588785677, 1416247791, 3412495415, 8235829927, 19906780104, 48185131721, 116790380824, 283432579807

Offset

0,4

Comments

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

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

Links

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

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 +fG(G-1)/(1+f), where f = z^2*(1-z^2+z^4)/(1-z^2).

Example

a(5)=7; 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; only the last one has a stack of length 2.

Maple

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

Crossrefs

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

Sequence in context: A247295 A120262 A202849 * A364589 A013326 A202973

Adjacent sequences: A202839 A202840 A202841 * A202843 A202844 A202845

Keyword

nonn

Author

Emeric Deutsch, Dec 25 2011

Status

approved