I was doing some math problems in my spare time when I saw this:

Suppose you have a m by n grid, and you start at the lower left corner and go to the upper right corner by moving only up and right. Suppose that m = 30; n = 40 and you cannot travel through the intersections (4,5) and (22,27). How many possible paths are there?

When I started this, I came across this question and I figured that the way to do this would be to take the paths going to (30,40), and then subtracting the paths from: (0,0) to (4,5), (4,5) to (30,40), (0,0) to (22,27), (22,27) to (30,40).

Is this the correct way to approach this problem? Is there a better or more "elegant" way?

  • 2
    $\begingroup$ You are miscomputing the bad paths. To get the number of bad paths that pass through $P$ you must multiply the paths from $(0,0)$ to $P$ by the paths from $P$ to $(30,40)$. Also, you have to add back the paths that go through both bad points as your method subtracts those twice. $\endgroup$ – lulu Mar 29 '18 at 3:33
  • $\begingroup$ I don't understand what you are trying to say @lulu - why would I multiply and what would I "add back"? $\endgroup$ – Jack Goldfarb Mar 29 '18 at 3:50

As you already know

No.of such paths are given by $\binom{m+n}{n}$ =$\binom{30+40}{40}$

A: No. of paths that pass through (4,5) = paths from ((0,0)to (4,5))* path from (4,5) to (30,40) = $\binom{4+5}{4}$ $\binom{26+35}{35}$

B : No. of paths that pass through (22,27) = paths from ((0,0)to (22,27))* path from (22,27) to (30,40) = $\binom{22+27}{27}$ $\binom{8+13}{13}$

$A\cap B$ : no of paths that pass through (4,5) and (22,27) = (0,0)to(4,5)|(4,5)to(22,27)|(22,27)to(30,40) = $\binom{4+5}{5}\binom{18+22}{22}\binom{8+13}{13}$

No of path that do not pass through (4,5) and (22,27)= $\binom{30+40}{40}$ - $\binom{4+5}{4}$ $\binom{26+35}{35}$ -$\binom{22+27}{27}$ $\binom{8+13}{13}$+ $\binom{4+5}{5}\binom{18+22}{22}\binom{8+13}{13}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.