|
%I #21 Sep 20 2020 19:15:16
%S 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,
%T 66,111,85,36,7,1,1,20,110,240,260,146,49,8,1,1,25,170,485,676,526,
%U 231,64,9,1,1,30,255,900,1615,1602,959,344,81,10,1,1,36,365,1590,3515,4432
%N 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).
%C Row sums form the Motzkin numbers (A001263).
%C 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
%H Paul D. Hanna, <a href="/A110470/b110470.txt">Table of n, a(n) for n = 0..1325</a>
%H J.-L. Baril, R. Genestier, S. Kirgizov, <a href="https://doi.org/10.1016/j.disc.2020.111995">Pattern distributions in Dyck paths with a first return decomposition constrained by height</a>, Disc. Math. 343 (9) (2020), Table 1.
%H L. Ferrari, E. Munarini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ferrari/ferrari.html">Enumeration of Edges in Some Lattices of Paths</a>, J. Int. Seq. 17 (2014) #14.1.5
%F T(n, k) = Sum_{j=0..n-k-1} C(n-j, k-j)*T(n-k-1, j).
%F 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].
%e 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)
%e = 1*35 + 4*15 + 3*5 + 1*1 = 111.
%e Triangle begins:
%e 1;
%e 1, 1;
%e 1, 2, 1;
%e 1, 4, 3, 1;
%e 1, 6, 9, 4, 1;
%e 1, 9, 19, 16, 5, 1;
%e 1, 12, 38, 44, 25, 6, 1;
%e 1, 16, 66, 111, 85, 36, 7, 1;
%e 1, 20, 110, 240, 260, 146, 49, 8, 1;
%e 1, 25, 170, 485, 676, 526, 231, 64, 9, 1; ...
%e Row sums form the Motzkin numbers:
%e {1,2,4,9,21,51,127,323,835,2188,...}.
%e G.f. of columns are:
%e column 1: 1/((1-x)^3*(1+x)^1);
%e column 2: (1 + x^2)/((1-x)^5*(1+x)^2);
%e column 3: (1 + 3*x^2 + x^4)/((1-x)^7*(1+x)^3);
%e column 4: (1 + 6*x^2 + 6*x^4 + x^6)/((1-x)^9*(1+x)^4);
%e column 5: (1 + 10*x^2 + 20*x^4 + 10*x^6 + x^8)/((1-x)^11*(1+x)^5); ...
%e where the coefficients in the above numerator polynomials form the Narayana triangle A001263:
%e 1;
%e 1, 1;
%e 1, 3, 1;
%e 1, 6, 6, 1;
%e 1, 10, 20, 10, 1; ...
%o (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));))}
%o for(n=0,12, for(k=0,n, print1(T(n,k),", "));print(""))
%o (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);))}
%o for(n=0,12, for(k=0,n, print1(T(n,k),", "));print(""))
%Y Cf. A001006 (Motzkin), A001263 (Narayana triangle).
%K nonn,tabl
%O 0,5
%A _Paul D. Hanna_, Jul 24 2005
|
