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,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, 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^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

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

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

Crossrefs

Cf. A202845, A202846, A023427, A202848

Sequence in context: A365857 A247295 A120262 * A202842 A364589 A013326

Adjacent sequences: A202846 A202847 A202848 * A202850 A202851 A202852

Keyword

nonn

Author

Emeric Deutsch, Dec 26 2011

Status

approved