A110235 Triangle read by rows: T(n,k)(1<=k<=n) is the number of peakless Motzkin paths of length n having k (1,0) steps (can be easily translated into RNA secondary structure terminology).
1, 0, 1, 1, 0, 1, 0, 3, 0, 1, 1, 0, 6, 0, 1, 0, 6, 0, 10, 0, 1, 1, 0, 20, 0, 15, 0, 1, 0, 10, 0, 50, 0, 21, 0, 1, 1, 0, 50, 0, 105, 0, 28, 0, 1, 0, 15, 0, 175, 0, 196, 0, 36, 0, 1, 1, 0, 105, 0, 490, 0, 336, 0, 45, 0, 1, 0, 21, 0, 490, 0, 1176, 0, 540, 0, 55, 0, 1, 1, 0, 196, 0, 1764, 0, 2520, 0
Offset: 1
Examples
T(5,3)=6 because we have UHDHH, UHHDH, UHHHD, HUHDH, HUHHD and HHUHD, where U=(1,1), D=(1,-1), H=(1,0). Triangle starts: 1; 0, 1; 1, 0, 1; 0, 3, 0, 1; 1, 0, 6, 0, 1; 0, 6, 0, 10, 0, 1; 1, 0, 20, 0, 15, 0, 1; 0, 10, 0, 50, 0, 21, 0, 1; 1, 0, 50, 0, 105, 0, 28, 0, 1; 0, 15, 0, 175, 0, 196, 0, 36, 0, 1; 1, 0, 105, 0, 490, 0, 336, 0, 45, 0, 1; ...
Links
- W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.
- P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1978), 261-272.
- M. Vauchassade de Chaumont and G. Viennot, Polynômes orthogonaux et problèmes d'énumération en biologie moléculaire, Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, Actes 8e Sem. Lotharingien, pp. 79-86.
Programs
-
Maple
T:=proc(n,k) if n+k mod 2 = 0 then 2*binomial((n+k)/2,k)*binomial((n+k)/2,k-1)/(n+k) else 0 fi end: for n from 1 to 14 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form
-
PARI
T(n,k)=polcoeff(polcoeff(exp(sum(m=1,n,sum(j=0,m,binomial(m,j)^2*y^j*x^(m-j))*x^m/m)+O(x^(n+1))),n,x),k,y) for(n=0,10,for(k=0,n,print1(T(n,k),", "));print()) \\ Paul D. Hanna, Oct 21 2012
Formula
T(n, k) = [2/(n+k)]binomial((n+k)/2, k)*binomial((n+k)/2, k-1).
G.f.: g=g(t, z) satisfies g=1+tzg+z^2*g(g-1).
G.f.: A(x,y) = exp( Sum_{n>=1} [Sum_{k=0..n} C(n,k)^2 * y^k * x^(n-k)] * x^n/n ). - Paul D. Hanna, Oct 21 2012
Comments