Manhattan Lattice Paths with Obstacle Avoidance

Scenario

An agent moves on a 2D integer grid from origin $(0, 0)$ to destination $(m, n)$. Each step must be either one unit Right $(+1, 0)$ or one unit Up $(0, +1)$. A hazardous obstacle is located at coordinate $(x, y)$ where $0 < x < m$ and $0 < y < n$.

Your Task

1. State the total number of unconstrained paths from $(0, 0)$ to $(m, n)$.
2. By applying the multiplication principle of combinatorics, calculate the number of paths that pass directly through the obstacle $(x, y)$.
3. Derive the exact formula for valid paths avoiding the obstacle using the subtraction rule (Inclusion-Exclusion).
4. Compute the valid paths for $m = 5, n = 5$ with an obstacle at $(2, 3)$.

Constraints

• Only Right and Up steps allowed.
• $0 < x < m, 0 < y < n$.

Examples For $m=2, n=2$ avoiding $(1, 1)$: Total paths $\binom{4}{2} = 6$. Paths through $(1, 1) = \binom{2}{1}\binom{2}{1} = 4$. Valid paths = $6 - 4 = 2$.