

A202851


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


0



1, 1, 1, 1, 1, 1, 3, 1, 6, 1, 10, 3, 1, 15, 14, 1, 21, 40, 1, 1, 28, 90, 16, 1, 36, 175, 85, 1, 45, 308, 295, 9, 1, 55, 504, 805, 105, 1, 66, 780, 1876, 594, 2, 1, 78, 1155, 3906, 2331, 76, 1, 91, 1650, 7470, 7280, 771, 1, 105, 2288, 13365, 19404, 4529, 30, 1, 120, 3094, 22660, 45990, 19348, 650
(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 A202850(n).


REFERENCES

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.


LINKS

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


FORMULA

G.f. G(t,z) satisfies G = 1 + zG + [tz^2/(1 + tz^2)]G(G1).
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 1,6: representing unpaired vertices by v and arcs by AA, BB, etc., the 7 (= A202850(5)) secondary structures of size 5 and with no stacks of length >=2 are vvvvv, AvAvv, vvAvA, AvvAv, vAvvA, AvvvA, vAvAv; with the exception of the first one, they all have 1 stack of length 1.
Triangle starts:
1;
1;
1;
1,1;
1,3;
1,6;
1,10,3;
1,15,14;


MAPLE

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


CROSSREFS

Cf. A202850
Sequence in context: A317496 A304236 A145063 * A007650 A236540 A165552
Adjacent sequences: A202848 A202849 A202850 * A202852 A202853 A202854


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Dec 27 2011


STATUS

approved



