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 (5,7). However, at (4,3) there is a frog that will eat him if he goes through that point. In how many ways can Marvin reach (5,7)?
+80 Marvin needs to take 5 right moves out of a total of 12, so ignoring the frog there are 12 choose 5 = 792 possible paths to 5,7.
The number of paths from 0,0 to 5,7 passing through 4,3 is the number of paths from 0,0 to 4,3 multiplied by the number from 4,3 to 5,7 , which is 7 choose 3* 5 choose 1 =175. There are thus 792 - 175 = 617 ways that Marvin can reach his destination.
This is the aops explanation.
