A089731 - OEIS

%I #14 Mar 07 2016 12:36:28

%S 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,

%T 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,

%U 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

%N 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).

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

%H P. R. Stein and M. S. Waterman, <a href="http://dx.doi.org/10.1016/0012-365X(79)90033-5">On some new sequences generalizing the Catalan and Motzkin numbers</a>, Discrete Math., 26 (1979), 261-272.

%H M. Vauchassade de Chaumont and G. Viennot, <a href="http://www.mat.univie.ac.at/~slc/opapers/s08viennot.html">Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire</a>, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

%H M. S. Waterman, <a href="http://www.cmb.usc.edu/people/msw/Waterman.html">Home Page</a> (contains copies of his papers)

%F 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.

%F 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

%e 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.

%e 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;

%o (Maxima)

%o 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 */

%Y Row sums give A004148.

%K nonn,tabl

%O 0,12

%A _Emeric Deutsch_, Jan 07 2004