A202843 Triangle read by rows: T(n,k) is the number of secondary structures of size n having k stacks of length 3.

1, 1, 1, 2, 4, 8, 17, 36, 1, 79, 3, 179, 6, 407, 16, 935, 43, 2173, 110, 5089, 284, 12005, 727, 3, 28500, 1858, 14, 68022, 4767, 43, 163154, 12210, 138, 393060, 31255, 433, 950652, 80057, 1295, 2307454, 205088, 3804, 1, 5618906, 525534, 10985, 16, 13723145, 1347174, 31297, 85

Offset: 0

Author

Emeric Deutsch, Dec 25 2011

Keywords

• nonn
• tabf

Comments

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

Sum of entries in row n is A004148 (the secondary structure numbers).

Sum(k*T(n,k), k>=0) = A202839(n-4).

T(n,0) = A202844(n).

Examples

			Row 5 is 8: 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; none of them has stacks of length 3.
Triangle starts:
1;
1;
1;
2;
4;
8;
17;
36,1;
79,3;
		

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. A004148, A202838, A202839, A202840, A202841, A202842, A202844

Programs

Maple

f := (t-1)*z^6+z^2/(1-z^2): eq := G = 1+z*G+f*G*(G-1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 26)): for n from 0 to 22 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 22 do seq(coeff(P[n], t, k), k = 0 .. degree(P[n])) end do; # yields sequence in triangular form

Formula

G.f.: G(t,z) satisfies G = 1 + zG + [f/(1 + f)]G(G-1), where f = (t-1)z^6 + z^2/(1-z^2).

The multivariate g.f. H(z, t[1], t[2], ...) of secondary structures with respect to size (marked by z) and number of stacks of length j (marked by t[j]) satisfies H = 1 + zH + [f/(1 + f)]H(H-1), where f = t[1]z^2 + t[2]z^4 + t[3]z^6 + ... .