In the plane let the positive end of the $$𝑥-axis$$ be directed towards East and the positive end of the $$y-axis$$ be directed towards North. Suppose you are at $$(0, 0)$$ and you want to go to $$(7, 12)$$. At every move you are allowed to move unit length towards East or unit length towards North from your current position but you are not allowed to visit any point $$(ℎ, 𝑘)$$ where both $$ℎ, 𝑘$$ are odd. Find the number of such paths $$𝑛$$.

Let $$W(x,y)$$ denote the number of admissible paths from the origin $$(0,0)$$ to the lattice point $$(x,y)$$ when we are

  • allowed moves : one step East (E) $$:(x,y)\rightarrow (x+1,y)$$ or one step North (N) $$:(x,y)\rightarrow (x,y+1)$$
  • forbidden points : those with both coordinates odd, i.e. $$(x,y)$$ with $$x$$ odd and $$y$$ odd.

The usual additive recurrence for rectangular‐grid paths remains valid provided the destination point itself is not forbidden:

If $$(x,y)$$ is not forbidden, then
$$W(x,y)=W(x-1,y)+W(x,y-1)$$   -(1)

If $$(x,y)$$ is forbidden (both $$x,y$$ odd) we put $$W(x,y)=0$$.

Initialisation : $$W(0,0)=1$$. On the coordinate axes at least one coordinate is even, hence no point on either axis is forbidden. Therefore

$$W(x,0)=1\;(0\le x\le 7),\qquad W(0,y)=1\;(0\le y\le 12).$$

Using (1) row by row (or column by column) we fill the $$8\times 13$$ array $$\{0\le x\le 7,\;0\le y\le 12\}.$$ The forbidden points are left blank (value 0).

y \x  0 1 2 3 4 5 6 7
0  1 1 1 1 1 1 1 1
1  1 0 1 0 1 0 1 0
2  1 1 2 2 3 3 4 4
3  1 0 2 0 3 0 4 0
4  1 1 3 3 6 6 10 10
5  1 0 3 0 6 0 10 0
6  1 1 4 4 10 10 20 20
7  1 0 4 0 10 0 20 0
8  1 1 5 5 15 15 35 35
9  1 0 5 0 15 0 35 0
10 1 1 6 6 21 21 56 56
11 1 0 6 0 21 0 56 0
12 1 1 7 7 28 28 84 84

The last entry in the table is $$W(7,12)=84$$, because $$(7,12)$$ itself is admissible (7 is odd, 12 is even).

Hence, the required number of paths is

$$n = 84$$