OFFSET
1,1
COMMENTS
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.
LINKS
Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.
FORMULA
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).
EXAMPLE
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).
Triangle begins:
2;
6,4;
34,24,8;
238,172,72,16;
1858,1360,624,192,32;
...
MAPLE
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
MATHEMATICA
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];
Table[T[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 11 2024, after Maple code. *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 04 2005
EXTENSIONS
Keyword tabf changed to tabl by Michel Marcus, Apr 09 2013
STATUS
approved