login
Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and having k level steps at height >0 (can be easily expressed using RNA secondary structure terminology).
0

%I #8 Jan 13 2025 04:09:51

%S 1,1,1,1,1,1,2,1,1,4,2,1,1,6,7,2,1,1,9,13,11,2,1,1,12,28,22,16,2,1,1,

%T 16,46,64,33,22,2,1,1,20,80,118,126,46,29,2,1,1,25,120,258,248,225,61,

%U 37,2,1,1,30,185,438,668,460,374,78,46,2,1,1,36,260,813,1231,1506,782,588,97

%N Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n and having k level steps at height >0 (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>, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08; Sem. Loth. Comb. B08l (1984) 79-86.

%F G.f.: G=G(t, z) satisfies z(t-tz+tz^2-1+2z-z^2)G^2-(1-2z+z^2+tz)G+1=0.

%e Triangle starts:

%e 1;

%e 1;

%e 1;

%e 1,1;

%e 1,2,1;

%e 1,4,2,1;

%e 1,6,7,2,1;

%e 1,9,13,11,2,1;

%e ...

%e Row n (n>=2) has n-1 terms.

%e T(5,2)=2 because among the eight peakless Motzkin paths of length 5 only HU(HH)D and U(HH)DH have two H's at positive height (shown between parentheses); here U=(1,1), H=(1,0), D=(1,-1).

%Y Cf. A004148.

%K nonn,tabf

%O 0,7

%A _Emeric Deutsch_, Sep 12 2004