// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 5.00 out of 5)
Loading ... Loading ...

Project Euler Solutions

Project Euler 15

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

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.

Post a comment