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

Jun 2017
399
6
Lima, Peru
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 there 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 reasonable method to solve this.
 
Jun 2017
399
6
Lima, Peru
The answer to this question, according to my book, is $365$. However, I have not any idea how the author got to this answer. Can someone explain this please? Help!
 

skeeter

Math Team
Jul 2011
3,355
1,848
Texas
I worked out two grids ... the one on the right has no barriers, the one on the left has the three barriers marked.

Each number at a lattice point is the number of paths from that point to point B.

Note the grid with no barriers has Pascal's Triangle starting at the lower right, which means the total number of paths is \(\displaystyle \binom{12}{6}\)

Only problem is, I came up with 366 paths from A to B on the grid with the barriers. I believe there is a way to do this one with combinations, also ... I just haven't figured it out yet.

grid paths.jpg
 

skeeter

Math Team
Jul 2011
3,355
1,848
Texas
right and down
 
Feb 2010
737
162
I think you need inclusion-exclusion.

$\binom{12}{6}-\binom{6}{2}\binom{6}{2}-\binom{5}{1}\binom{7}{2}-\binom{9}{4}\binom{3}{1}+0+\binom{6}{2}\binom{3}{1}\binom{3}{1}+\binom{5}{1}\binom{3}{1}-0=366$

However I think there is something tricky about the two points in a vertical line. That is, I think the path from A to B through those two points somehow gets double counted which would make the answer 365.
 
Jun 2017
399
6
Lima, Peru
I think you need inclusion-exclusion.

$\binom{12}{6}-\binom{6}{2}\binom{6}{2}-\binom{5}{1}\binom{7}{2}-\binom{9}{4}\binom{3}{1}+0+\binom{6}{2}\binom{3}{1}\binom{3}{1}+\binom{5}{1}\binom{3}{1}-0=366$

However I think there is something tricky about the two points in a vertical line. That is, I think the path from A to B through those two points somehow gets double counted which would make the answer 365.
I've been having a hard time trying to understand binomials. Perhaps can you explain me the inclusion exclusion principle and where do those binomials comes from and why?.

Although I understand how to work with Pascal approach, this thing with binomials is the approach which I would like to learn. So far I recall that binomials do not regard the order and not allow repetitions. Am I right with this?.
 
Jun 2017
399
6
Lima, Peru
Using that rule, there are 366 ways and the book is incorrect.
I also agree that the answer should be $366$ unless the author didn't took into consideration one of the ends, which doesn't make much sense to me.