February 15, 2025

Grid Path Problems in Combinatorics

Problem 1

Consider an $m \times n$ grid where you can only move right or down. There is an obstacle at $(a, b)$. Find the number of ways to reach the bottom-right corner from the top-left corner while avoiding the obstacle.

Solution

1. Compute the number of paths ignoring the obstacle: $\binom{m+n}{m} = \frac{(m+n)!}{m! n!}$

2. Compute the number of paths reaching $(a, b)$: $\binom{a+b}{a}$

3. Compute the number of paths from $(a, b)$ to $(m, n)$: $\binom{(m-a)+(n-b)}{m-a}$

4. By removing the paths that pass through the obstacle, the final count is:

   $$\binom{m+n}{m} - \left(\binom{a+b}{a} \times \binom{(m-a)+(n-b)}{m-a} \right)$$

Problem 2

Consider an $n \times n$ grid where you can only move right or up. However, you are not allowed to step on any point $(i, j)$ where either $i$ or $j$ is odd. Find the total number of ways to reach the top-right corner from the bottom-left corner.

Solution

Since movement is restricted, we can only step on coordinates where both $i$ and $j$ are even. Effectively, the grid reduces to an $\frac{n}{2} \times \frac{n}{2}$ grid where each move corresponds to a move in the smaller grid.

In the reduced grid, we must make exactly $\frac{n}{2}$ right moves and $\frac{n}{2}$ up moves to reach the top-right corner. The number of such paths is given by the binomial coefficient:

which represents the number of ways to choose $n/2$ right moves out of $n$ total moves.