A068218 - OEIS

%I #12 Apr 20 2020 02:27:30

%S 1,2,2,2,16,2,4,84,84,4,10,400,1056,400,10,28,1820,9184,9184,1820,28,

%T 84,8064,66276,126720,66276,8064,84,264,35112,426888,1329768,1329768,

%U 426888,35112,264,858,151008,2546544,11737440,19123776,11737440

%N 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.

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

%F 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]

%e 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.

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

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

%Y Cf. A054474 (row sums).

%K easy,nice,nonn,tabl

%O 0,2

%A _Martin Wohlgemuth_, Mar 24 2002