A110470 Triangle, read by rows, where the g.f. of diagonal n, D_n(x) and the g.f. of row n-1, R_{n-1}(x), are related by: D_n(x) = R_{n-1}(x) / (1-x)^(n+1) for n>0 and the g.f. of the main diagonal is D_0(x) = 1/(1-x).

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, 1, 30, 255, 900, 1615, 1602, 959, 344, 81, 10, 1, 1, 36, 365, 1590, 3515, 4432

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

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

Sequence in context: A161492 A177976 A034781 * A347699 A055080 A034367

Adjacent sequences: A110467 A110468 A110469 * A110471 A110472 A110473

Keyword

nonn,tabl

Author

Paul D. Hanna, Jul 24 2005

Status

approved