# Shortest paths from A to B in a grid

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?

• Again, what does "shortest" mean? Unless I misunderstand the rules, all the paths from $A$ to $B$ have the same length.
– lulu
Commented Oct 3, 2022 at 11:29
• Are the paths from square to square rather than on the grid lines? Commented Oct 3, 2022 at 11:30
• Well it is said that we can move from cell to cell, so I guess from square to square.
– marc
Commented Oct 3, 2022 at 11:31

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.

• Thanks a lot! Can you just explain me once more why are we substracting 1 in first and second case? And why we don't do that in third case?
– marc
Commented Oct 3, 2022 at 11:46
• @marc $1$ is the number of paths from $(5,1)$ to $(8,4)$ passing through the inaccessible square $(5,4)$. Commented Oct 3, 2022 at 11:48

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.