Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20×20 grid?
This question has been posed as: “Starting at the top left corner, how many ways through town are possible using only one-way streets and ending at the bottom right corner of a n x n grid?”
The solution is the central binomial coefficient or the center number in the 2n+1 row of pascal’s triangle. The formula in general for an n x m grid is (n+m)! / (n!m!). Any combination using nDowns(D) and mLefts(L) would be a valid move.
In the example provided in the problem description there would be (2+2)! or 24 possible moves, but many would be indistinguishable, and we would have to divide by (2! · 2!) to eliminate them. So, (2 + 2)! / (2! · 2!) = 24 / 4 = 6. Namely, LLDD, LDLD, LDDL, DLLD, DLDL and DDLL. By indistinguishable we mean DDL1L2 is the same move as DDL2L1.
Runs < 1 second in Python.
from Euler import factorial, binomial n, m = 20, 20 # method 1, m==n, middle number in row 2*n of Pascal's triangle print "Answer to PE15 = ", binomial(2*n, n) # method 2, m!=n print "Answer to PE15 = ", factorial(n+m) / (factorial(n)*factorial(m))
- The OEIS for this series is A000984
- If we added the condition “which do not pass below the diagonal” to our problem statement, we would use a Catalan number. It is calculated as 2n! / n! / (n+1)!