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

Author

Emeric Deutsch, Dec 25 2011

Keywords

• nonn

Comments

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

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

Examples

			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.
		

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, A202843, A202844

Programs

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);

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).