A108428 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 doubledescents (i.e., dd's).

1, 1, 1, 1, 4, 4, 1, 1, 9, 23, 23, 9, 1, 1, 16, 76, 156, 156, 76, 16, 1, 1, 25, 190, 650, 1167, 1167, 650, 190, 25, 1, 1, 36, 400, 2045, 5685, 9318, 9318, 5685, 2045, 400, 36, 1, 1, 49, 749, 5341, 21133, 50813, 77947, 77947, 50813, 21133, 5341, 749, 49, 1, 1, 64, 1288

Offset

0,5

Comments

Row n contains 2n terms (n > 0).

Row sums yield A027307.

T(n,1) = T(n,2n-2) = n^2*T(n,k) = T(n,2n-k-1) (mirror symmetry).

Links

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

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

Formula

T(n, k) = (1/n)*Sum_{j=0..k} binomial(n, j)*binomial(n, k-j)*binomial(n+j, k+1).

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

Example

T(2,1)=4 because we have udUdd, uudd, Uddud and Ududd.
Triangle begins:
  1;
  1,  1;
  1,  4,  4,   1;
  1,  9, 23,  23,   9,  1;
  1, 16, 76, 156, 156, 76, 16, 1;
  ...

Maple

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

Crossrefs

Cf. A027307.

Sequence in context: A198929 A172347 A375863 * A373431 A174126 A075613

Adjacent sequences: A108425 A108426 A108427 * A108429 A108430 A108431

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 03 2005

Status

approved