.
Marvin the fly starts at (0,0). For each step, Marvin moves one unit right or one unit up.
He is trying to get to the point (5,7). However, at (4,4) there is a frog that will eat him
if he goes through that point. In how many ways can Marvin reach (5,7)?
~~~~~~~~~~~~~~
The idea of the solution is to calculate the number of all existing different paths
from (0,0) to (5,7), and then SUBTRACT from it the number of all such different paths
from (0,0) to (5,7), that go through point (4,4).
Each path from (0,0) to (5,7) on this grid can be presented as the word consisting of
5+7 = 12 letters R and U; each such letter represents one move one init Right or one
unit Up, respectively.
So, the number of all possible paths from (0,0) to (5,7) is = = 792.
Next, the paths from (0,0) to (5,7) that go through point (4,4) are combinations /compositions of these partial paths:
- one from (0,0) to (4,4); the number of such paths is = = 70;
- and the other path is from (4,4) to (5,7); the number of such paths is = = 4.
The number of such special paths is the product 70*4 = 280.
Doing in accordance with the general idea, we should SUBTRACT 280 from 792, and we get the answer
the number of the sought paths is 792 - 280 = 512. ANSWER
Solved.