OFFSET
0,7
COMMENTS
A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. An ascent in a Motzkin path is a maximal sequence of consecutive U steps.
Row n contains 1+floor(n/3) terms.
Row sums yield the RNA secondary structure numbers (A004148).
T(3n,n) = A000108(n) (the Catalan numbers).
Sum(k*T(n,k),k=0..floor(n/3)) = A114713(n-3) (n>=3).
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.
FORMULA
G.f.: G=G(t, z) satisfies G=1+zG+z^2*(tzG+G-1-zG)G.
EXAMPLE
T(6,2)=2 because we have (U)HD(U)HD and (U)H(U)HDD (the ascents are shown between parentheses).
Triangle begins:
1;
1;
1;
1,1;
1,3;
1,7;
1,14,2;
MAPLE
G:=(1+z^2-z-sqrt(1-z^2-2*z+z^4+2*z^3-4*z^3*t))/2/z^2/(z*t+1-z): Gser:=simplify(series(G, z=0, 22)): P[0]:=1: for n from 1 to 18 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 18 do seq(coeff(t*P[n], t^j), j=1..1+floor(n/3)) od; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Dec 27 2005
STATUS
approved