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

Author

Emeric Deutsch, Jun 03 2005

Keywords

• nonn
• tabl

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.

Examples

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

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.

Crossrefs

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

Programs

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

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

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.