%I #10 Nov 05 2025 15:35:31

%S 1,1,1,4,5,1,20,32,13,1,113,223,135,26,1,688,1620,1300,412,45,1,4404,

%T 12064,12050,5350,1030,71,1,29219,91335,109134,62450,17575,2247,105,1,

%U 199140,699689,973077,682234,254625,49210,4438,148,1,1385904,5407744

%N Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and have k peaks of the form ud.

%C Row sums yield A027307. Column 0 yields A108447. T(n,n-1) = A008778(n-1) = n(n^2+6n-1)/6. Number of ud peaks in all paths from (0,0) to (3n,0) is given by A108448.

%H Emeric Deutsch, <a href="https://www.jstor.org/stable/2589192">Problem 10658: Another Type of Lattice Path</a>, American Math. Monthly, 107, 2000, 368-370.

%F T(n,k) = (1/n) binomial(n, k)*sum(binomial(n-k,j)*binomial(n+2j,k+j-1), j=0..n-k).

%F G.f.: G = G(t,z) satisfies G = 1+z(G-1+t)G+zG^3.

%e T(2,1) = 5 because we have udUdd, uudd, Uddud, Ududd and Uuddd.

%e Triangle begins:

%e 1;

%e 1,1;

%e 4,5,1;

%e 20,32,13,1;

%e 113,223,135,26,1;

%p T:=proc(n,k) if n=0 and k=0 then 1 elif n=0 then 0 elif k=n then 1 elif k=n then 1 else (1/n)*binomial(n,k)*sum(binomial(n-k,j)*binomial(n+2*j,k+j-1),j=0..n-k) fi end: for n from 0 to 9 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

%t T[0, 0] = 1; T[n_, k_] := (1/n) Binomial[n, k]*Sum[Binomial[n-k, j]* Binomial[n+2j, k+j-1], {j, 0, n-k}];

%t Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 19 2018 *)

%Y Cf. A027307, A008778, A108447, A108448, A108425, A108426.

%K nonn,tabl

%O 0,4

%A _Emeric Deutsch_, Jun 10 2005