%I #7 Mar 07 2016 11:32:20
%S 1,1,1,2,4,8,17,36,1,77,4,1,167,13,4,1,365,40,13,4,1,805,114,41,13,4,
%T 1,1790,314,119,42,13,4,1,4008,845,335,124,43,13,4,1,9033,2230,925,
%U 356,129,44,13,4,1,20477,5809,2506,1006,377,134,45,13,4,1,46663,14980,6712
%N Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and containing a total of k level steps H in all DHH...HU's, where U=(1,1), H=(1,0) and D=(1,-1) (can be easily expressed using RNA secondary structure terminology).
%C Row sums yield the RNA secondary structure numbers (A004148).
%H I. L. Hofacker, P. Schuster and P. F. Stadler, <a href="http://dx.doi.org/10.1016/S0166-218X(98)00073-0">Combinatorics of RNA secondary structures</a>, Discrete Appl. Math., 88, 1998, 207-237.
%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1979), 261-272.
%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]
%F G.f.: G=G(t, z) satisfies G=1+zG+z^2*(G-1)[(1-z)G+z(1-t)/(1-z)]/(1-tz).
%e Triangle starts:
%e 1;
%e 1;
%e 1;
%e 2;
%e 4;
%e 8;
%e 17;
%e 36,1;
%e 77,4,1;
%e 167,13,4,1;
%e Row n>=6 contains n-5 terms.
%e T(10,3)=4 because we have UHD(HHH)UHDH, UHD(HHH)UHHD, HUHD(HHH)UHD and UHHD(HHH)UHD, where U=(1,1), H=(1,0) and D=(1,-1); the 3 required H's are shown between parentheses.
%Y Cf. A004148.
%K nonn,tabf
%O 0,4
%A _Emeric Deutsch_, Sep 16 2004
|