A108426 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 peaks of the form Ud.

1, 1, 1, 3, 5, 2, 12, 28, 21, 5, 55, 165, 180, 84, 14, 273, 1001, 1430, 990, 330, 42, 1428, 6188, 10920, 10010, 5005, 1287, 132, 7752, 38760, 81396, 92820, 61880, 24024, 5005, 429, 43263, 245157, 596904, 813960, 678300, 352716, 111384, 19448, 1430, 246675

Offset

0,4

Comments

Row sums yield A027307.

T(n,n) = A000108(n) (the Catalan numbers).

T(n,0) = A001764(n) = binomial(3n,n)/(2n+1).

Number of Ud peaks in all paths from (0,0) to (3n,0) is given by A108427.

Links

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Formula

T(n,k) = (1/n)*binomial(n,k)*binomial(3*n-k,n-1).

G.f.: G = G(t,z) satisfies G=1+z(t+G)G^2.

Example

Example T(2,1) = 5 because we have udUdd, uUddd, Uddud, Ududd and UUdddd.
Triangle begins:
1;
1,1;
3,5,2;
12,28,21,5;
...

Maple

T:=(n, k)->binomial(n, k)*binomial(3*n-k, n-1)/n: print(1); for n from 1 to 9 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Mathematica

Table[If[n == 0, 1, (1/n)*Binomial[n, k]*Binomial[3 n - k, n - 1]], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, Nov 29 2017 *)

Prog

(PARI) for(n=0, 10, for(k=0, n, print1(if(n==0, 1, (1/n)*binomial(n, k) *binomial(3*n-k, n-1)), ", "))) \\ G. C. Greubel, Nov 29 2017

Crossrefs

Cf. A027307, A000108, A001764, A108425, A108427.

Sequence in context: A324776 A325891 A217859 * A355267 A301305 A163237

Adjacent sequences: A108423 A108424 A108425 * A108427 A108428 A108429

Keyword

nonn,tabl

Author

Emeric Deutsch, Jun 03 2005

Status

approved