OFFSET
0,5
COMMENTS
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, Jun 07 2006
LINKS
Paul D. Hanna, Table of n, a(n) for n = 0..1325
J.-L. Baril, R. Genestier, S. Kirgizov, Pattern distributions in Dyck paths with a first return decomposition constrained by height, Disc. Math. 343 (9) (2020), Table 1.
L. Ferrari, E. Munarini, Enumeration of Edges in Some Lattices of Paths, J. Int. Seq. 17 (2014) #14.1.5
FORMULA
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].
EXAMPLE
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);
column 5: (1 + 10*x^2 + 20*x^4 + 10*x^6 + x^8)/((1-x)^11*(1+x)^5); ...
where the coefficients in the above numerator polynomials form the Narayana triangle A001263:
1;
1, 1;
1, 3, 1;
1, 6, 6, 1;
1, 10, 20, 10, 1; ...
PROG
(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)); ))}
for(n=0, 12, for(k=0, n, print1(T(n, k), ", ")); print(""))
(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); ))}
for(n=0, 12, for(k=0, n, print1(T(n, k), ", ")); print(""))
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Paul D. Hanna, Jul 24 2005
STATUS
approved