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
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 25.
Jean Luc Baril, Richard Genestier, and Sergei Kirgizov, Pattern distributions in Dyck paths with a first return decomposition constrained by height, Disc. Math. 343 (9) (2020), Table 1.
Luca Ferrari and Emanuele 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
