login
A108435
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
2, 6, 4, 34, 24, 8, 238, 172, 72, 16, 1858, 1360, 624, 192, 32, 15510, 11444, 5520, 1952, 480, 64, 135490, 100520, 50040, 19136, 5600, 1152, 128, 1223134, 911068, 463512, 186416, 60320, 15168, 2688, 256, 11320066, 8457504, 4371808, 1821312, 629440, 178176, 39424, 6144, 512
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