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,2

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

Links

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

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]

Example

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.

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

Crossrefs

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

Cf. A054474 (row sums).

Sequence in context: A352029 A025521 A305109 * A098919 A161748 A369011

Adjacent sequences: A068215 A068216 A068217 * A068219 A068220 A068221

Keyword

easy,nice,nonn,tabl

Author

Martin Wohlgemuth, Mar 24 2002

Status

approved