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?
First we translate a problem into a combinatorical problem. We code the moves, a right move is 1, a left move is 0. This way a solution is a combination of n ones and n zeros. We want to place n ones and n zeros in a 2n positions. Once the zeros are placed the ones position are automatically known. So we reduce the problem to how can we choose n items into 2 n position:
$$ \binom {2n} {n}$$
In [8]:
from math import factorial
n = 20
print(int(factorial(2*n)/(factorial(n)*factorial(n))))
This solution is O(1) in both memory and cpu.