A108429 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 down steps (d).
1, 0, 1, 1, 0, 0, 2, 5, 3, 0, 0, 0, 5, 21, 28, 12, 0, 0, 0, 0, 14, 84, 180, 165, 55, 0, 0, 0, 0, 0, 42, 330, 990, 1430, 1001, 273, 0, 0, 0, 0, 0, 0, 132, 1287, 5005, 10010, 10920, 6188, 1428, 0, 0, 0, 0, 0, 0, 0, 429, 5005, 24024, 61880, 92820, 81396, 38760, 7752, 0, 0, 0, 0
Offset: 0
Examples
Example T(2,3) = 5 because we have udUdd, uUddd, Uddud, Ududd and Uuddd. Triangle begins: 1; 0,1,1; 0,0,2,5,3; 0,0,0,5,21,28,12; ...
Links
- Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.
Programs
-
Maple
a:=proc(n,k) if n=0 and k=0 then 1 elif n=0 then 0 elif k=0 then 0 else binomial(n,2*n-k)*binomial(n+k,n-1)/n fi end: for n from 0 to 8 do seq(a(n,k),k=0..2*n) od; # yields sequence in triangular form
Formula
T(n,k) = binomial(n,2n-k)*binomial(n+k, n-1)/n.
G.f.: G = G(t, z) satisfies G=1+tzG^2*(1+tG).
Comments