OFFSET
0,7
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.
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.]
FORMULA
G.f.: G=G(t, z) satisfies G=1+zG+tz^2*G(G-1)/(1-z^2+tz^2).
EXAMPLE
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.
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Sep 14 2004
STATUS
approved