Note (er, rather, rant) :)
Greenestamps was exactly right by his brute force solution. Below is the
formal mathematical combinatorial solution. Brute force methods, especially
computer brute force, have taken a lot of fun out of formal mathematics, as well
as the need for even teaching it. My observations are that the entire
mathematics curriculum from high school up through the undergraduate college
level was designed so that the student would be able to solve differential
equations. But nowadays, the computer can solve all differential equations by
brute force. I predict the day when no mathematics will be taught in schools.
Why do math when you can get the answer by pointing and clicking with a mouse?
--------------------------------------------------------------------------
The figure below has the two omitted lines CD and EF in red.
First we'll find the number of paths for the entire grid including CD and EF.
Then we'll subtract the number of paths that use one or both of CD and EF.
Let N(AB) = the number of paths from A to B each of which is described by a
unique distinguishable permutation of RRRRRRRRRUUUU, 13 moves, 9 units right and
4 units up, of which there are .
To find the number of paths to subtract from the 715, we will need the following
partial paths:
Let N(AC) = the number of paths from A to C each of which is described by a
unique distinguishable permutation of RRU, 3 moves, 2 units right and 1 unit up,
of which there are .
Let N(DB) = the number of paths from D to B each of which is described by a
unique distinguishable permutation of RRRRRRRUU, 9 moves, 7 units right and 2
units up, of which there are .
Let N(AE) = the number of paths from A to E each of which is described by a
unique distinguishable permutation of RRRRRUUU, 8 moves, 5 units right and 3
units up, of which there are .
Let N(FB) = the number of paths from F to B each of which is described by a
unique distinguishable permutation of RRRU, 4 moves, 3 units right and 1 unit
up, of which there are .
Let N(DE) = the number of paths from D to E each of which is described by a
unique distinguishable permutation of RRRU, 4 moves, 3 units right and 1 unit
up, of which there are .
And of course, we need, the number of very short partial paths, of 1 move each.
N(CD) = 1 and N(EF) = 1,
The answer will be
N(AB) - [N(AC)*N(CD)*N(DB) + N(AE)*N(EF)*N(FB)] + [N(AC)*N(CD)*N(DE)*N(EF)*N(FB)]
The middle term counts TWICE the paths through both CD and EF, and thus
subtracts that number twice. This is why we need the third term, to correct by
adding on the number of paths through both CD and EF. Calculating,
715 - [3*1*36 + 56*1*4] + [3*1*4*1*4] = 431.
Edwin