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

Author

Emeric Deutsch, Jun 03 2005

Keywords

• nonn
• tabf

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.

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.

Crossrefs

Cf. A027307, A000108, A001764, A104978, A108430.

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).