Problem:

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

rrdd rdrd rddr drrd drdr ddrr

Treating the paths as strings, we see that for an NxN grid, these are the permutations of N "d" and N "r" movements.

So there are (2N)! / (N!)^2.

For N = 20, (2N)! is huge; so we should simplify the expression first.

40! / (20! 20!) = ((403938...2221)20!) / (20! 20!)



In [1]:

    
n = 1
d = 1
for i in range(21,41):
    n *= i
    d *= (i - 20)

print n,d,n/d









    



335367096786357081410764800000 2432902008176640000 137846528820



In [ ]: