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

Author

Emeric Deutsch, Jun 03 2005

Keywords

• nonn
• tabf

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

Examples

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

Links

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

Crossrefs

Cf. A027307.

Programs

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

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.