OFFSET
0,4
COMMENTS
Row sums are the RNA secondary structure numbers (A004148).
T(n,0)=A190160(n).
Sum(k*T(n,k),k>=0)=A190161(n).
The generating function G=G(t,s,z) relative to the number of subwords of the form uh^bu (marked by t) and dh^bd (marked by s) for a fixed b>=1, satisfies G = 1+zG+z^2*G[z/(1-z) + (w^2+twz^b+swz^b+tsz^{2b})H], where H=(1-z)[(1-z)G-1] and w = 1/(1-z) - z^b.
REFERENCES
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.
M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux et problemes d'enumeration en biologie moleculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
LINKS
M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86.
FORMULA
G.f.=G=G(t, z) satisfies G=1+zG+z^2*G*[z+(1-z+t*z)^2*(G-zG-1)]/(1-z).
EXAMPLE
Triangle starts:
1;
1;
1;
2;
4;
8;
15,2;
28,8,1;
53,24,5;
It seems that, except for the first 3 rows, rows 4n-1, 4n, 4n+1 have 2n-1 terms and rows 4n+2 have 2n terms (n=1,2,...).
T(8,2)=5 because we have (UHU)H(DHD)H, (UHU)HH(DHD), H(UHU)H(DHD), (UHHU)H(DHD) and (UHU)H(DHHD); the required subwords are shown between parentheses.
MAPLE
eq := G = 1+z*G+z^2*G*(z+(1-z+t*z)^2*(G-z*G-1))/(1-z): G:= RootOf(eq, G): Gser := simplify(series(G, z=0, 20)): 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, j), j=0 .. degree(P[n])) end do; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Sep 15 2004
STATUS
approved