__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 2*n*+1 row of pascal’s triangle. The formula in general for an *n* x *m* grid is (*n*+*m*)! / (*n*!*m*!). Any combination using *n*Downs(D) and *m*Lefts(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 DDL_{1}L_{2} is the same move as DDL_{2}L_{1}.

__Solution__

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

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

## Discussion

## No comments yet.