Problem Description

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?

Analysis

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 nDs and mLs 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 DDL₁L₂ is the same move as DDL₂L₁.

Solution

Runs < 1 second in Python.

f = lambda n:[1,0][n>0] or f(n-1)*n
n = 20
m = 20
 
print "Answer to PE15 = ", f(n+m) / ( f(n)*f(m) )

Comments

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)!