Does it exist a way how to find the ways to get from one point to another when certain points must be avoided in a grid

combinatoricspuzzlerecreational-mathematics

The problem is as follows:

The diagram from below shows a grid of $6\times 6$. How many different ways can you get from $A$ to $B$ without going through any of the highlighted points?

Sketch of the problem

The alternatives given are as follows:

$\begin{array}{ll}
1.&\textrm{265 ways}\\
2.&\textrm{365 ways}\\
3.&\textrm{395 ways}\\
4.&\textrm{405 ways}\\
\end{array}$

Does it exist a way to simplify this problem?. How exactly can I find the method to solve this?. There isn't any indication of which sort of path should be taken. Hence there could be tons of ways and I'm stuck on it. Can someone help me here?.

It would help a lot to me to include some sort of diagram or drawing to justify a resonable method to solve this.

Best Answer

I'm assuming the paths must go right and down only.

You can count the paths by using the inclusion-exclusion principle. Without considering the points that must be avoided, there are $\binom{6+6}{6}$ paths. Now subtract the $\binom{4+1}{1}\binom{2+5}{5}$ paths that visit the first bad point, the $\binom{2+4}{4}\binom{4+2}{2}$ paths that visit the second bad point, and the $\binom{4+5}{5}\binom{2+1}{1}$ paths that visit the third bad point. Then add back in the paths that visit two bad points. No paths visit all three bad points.

\begin{align} &\binom{12}{6} -\left(\binom{5}{1}\binom{7}{5} +\binom{6}{4}\binom{6}{2}+\binom{9}{5}\binom{3}{1}\right) +\left(\binom{5}{1}\binom{4}{4}\binom{3}{1}+\binom{6}{4}\binom{3}{1}\binom{3}{1}\right)\\ &=924-(5\cdot 21+15\cdot 15+ 126\cdot 3)+(5\cdot 1\cdot 3+15\cdot 3\cdot 3)\\ &=924-(105+225+378)+(15+105)\\ &=924-708+120\\ &= {\color{red}{366}} \end{align}


Here's an alternative solution that uses a Pascal-type recursion. Let $p(i,j)$ be the number of good paths that start from $A=(0,0)$ and reach point $(i,j)$. We want to compute $p(6,6)$. By conditioning on the last step into $(i,j)$, we find that $p(i,j)$ satisfies the following recursion: $$ p(i,j)= \begin{cases} 0 &\text{if $(i,j)$ is a bad point}\\ 1 &\text{if $i=0$ or $j=0$}\\ p(i-1,j)+p(i,j-1) &\text{otherwise} \end{cases} $$ The resulting values of $p(i,j)$ are: \begin{matrix} i\backslash j &0 &1 &2 &3 &4 &5 &6 \\ 0 &1 &1 &1 &1 &1 &1 &1 \\ 1 &1 &2 &3 &4 &0 &1 &2 \\ 2 &1 &3 &6 &10 &10 &11 &13 \\ 3 &1 &4 &10 &20 &30 &41 &54 \\ 4 &1 &5 &0 &20 &50 &91 &145 \\ 5 &1 &6 &6 &26 &0 &91 &236 \\ 6 &1 &7 &13 &39 &39 &130 &{\color{red}{366}} \end{matrix} So $p(6,6)=366$.

Related Question