Shortest paths from A to B in a grid

Question

My task is to count number of different paths from A to B, moving only down or right so that path does not pass through walls on picture below.

So, in both of these walls we have $4$ segments. For the top right one I tried to find all paths that pass through segment $i(i=1,2,3,4)$.

Let $A_i$ be number of paths that pass through segment $i$ for the top wall.

Now, I've found cardinality of those $4$ sets, and got following results: $|A_1|$ = $5 \choose 4$ $9 \choose 4$ $|A_2|$ = $7 \choose 4$ $8 \choose 3$ $|A_3|$ = $8 \choose 5$ $7 \choose 3$ $|A_4|$ = $9\choose 5$ $5 \choose 4$

For the next part, using inclusion exclusion formula, I should find intersection of all combinations of $2,3$ and $4$ sets, but not sure how to do that. For the cardinalities above I first found path from A to starting point of segment, and then from end point of segment to B(without that segment). Any idea how to continue?

Answer 1

Don't use inclusion–exclusion at top-level for this one. Instead observe that the path must follow exactly of three routes,

• Through the $(1,5)$ and $(4,8)$ squares in the southwest. The path from $(1,1)$ to $(1,5)$ and $(4,8)$ to $(8,8)$ are unique; there are $\binom63-1=19$ paths from $(1,5)$ to $(4,8)$, the $-1$ because of the wall protrusion blocking the $(5,4)$ square. Thus there are $19$ paths on this route.
• Through the $(5,1)$ and $(8,4)$ squares in the northeast – also $19$ paths by symmetry.
• Through the $(4,4)$ and $(5,5)$ squares. The number of possibilities for each segment is an unconstrained lattice-paths-in-rectangle problem, so they can be multiplied: $\binom63\binom21\binom63=800$.

Thus there are $800+19+19=838$ admissible paths in all.

Answer 2

Using full inclusion-exclusion for all the segments of the wall seems like a fairly inefficient way to get the result here. As a hint: use the fact that all such paths either go through $(5,1)$ and $(8,4)$, or through $(4,4)$ and $(5,5)$, or through $(1,5)$ and $(4,8)$, and that these possibilities are mutually exclusive. For each possibility the number of paths seems easy to determine.