

A202838


Triangle read by rows: T(n,k) is the number of secondary structures of size n (n>=0) having k stacks of length 1 (k>=0).


6



1, 1, 1, 1, 1, 1, 3, 2, 6, 4, 10, 3, 8, 15, 14, 14, 27, 40, 1, 23, 56, 90, 16, 38, 122, 178, 85, 65, 253, 356, 295, 9, 117, 494, 762, 805, 105, 214, 938, 1713, 1912, 594, 2, 391, 1783, 3828, 4326, 2331, 76, 708, 3456, 8265, 9882, 7290, 771, 1278, 6793, 17309, 23109, 19784, 4529, 30
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,7


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).
T(n,0)=A202840(n).


LINKS

Table of n, a(n) for n=0..61.
I. L. Hofacker, P. Schuster and P. F. Stadler, Combinatorics of RNA secondary structures, Discrete Appl. Math., 88, 1998, 207237.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261272.


FORMULA

G.f. G(t,z) satisfies G = 1 + zG + [f/(1 + f)]G(G1), where f = (t1)z^2 + z^2/(1z^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(H1), where f = t[1]z^2 + t[2]z^4 + t[3]z^6 + ... .


EXAMPLE

Row 5 is 2,6: 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.
Triangle starts:
1;
1;
1;
1,1;
1,3;
2,6;
4,10,3;
8,15,14;


MAPLE

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


CROSSREFS

Cf. A202839, A202840, A202841, A202842, A202843, A202844
Sequence in context: A257910 A006368 A202845 * A105354 A094077 A260220
Adjacent sequences: A202835 A202836 A202837 * A202839 A202840 A202841


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Dec 25 2011


STATUS

approved



