

A202848


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


3



1, 1, 1, 2, 4, 7, 1, 14, 3, 31, 6, 66, 16, 141, 44, 313, 107, 3, 702, 262, 14, 1577, 663, 43, 3581, 1654, 138, 8207, 4091, 436, 1, 18903, 10178, 1275, 16, 43770, 25339, 3638, 85, 101903, 62952, 10316, 331, 238282, 156495, 28743, 1228, 559322, 389374, 78979, 4320, 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).
Sum(k*T(n,k), k>=0) = A202846(n2).
T(n,0) = A202849(n).


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

G.f.: G(t,z) satisfies G = 1 + zG + [f/(1 + f)]G(G1), where f = (z^2 + t*z^4)/(1z^4).
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; the last one has 1 stack of length 2.
Triangle starts:
1;
1;
1;
2;
4;
7,1;
14,3;
31,6;


MAPLE

f := (z^2+t*z^4)/(1z^4): eq := G = 1+z*G+f*G*(G1)/(1+f): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 25)): 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. A004145, A202846, A023427, A202849,
Sequence in context: A098073 A118390 A247294 * A202841 A247290 A246183
Adjacent sequences: A202845 A202846 A202847 * A202849 A202850 A202851


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Dec 26 2011


STATUS

approved



