login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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 returns to the x-axis.
2

%I #15 Aug 11 2024 22:06:31

%S 2,6,4,34,24,8,238,172,72,16,1858,1360,624,192,32,15510,11444,5520,

%T 1952,480,64,135490,100520,50040,19136,5600,1152,128,1223134,911068,

%U 463512,186416,60320,15168,2688,256,11320066,8457504,4371808,1821312,629440,178176,39424,6144,512

%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 returns to the x-axis.

%C 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 steps up to the first peak. Example: T(2,2)=4 because we have uudd, uUddd, Uuddd and UUdddd. Row sums yield A027307. T(n,1)=A108424(n). T(n,n)=2^n.

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

%F T(n, k)=[k/(n-k)][3*2^k*binomial(n-1, k)+sum(2^(n-1-j)*(5n-2k+j+1)binomial(n-1, j)binomial(2n-k-1, n+j)/(n+j+1), j=0..n-k-2)] if k<n; T(n, n)=2^n. G.f. =1/(1-tzA-tzA^2)-1, where A=1+zA^2+zA^3 or, equivalently, A=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

%e T(2,2)=4 because u(d)u(d), u(d)Ud(d), Ud(d)u(d) and Ud(d)Ud(d) (the steps d that return to the x-axis are shown between parentheses).

%e Triangle begins:

%e 2;

%e 6,4;

%e 34,24,8;

%e 238,172,72,16;

%e 1858,1360,624,192,32;

%e ...

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

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

%t Table[T[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Aug 11 2024, after Maple code. *)

%Y Cf. A027307, A108424, A108436.

%K nonn,tabl

%O 1,1

%A _Emeric Deutsch_, Jun 04 2005

%E Keyword tabf changed to tabl by _Michel Marcus_, Apr 09 2013