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?
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}$