A089731 Triangle of T(n,k)=number of peakless Motzkin paths of length n having k (1,0) steps at level zero (can be easily translated into RNA secondary structure terminology).

1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 1, 2, 2, 3, 0, 0, 1, 5, 4, 3, 4, 0, 0, 1, 10, 11, 6, 4, 5, 0, 0, 1, 22, 22, 18, 8, 5, 6, 0, 0, 1, 50, 49, 36, 26, 10, 6, 7, 0, 0, 1, 113, 114, 81, 52, 35, 12, 7, 8, 0, 0, 1, 260, 260, 193, 118, 70, 45, 14, 8, 9, 0, 0, 1, 605, 604, 444, 288, 160, 90, 56

Offset

0,12

References

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

Links

Table of n, a(n) for n=0..84.

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.]

M. S. Waterman, Home Page (contains copies of his papers)

Formula

G.f.= g/(1+zg-tzg), where g := (1-z+z^2-sqrt(1-2z-z^2-2z^3+z^4))/(2z^2) is the g.f. of A004148.

T(n,m) = Sum_{j=0..n-m}((m+j+1)*binomial(m+j,j)*Sum_{i=0..(n-j+1)/2 }((binomial(m+j+2*i+1,i)*Sum_{k=0..n-m-j-2*i}(binomial(k,n-m-k-j-2*i)*binomial(m+k+j+2*i,k)*(-1)^(n-m-k)))/(m+j+2*i+1))). - Vladimir Kruchinin, Mar 07 2016

Example

T(5,2)=3 because we have H'H'UHD, H'UHDH' and UHDH'H', where U=(1,1), D=(1,-1), H=(1,0) and H' indicates an H step at level zero.
1; 0,1; 0,0,1; 1,0,0,1; 1,2,0,0,1; 2,2,3,0,0,1; 5,4,3,4,0,0,1; 10,11,6,4,5,0,0,1; 22,22,18,8,5,6,0,0,1;

Prog

(Maxima)
T(n, m):=sum((m+j+1)*binomial(m+j, j)*sum((binomial(m+j+2*i+1, i)*sum(binomial(k, n-m-k-j-2*i)*binomial(m+k+j+2*i, k)*(-1)^(n-m-k), k, 0, n-m-j-2*i))/(m+j+2*i+1), i, 0, (n-j+1)/2), j, 0, n-m); /* Vladimir Kruchinin, Mar 07 2016 */

Crossrefs

Row sums give A004148.

Sequence in context: A089616 A089615 A301593 * A097098 A123679 A167948

Adjacent sequences: A089728 A089729 A089730 * A089732 A089733 A089734

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 07 2004

Status

approved