0,5

Row sums form the Motzkin numbers (A001263).

With offset n>=1 and k>=0, T(n,k) is the number of Motzkin n-paths (A001006) with k weak valleys. A weak valley in a Motzkin path is an interior vertex whose following step has nonnegative slope and whose preceding step has nonpositive slope. For example, T(4,1)=4 counts F.UFD, UD.UD, UFD.F, UF.FD (U=upstep, D=downstep, F=flatstep, dots indicate weak valleys). - David Callan (callan(AT)stat.wisc.edu), Jun 07 2006

T(n, k) = Sum_{j=0..n-k-1} C(n-j, k-j)*T(n-k-1, j). G.f. of column k>0: [Sum_{j=0..k-1}A001263(k-1, j)*x^(2*j)]/[(1-x)^(2*n+1)*(1+x)^n].

T(6,3)=T(3,0)*C(7,3)+T(3,1)*C(6,2)+T(3,2)*C(5,1)+T(3,3)*C(4,0)

= 1*35 + 4*15 + 3*5 + 1*1 = 111.

Triangle begins:

1;

1,1;

1,2,1;

1,4,3,1;

1,6,9,4,1;

1,9,19,16,5,1;

1,12,38,44,25,6,1;

1,16,66,111,85,36,7,1;

1,20,110,240,260,146,49,8,1;

1,25,170,485,676,526,231,64,9,1; ...

Row sums form the Motzkin numbers:

{1,2,4,9,21,51,127,323,835,2188,...}.

G.f. of columns are:

column 1: 1/((1-x)^3*(1+x)^1);

column 2: (1 + x^2)/((1-x)^5*(1+x)^2);

column 3: (1 + 3*x^2 + x^4)/((1-x)^7*(1+x)^3);

column 4: (1 + 6*x^2 + 6*x^4 + x^6)/((1-x)^9*(1+x)^4);

where coefficients form the Narayana triangle A001263:

1;

1,1;

1,3,1;

1,6,6,1;

1,10,20,10,1; ...

(PARI) {T(n, k)=if(n<k|k<0, 0, if(k==0|k==n, 1, sum(j=0, n-k-1, T(n-k-1, j)*binomial(n-j, k-j)); ))} (PARI) {T(n, k)=local(X=x+x*O(x^n)); if(n<k|k<0, 0, if(k==0|k==n, 1, polcoeff(x^k*sum(j=0, k-1, binomial(k-1, j)*binomial(k, j)/(j+1)*x^(2*j)) /((1-X)^(k+1)*(1-X^2)^k), n); ))}

Cf. A001006 (Motzkin), A001263 (Narayana triangle).

Adjacent sequences: A110467 A110468 A110469 this_sequence A110471 A110472 A110473

Sequence in context: A026769 A060098 A034781 this_sequence A055080 A034367 A058717

nonn,tabl

Paul D. Hanna (pauldhanna(AT)juno.com), Jul 24 2005