Marvin the fly starts at (0,0). Each step, Marvin moves one unit right or one unit up. He is trying to get to the point . However, at there is a frog that will eat him if he goes through that point. In how many ways can Marvin reach ?
+195 Let's call the position of the frog (a,b). To get from (0,0) to (n,m) without going through the frog, Marvin must take exactly n steps to the right and m steps up, for a total of n+m steps. Furthermore, he must choose which n of these steps will be the steps to the right (and the other m steps will be up).
Therefore, the number of ways for Marvin to get from (0,0) to (n,m) without going through the frog is the number of ways to choose n steps out of n+m total steps. This is given by the binomial coefficient:
(n+m choose n) = (n+m choose m)
Now, we need to subtract the number of ways that Marvin can get from (0,0) to (a,b) and then from (a,b) to (n,m), because these are the cases where he goes through the frog. To get from (0,0) to (a,b), Marvin must take exactly a steps to the right and b steps up, and he must choose which a of these steps will be to the right. Therefore, there are (a+b choose a) ways for Marvin to get from (0,0) to (a,b) without going through the frog.
Similarly, to get from (a,b) to (n,m), Marvin must take exactly n-a steps to the right and m-b steps up, and he must choose which n-a of these steps will be to the right. Therefore, there are (n+m-a-b choose n-a) ways for Marvin to get from (a,b) to (n,m) without going through the frog.
Therefore, the total number of ways for Marvin to get from (0,0) to (n,m) without going through the frog is:
(n+m choose n) - (a+b choose a) x (n+m-a-b choose n-a)
Substituting the values given in the problem, we get:
(5 choose 4) - (2 choose 1) x (6-2-3 choose 4-2)
= 5 - 2 x (1 choose 2)
= 5 - 0
= 5
Therefore, there are 5 ways for Marvin to get from (0,0) to (5,3) without going through the frog.
