A202849 Number of secondary structures of size n having no stacks of even length.

1, 1, 1, 2, 4, 7, 14, 31, 66, 141, 313, 702, 1577, 3581, 8207, 18903, 43770, 101903, 238282, 559322, 1317717, 3114676, 7383914, 17552857, 41831618, 99923471, 239200459, 573750288, 1378763083, 3319005743, 8002573350, 19324601494, 46731582653, 113160019865

Offset: 0

Author

Emeric Deutsch, Dec 26 2011

Keywords

• nonn

Comments

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

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 stacks of even length.
		

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. A202845, A202846, A023427, A202848

Programs

Maple

f := z^2/(1-z^4): 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).

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

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) +(-n+7)*a(n-6) +3*(2*n-17)*a(n-7) +(-n+10)*a(n-8) +(-2*n+23)*a(n-9) +(n-13)*a(n-10)=0. - R. J. Mathar, Jul 26 2022