A098071 Triangle read by rows: T(n,k) is number of peakless Motzkin paths of length n and having k uhh...hd's starting at level 0, where u=(1,1), h=(1,0) and d=(1,-1) (can be easily expressed using RNA secondary structure terminology).
1, 1, 1, 1, 1, 1, 3, 2, 6, 6, 10, 1, 17, 15, 5, 44, 23, 15, 107, 42, 35, 1, 252, 94, 70, 7, 588, 233, 129, 28, 1376, 585, 237, 84, 1, 3245, 1441, 468, 210, 9, 7717, 3481, 1026, 466, 45, 18485, 8319, 2434, 968, 165, 1, 44535, 19835, 5972, 1984, 495, 11, 107796, 47436
Offset: 0
Examples
Triangle starts: 1; 1; 1; 1,1; 1,3; 2,6; 6,10,1; 17,15,5; 44,23,15; 107,42,35,1; T(6,2)=1 because we have (uhd)(uhd) (the two pertinent subwords are shown between parentheses).
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 aG^2 + bG + c = 0, where a=z^2*(1-z-z^2+2z^3-tz+2tz^2-2tz^3-tz^4+t^2z^4), b=-(1-z)(1-2z+2z^2+z^3-2tz^3), c=(1-z)^2.
The g.f. H(t,z), counting peakless Motzkin paths by the number of UH^bD (b is fixed) starting at level 0 (marked by t) and by length (marked by z), satisfies the equation H=1+zH+z^2*H(g-1-z^b + tz^b), where g=1+zg+z^2*g(g-1).
Comments