|
%I #12 Nov 28 2019 08:07:52
%S 1,1,1,2,4,8,17,36,1,77,5,167,18,365,58,805,172,1,1790,486,7,4008,
%T 1331,34,9033,3561,141,20477,9370,524,1,46663,24350,1810,9,106843,
%U 62674,5930,55,245691,160126,18652,279,567194,406732,56832,1245,1,1314086,1028360
%N Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n containing k DHH...HU's, where U=(1,1), D=(1,-1) and H=(1,0) (can be easily expressed using RNA secondary structure terminology).
%C Row n >= 3 has ceiling((n-2)/4) terms.
%C Row sums yield the RNA secondary structure numbers (A004148).
%C T(n,0) = A190162(n).
%C Sum_{k>=0} k*T(n,k) = A190163(n).
%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 + z*G + z^2*(G-1)*(G - (1-t)*z*(G-z*G-1)/(1-z)).
%e Triangle starts:
%e 1;
%e 1;
%e 1;
%e 2;
%e 4;
%e 8;
%e 17;
%e 36, 1;
%e 77, 5;
%e 167, 18
%e T(8,1)=5 because we have UH(DHU)HHD, HUH(DHU)HD, UH(DHHU)HD, UH(DHU)HDH and UHH(DHU)HD (the required subwords are shown between parentheses).
%p eq := G = 1+z*G+z^2*(G-1)*(G-(1-t)*z*(G-1-z*G)/(1-z)): G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 23)): for n from 0 to 20 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 20 do seq(coeff(P[n], t, j), j = 0 .. degree(P[n])) end do; # yields sequence in triangular form
%Y Cf. A004148.
%K nonn,tabf
%O 0,4
%A _Emeric Deutsch_, Sep 13 2004
|
