login
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.
6
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
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jun 03 2005
STATUS
approved