Finding the # of paths in a grid from opposite corner but most avoid certain paths

Question

In x-y coordinate you start out at (0,0) and you want to get to (8,14) by either moving up or right only.

You can't move to any points that are both odd, e.g. (1,1), (1,3)... (3,1), (3,3) ... (7, 13).

So my strategy is to count all the possible paths and subtract out the path that hits the (odd,odd) coordinates.

Total path in this 8 by 14 grid is

$$\binom{22}{8} or \binom{22}{14}$$

Now I need to subtract the paths that hit (odd,odd) from that.

I'm not wrapping my head around how to count the number of ways you can hit the (odd,odd) coordinates. One way is to brute force it by counting # of ways to get to (1,1), (1,3)... etc. but that's really inefficient and I think I will accidentally double count a lot of the paths.

Answer 1

Hint: In two consecutive steps, you must move uu (up, up) or rr (right, right). Let's shorten uu to U and rr to R. Then you have to make a total of $4$ R's and $7$ U's.

Answer 2

If you start writing down the number of possible paths, do you see a pattern developing? (The faintly shaded bits are examples of where there two positions from which you could arrive at one spot, so the numbers of paths from the start to each of those previous positions need to be added.)

Answer 3

From the picture of Steve Kass it is obvious that once you are on any white square between two red ones the next step is predetermined and will not contribute to the multiplicity of the possible paths. If you are on the white square which up- and right-neighbours are white, you are in the situation (locally) as if there would be no restrictions (no red squares) on the grid.

Therefore, the number of paths would be still the same if you delete all the rows and columns with red squares. The new grid has the size $4 \times 7$, resulting in $\binom{11}{4}$ possible paths.