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?

Question

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?

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.

Answer 1

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$.

Answer 2

Denote the points to be avoided by $1$, $2$, $3$, in the order Left, Top, Bottom.

Number of paths through $1 = \binom{6}{2}\cdot \binom{6}{2}$

Number of paths through $2= \binom{5}{1}\cdot\binom{7}{2}$

Number of paths though $3= \binom{9}{4}\cdot \binom{3}{1}$

Number of paths through $1$ and $3= \binom{6}{2}\cdot \binom{3}{1}\cdot \binom{3}{1}$

Number of paths through $2$ and $3 = \binom{5}{1}\cdot \binom{3}{1}$

Number of paths through $1$ and $2 = 0$.

Now we have to substract from the number of paths from $A$ to $B = \binom{12}{6}$ the first three amounts and add the next three amounts, which gets $366$ ( we use the inclusion-exclusion).

Answer 3

I believe you are meant to always move either to the right or down along the grid. Without that restriction there would be infinitely many paths.

To get from $A$, which is $(0,0)$, to $B$, which is $(6,6)$, you need to take six steps down and six steps to the right. (I'm ignoring the restriction to avoid the three marked points for now.) It is true that there are seven horizontal and seven vertical lines in the figure, as you mention in a comment, but the steps are the segments between vertices, not the vertices themselves, which is why only six steps down are needed instead of seven.

One possible path from $A$ to $B$ is $RRDDRDRRDDDR$. Another is $RDRDRDRDRDRD$. A third is $RRRRRRDDDDDD$. In fact, any "word" consisting of six $R$s and six $D$s corresponds to a path. So the problem is reduced to counting words with six $R$s and six $D$s. Such a word is completely specified by stating where the $R$s are (or alternatively stating where the $D$s are). Any set of six elements chosen from $1,2,3,4,5,6,7,8,9,10,11,12$ is a set of possible $R$ positions. For the first possible path mentioned above, the set of $R$ positions is $\{1,2,5,7,8,12\}$. For the second it is $\{1,3,5,7,9,11\}$, and for the third it is $\{1,2,3,4,5,6\}$. There are $\binom{12}{6}$ ways of forming such a set.

Now that we know how many paths there are from $A$ to $B$, we want to subtract paths that are invalid in that they do pass through one of the marked points. There are, for example, $\binom{5}{4}\binom{7}{2}$ paths that pass through the marked point in the second row. The first binomial coefficient is the number of ways to get from $A$ to the marked point; the second is the number of ways to get from the marked point to $B$.

You can compute the number of paths passing through each of the other two marked points by similar reasoning. You will see, however, that some paths have been subtracted twice, so you will need to add these back. That is, you need to use the principle of inclusion-exclusion. One set of paths that needs to be added back is the set of paths that pass through both $(2,4)$ and $(4,5)$. They were subtracted once because they pass through $(2,4)$, and they were subtracted a second time because the pass through $(4,5)$. The number that needs to be added back to compensate for the double subtraction is $\binom{6}{2}\binom{3}{2}\binom{3}{2}$, which is the number of ways of going from $(0,0)$ to $(2,4)$, then from $(2,4)$ to $(4,5)$, and then from $(4,5)$ to $(6,6)$.

Added: Rob Pratt has given a beautiful solution using a Pascal's-triangle-like recurrence. I think it worth pointing out that Pascal's triangle is a table of binomial coefficients, so the binomial coefficients are still there in the background when you use that method. A formula for the result of applying the recurrence can be obtained by combining a sequence of arrays, each of which is a shifted Pascal's triangle multiplied by one or more binomial coefficients.

If no points are required to be avoided, the relevant portion of Pascal's triangle is $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & 15 & 35 & 70 & 126 & 210\\ 1 & 6 & 21 & 56 & \color{red}{126} & 252 & 462\\ 1 & 7 & 28 & 84 & 210 & 462 & 924 \end{array} $$ where, if rows and columns are both labeled $0$ through $6$, the entry in row $i$, column $j$ is $\binom{i+j}{i}$. To eliminate paths that pass through the marked point in the second-to-last row, we need to subtract the array $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 126 & 126 & 126\\ 0 & 0 & 0 & 0 & 126 & 252 & 378 \end{array} $$ whose row $i$, column $j$ entry is $\binom{5+4}{5}\binom{i-5+j-4}{i-5}=126\binom{i-5+j-4}{i-5}$ for $i\ge5$, $j\ge4$. This leaves $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & \color{red}{15} & 35 & 70 & 126 & 210\\ 1 & 6 & 21 & 56 & 0 & 126 & 336\\ 1 & 7 & 28 & 84 & 84 & 210 & 546 \end{array} $$ Similarly, to eliminate paths that pass through the marked point in Row $4$, Column $2$, subtract the array $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 15 & 15 & 15 & 15 & 15\\ 0 & 0 & 15 & 30 & 45 & 60 & 75\\ 0 & 0 & 15 & 45 & 90 & 150 & 225 \end{array} $$ whose row $i$, column $j$ entry is $\binom{4+2}{4}\binom{i-4+j-2}{i-4}=15\binom{i-4+j-2}{i-4}$ for $i\ge4$, $j\ge2$. This leaves $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & 0 & 20 & 55 & 111 & 195\\ 1 & 6 & 6 & 26 & \color{red}{-45} & 66 & 261\\ 1 & 7 & 13 & 39 & -6 & 60 & 321 \end{array} $$ At this point, paths that pass through both the marked point in Row $5$ and the one in Row $4$ have been subtracted twice, which explains the negative entries. To add these back, add the array $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 45 & 45 & 45\\ 0 & 0 & 0 & 0 & 45 & 90 & 135 \end{array} $$ whose row $i$, column $j$ entry is $\binom{4+2}{4}\binom{1+2}{1}\binom{i-5+j-4}{i-5}=45\binom{i-5+j-4}{i-5}$ for $i\ge5$, $j\ge4$. This leaves $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & \color{red}{5} & 6 & 7\\ 1 & 3 & 6 & 10 & 15 & 21 & 28\\ 1 & 4 & 10 & 20 & 35 & 56 & 84\\ 1 & 5 & 0 & 20 & 55 & 111 & 195\\ 1 & 6 & 6 & 26 & 0 & 111 & 306\\ 1 & 7 & 13 & 39 & 39 & 150 & 456 \end{array} $$ A similar subtraction followed by addition are needed to eliminate paths that pass through the marked point in Row $1$, Column $4$. Subtracting $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 5 & 5 & 5\\ 0 & 0 & 0 & 0 & 5 & 10 & 15\\ 0 & 0 & 0 & 0 & 5 & 15 & 30\\ 0 & 0 & 0 & 0 & 5 & 20 & 50\\ 0 & 0 & 0 & 0 & 5 & 25 & 75\\ 0 & 0 & 0 & 0 & 5 & 30 & 105 \end{array} $$ whose entries are $\binom{1+4}{1}\binom{i-1+j-4}{i-1}=5\binom{i-1+j-4}{i-1}$ for $i\ge1$, $j\ge4$, gives $$ \begin{array}{lllllll} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 3 & 4 & 0 & 1 & 2\\ 1 & 3 & 6 & 10 & 10 & 11 & 13\\ 1 & 4 & 10 & 20 & 30 & 41 & 54\\ 1 & 5 & 0 & 20 & 50 & 91 & 145\\ 1 & 6 & 6 & 26 & \color{red}{-5} & 86 & 231\\ 1 & 7 & 13 & 39 & 34 & 120 & 351 \end{array} $$ To eliminate double subtraction of paths the pass through both $(1,4)$ and $(5,4)$ add $$ \begin{array}{lllllll} 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 5 & 5 & 5\\ 0 & 0 & 0 & 0 & 5 & 10 & 15 \end{array} $$ whose entries are $\binom{1+4}{1}\binom{4+0}{4}\binom{i-5+j-4}{i-5}=5\binom{i-5+j-4}{i-5}$ for $i\ge5$, $j\ge4$. This gives the array in Rob Pratt's answer.

Assembling all these arrays to get a non-recursive formula for the entries in the final array is equivalent to the binomial coefficient method with inclusion-exclusion.