0

How many different combinations there is to get from point $A$ to point $B$ if you have to stop by point $P$ on the way and how many if you want to avoid never to go by $P$?

Im a bit stuck with this. Any help is appreciated.

enter image description here

  • 1
    Presumably you are only ever allowed to go north or east. First count how many ways there are to go from $A$ to $P$. Then count how many ways there are to go from $P$ to $B$. Note in particular how $P$ is not at an intersection but is rather between intersections which only mildly complicates matters. These smaller counting questions can be accomplished using binomial coefficients and then multiplied to give the combined count. – JMoravitz Dec 09 '19 at 17:22
  • If you haven't seen counting paths using binomial coefficients before, as a further hint/push towards a solution., how many sequences of length four can you make using two $E$'s and two $N$'s? Take a moment to understand what this question has to do with your problem and how to count it. – JMoravitz Dec 09 '19 at 17:23
  • Hmm, correct me if im wrong but there's ${5}\choose{2}$ = $10$ ways to go from $A$ to $P$ and ${4}\choose{1}$ = $4$ from $P$ to $B$? –  Dec 09 '19 at 17:50
  • You need two E's and two N's in any order to go from $A$ to the intersection just south of $P$. Once having made it to the intersection immediately south of $P$ you are forced to go north along that road to arrive at $P$. You are forced to continue north to the intersection just immediately north of $P$, from which you need one E and two N's in any order to continue to B. – JMoravitz Dec 09 '19 at 17:56
  • I don't see how to represent that mathematically. –  Dec 09 '19 at 17:59
  • To go from $A$ to the intersection just south of $P$ you need two E's and two N's in any order. The number of available orders of two E's and two N's is $\binom{4}{2}$. We then continue along the half of a road from that intersection to $P$, there are no choices to make here... so if you insist, multiply by $1$, but it doesn't change anything. Then to go from $P$ to $B$ we continue north along the road to the intersection since we have no choice but to do so... again, you can multiply by $1$ if you insist... at which point we have some arrangement of $2$ Ns and $1$ E, in $\binom{3}{1}$ ways – JMoravitz Dec 09 '19 at 18:02

1 Answers1

1

To arrive at $P$ from $A$ you must first travel from $A$ to the intersection just south of $P$. There are $\binom{4}{2}$ ways to arrange two N's (representing going north a full block) and two E's (representing going east a full block) to go from point $A$ to the intersection just south of $P$. From there, we have no option except to travel north a half-block to arrive at $P$.

Once having reached $P$, we continue north along that block to reach the intersection immediately north of $P$ at which point we need an additional $2$ N's and $1$ E to continue to point $B$ which these N's and E can be arranged in $\binom{3}{1}$ different ways.

There are then $\binom{4}{2}\times \binom{3}{1}$ ways to travel from $A$ to $B$ which passes through point $P$.

As for paths from $A$ to $B$ which avoid point $P$, these would be all paths from $A$ to $B$ which aren't among those we just counted.

There are $\binom{8}{3}$ ways to arrange $5$ N's and $3$ E's which represent the number of ways of going from $A$ to $B$ without restriction on whether or not it passes through $P$, and so subtracting the count of paths which do pass through $P$ gives us the count of paths which don't pass through $P$, giving the number of paths from $A$ to $B$ not passing through $P$ as being:

$$\binom{8}{3}-\binom{4}{2}\binom{3}{1}$$

JMoravitz
  • 79,518