A202840 Number of secondary structures of size n having no stacks of length 1.

1, 1, 1, 1, 1, 2, 4, 8, 14, 23, 38, 65, 117, 214, 391, 708, 1278, 2318, 4238, 7803, 14419, 26684, 49433, 91736, 170656, 318280, 594905, 1113868, 2088554, 3921505, 7373367, 13883045, 26174600, 49408932, 93372078, 176637791, 334491586, 634023965, 1202894908, 2284187117

Offset

0,6

Comments

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

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

Links

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

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

D-finite with recurrence +(n+4)*a(n) +(-2*n-5)*a(n-1) +(-n-1)*a(n-2) +2*(2*n-1)*a(n-3) +(-n+2)*a(n-4) +4*(-2*n+7)*a(n-5) +3*(n-5)*a(n-6) +3*(2*n-13)*a(n-7) +2*(-n+8)*a(n-8) +2*(-2*n+19)*a(n-9) +(n-11)*a(n-10)=0. - R. J. Mathar, Jul 26 2022

Example

a(5)=2; 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; they have 0,1,1,1,1,1,1,0 stacks of length 1, respectively.

Maple

f := 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, 42)): seq(coeff(Gser, z, n), n = 0 .. 39);

Crossrefs

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

Sequence in context: A055291 A091773 A107055 * A018153 A101687 A096461

Adjacent sequences: A202837 A202838 A202839 * A202841 A202842 A202843

Keyword

nonn

Author

Emeric Deutsch, Dec 25 2011

Status

approved