

A202841


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


6



1, 1, 1, 2, 4, 7, 1, 14, 3, 31, 6, 66, 16, 142, 43, 316, 104, 3, 708, 256, 14, 1593, 647, 43, 3625, 1610, 138, 8314, 3990, 430, 1, 19165, 9944, 1247, 16, 44433, 24762, 3552, 85, 103557, 61574, 10040, 331, 242376, 153270, 27877, 1225, 569514, 381718, 76491, 4272, 9
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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


LINKS

Table of n, a(n) for n=0..51.
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

Sum(k*T(n,k), k>=0) = A202839(n2).
T(n,0) = A202842(n).
G.f. G(t,z) satisfies G = 1 + zG + [f/(1 + f)]G(G1), where f = (t1)z^4 + 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 7,1: 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 a stack of length 2.
Triangle starts:
1;
1;
1;
2;
4;
7,1;
14,3;
31,6;


MAPLE

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


CROSSREFS

Cf. A004148, A202838, A202839, A202840, A202842, A202843, A202844
Sequence in context: A118390 A247294 A202848 * A247290 A246183 A134974
Adjacent sequences: A202838 A202839 A202840 * A202842 A202843 A202844


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Dec 25 2011


STATUS

approved



