(5 votes, average: 5.00 out of 5)

## Project Euler Problem 15 Solution

#### 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 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.

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