Question 1196699
.
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).



<pre>
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  {{{C[12]^5}}} = {{{(12*11*10*9*8)/(1*2*3*4*5)}}} = 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  {{{C[4+4]^4}}} = {{{C[8]^4}}} = 70;

    - and the other path is from (4,4) to (5,7); the number of such paths is  {{{C[(5-4)+(7-4)]^1}}} = {{{C[4]^1}}} = 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.    <U>ANSWER</U>
</pre>

Solved.