Problem #15

This one took me a while to figure out. I never actually wrote code for it (I wasnt sure how to do it exactly). But I was able to solve it mathematically using the pascals triangle (well, nCr that makes it up).

       1
     1   1
    1  2  1
   1  3 3  1
  1 4  6  4 1
 1 5 10 10 5 1 
1 6 15 20 15 6 1

If you will notice, for a 1x1 block, there are 2 possible paths, for a 2x2 block, there are 6 possible paths, for a 3x3 block, there are 20 possible paths. if you will see, for an 'n' possible paths, it is the center of the 2n (if the first row is '0', second is '1', etc.). So, paths for n x n = (2n) C (n).

Thus, for a 1x1, it is 2 C 1.

nCr is defined as:

     n!
------------
 r! (n-r)!

where

n! = 1 * 2 * 3 * ... * (n - 2) * (n - 1) * n

So, jumping up, we want the paths for a 20x20 grid:
(2 * 20) C (20)
40 C 20

Typing that into Mathematica (or a calculator) will give the correct answer.