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,8

Comments

Row sums yield A004148. sum(k*T(n,k),k=1..n)=A110236(n).

Links

Table of n, a(n) for n=1..86.

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.

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

Example

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

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

Prog

(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

Crossrefs

Cf. A004148, A110236.

Sequence in context: A229995 A119467 A166353 * A036856 A036855 A147985

Adjacent sequences: A110232 A110233 A110234 * A110236 A110237 A110238

Keyword

nonn,tabl

Author

Emeric Deutsch, Jul 17 2005

Status

approved