I'm working on a research project and I came across this problem. I was curious if there is a strategy to count the number of paths from A to B, using free nodes while avoiding the blocked nodes.
The starting point is always the bottom left-hand side corner, and the endpoint is always the top right-hand side corner. We can only move up or to the right.
Blocked nodes always appear on the top left-hand side corner of the grid. There is no free node on the left-hand side, or above any forbidden node.
I can find the answer using search algorithms, but that's not efficient, especially, with large scale problems. I was curious if there is a better mathematical expression/strategy for this problem. Thank you!
This is an example:
Best Answer
One way to do this is by inclusion–exclusion.
It’s enough to exclude the bottom forbidden node in each column. In your example, these are the nodes $(0,2)$, $(1,2)$, $(2,4)$ and $(3,5)$. Denote the set of these nodes by $N$ and the number of paths that use all nodes in a set $S$ by $a_S$. Then by inclusion–exclusion the number of admissible paths is
$$ \sum_{S\subseteq N}(-1)^{|S|}a_S\;. $$
There are $\binom{x_2-x_1+y_2-y_1}{x_2-x_1}$ paths from $(x_1,y_1)$ to $(x_2,y_2)$. By inserting the forbidden nodes as intermediate steps, we can write the above sum as
$$ \sum_{S\subseteq N}(-1)^{|S|}\prod_{i=0}^{|S|}\binom{y_{s_{i+1}}-y_{s_i}+x_{s_{i+1}}-x_{s_i}}{x_{s_{i+1}}-x_{s_i}}\;, $$
where $s_1,\ldots,s_{|S|}$ are the nodes in $S$ in order of ascending $x$ coordinates, and $s_0=A$ and $s_{|S|+1}=B$.
In your example, this is
$$ \binom{10}5-\binom20\binom85-\binom31\binom74-\binom62\binom43-\binom83\binom22+\binom20\binom11\binom74+\binom20\binom42\binom43+\binom20\binom63\binom22+\binom31\binom31\binom43+\binom31\binom52\binom22+\binom62\binom21\binom22-\binom20\binom11\binom31\binom43-\binom20\binom11\binom52\binom22-\binom20\binom42\binom21\binom22-\binom31\binom31\binom21\binom22+\binom20\binom11\binom31\binom21\binom22 \\[15pt] =104\;. $$