A098093 Triangle read by rows: T(n,k) is the number of peakless Motzkin paths of length n and having k ladders.

1, 1, 1, 1, 1, 1, 3, 1, 7, 1, 13, 3, 1, 22, 14, 1, 34, 46, 1, 1, 50, 118, 16, 1, 70, 264, 88, 1, 95, 530, 343, 9, 1, 125, 986, 1066, 105, 1, 161, 1722, 2857, 630, 2, 1, 203, 2863, 6841, 2751, 76, 1, 252, 4564, 15028, 9746, 781, 1, 308, 7028, 30778, 29778, 4909, 30

Offset: 0

Author

Emeric Deutsch, Sep 14 2004

Keywords

• nonn
• tabf

Comments

A string of consecutive up steps U_1, U_2, ..., U_m and their matching down steps D_1, D_2, ..., D_m are said to form a ladder if (i) D_1, D_2, ..., D_m are consecutive steps and (ii) the sequence of pairs (U_j, D_j) (j=1,2,...,m) is maximal. For example, in the path (UU)[U]H[D]H(DD), where U=(1,1), H=(1,0), D=(1,-1), we have 2 ladders, shown between parentheses and square brackets, respectively.

Row sums yield the RNA secondary structure numbers (A004148). Column 1 is A002623.

Examples

			Triangle starts:
1;
1;
1;
1,1;
1,3;
1,7;
1,13,3;
1,22,14;
1,34,46,1;
Apparently, rows 5n+1 and 5n+2 have 2n+1 terms and rows 5n+3,5n+4 and 5n+5 have 2n+2 terms.
T(6,2)=3 because we have (U)H(D)[U]H[D], (U)H[U]H[D](D) and (U)[U]H[D]H(D), the two ladders being shown between parentheses and square brackets, respectively.
		

Links

• 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, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

Crossrefs

Cf. A004148, A002623.

Formula

G.f.: G=G(t, z) satisfies G=1+zG+tz^2*G(G-1)/(1-z^2+tz^2).