|
| |
|
|
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).
|
|
0
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
| |
|
|
