A068218 Triangle of numbers of square lattice walks that start and end at origin after 2k steps and contain exactly r steps to the east, not touching origin at intermediate stages.

1, 2, 2, 2, 16, 2, 4, 84, 84, 4, 10, 400, 1056, 400, 10, 28, 1820, 9184, 9184, 1820, 28, 84, 8064, 66276, 126720, 66276, 8064, 84, 264, 35112, 426888, 1329768, 1329768, 426888, 35112, 264, 858, 151008, 2546544, 11737440, 19123776, 11737440

Offset: 0

Author

Martin Wohlgemuth, Mar 24 2002

Keywords

• easy
• nice
• nonn
• tabl

Comments

The given recurrences do not provide a means to calculate T(2r,r). But T(2r,r) is computable by the formula relating T(k,r) to A069466(k,r).

Examples

			T(3,1)=84 because there are 84 distinct lattice walks of length 2*3=6 starting and ending at the origin and containing exactly 1 step to the east and not touching origin at intermediate steps. Let E, W, S, N denote the 4 possible directions, then NNEWSS and NWSSNE are examples of such walks.
		

Crossrefs

T(k, 0) = A002420(k) = A069466(k)/(2k-1).

Cf. A054474 (row sums).

Programs

Mathematica

A069466[k_, r_] := Binomial[2 k, k]*Binomial[k, r]^2; t[k_, r_] := t[k, r] = A069466[k, r] - Sum[Sum[t[i, j]*A069466[k - i, r - j], {j, 0, r}], {i, 1, k - 1}]; Table[t[k, r], {k, 0, 8}, {r, 0, k}] // Flatten (* Jean-François Alcover, Nov 21 2012, from formula *)

Formula

T(k, r) = 2*(2k-3)/(k-2r) * ( T(k-1, r) - T(k-1, r-1) ), for k > 2r. T(1, 0)=2, T(1, 1)=2 Sum[T(k, r), r=0, ..., k] = A054474(k) T(k, r)=A069466(k, r) - Sum[ Sum[ T(i, j)*A069466(k-i, r-j), j=0...r], i=1, k-1]