login
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
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,7
COMMENTS
Row n contains 2n+1 terms, the first n of which are equal to 0.
Row sums yield A027307.
T(n,n) = A000108(n) (the Catalan numbers).
T(n,2n) = A001764(n) = binomial(3n,n)/(2n+1).
Except for the 0's, the same as A104978.
Number of d steps in all paths from (0,0) to (3n,0) is given by A108430.
LINKS
Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.
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).
EXAMPLE
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;
...
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
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jun 03 2005
STATUS
approved