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,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

Table of n, a(n) for n=0..67.

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

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

Sequence in context: A229029 A055385 A160503 * A130280 A160127 A361226

Adjacent sequences: A108426 A108427 A108428 * A108430 A108431 A108432

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 03 2005

Status

approved