A108446 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A108446

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, 4, 5, 1, 20, 32, 13, 1, 113, 223, 135, 26, 1, 688, 1620, 1300, 412, 45, 1, 4404, 12064, 12050, 5350, 1030, 71, 1, 29219, 91335, 109134, 62450, 17575, 2247, 105, 1, 199140, 699689, 973077, 682234, 254625, 49210, 4438, 148, 1, 1385904, 5407744

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

Row sums yield A027307. Column 0 yields A108447. T(n,n-1) = A008778(n-1) = n(n^2+6n-1)/6. Number of ud peaks in all paths from (0,0) to (3n,0) is given by A108448.

LINKS

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

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)*sum(binomial(n-k,j)*binomial(n+2j,k+j-1), j=0..n-k).

G.f.: G = G(t,z) satisfies G = 1+z(G-1+t)G+zG^3.

EXAMPLE

T(2,1) = 5 because we have udUdd, uudd, Uddud, Ududd and Uuddd.

Triangle begins:

1,1;

4,5,1;

20,32,13,1;

113,223,135,26,1;

MAPLE

T:=proc(n, k) if n=0 and k=0 then 1 elif n=0 then 0 elif k=n then 1 elif k=n then 1 else (1/n)*binomial(n, k)*sum(binomial(n-k, j)*binomial(n+2*j, k+j-1), j=0..n-k) fi end: for n from 0 to 9 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

MATHEMATICA

T[0, 0] = 1; T[n_, k_] := (1/n) Binomial[n, k]*Sum[Binomial[n-k, j]* Binomial[n+2j, k+j-1], {j, 0, n-k}];

Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 19 2018 *)

CROSSREFS

Cf. A027307, A008778, A108447, A108448, A108425, A108426.

Sequence in context: A266699 A234937 A210590 * A283263 A109962 A102230

Adjacent sequences: A108443 A108444 A108445 * A108447 A108448 A108449

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jun 10 2005

STATUS

approved