Project Euler Solution 15: Lattice paths

Here we take a look at Problem 15: Lattice paths as part of the Project Euler series. This problem asks how many paths there are on a 20 × 20 lattice to go from the top-left to the bottom-right when only going right or down.

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

For this one, we don't even need a computer. We can reason about this with combinatorics from high school math.

We have the grid of size $n \times n$. Starting at the top-left corner and going down to the bottom-right with only going right or down means that we take $2 n$ steps. This is easy to see with a path that first only goes right for $n$ steps and then down for another $n$ steps. All other paths are just different orders of these steps. So we always have $n$ steps down and $n$ steps right. The number of possible paths therefore is the number of unique ways that we can permute these $2n$ steps.

For me it helps to let go of that 20 × 20 grid and think of an infinite grid. We start at some point and then move by these rules for 40 steps. Where could we potentially end up? We have 40 steps, and we can choose between down or right at each turn, so there are $2^{2n}$ possible paths. Many paths will bring us to the same location if the number of lefts and downs is the same. We only care for the case where we have 20 lefts and 20 downs, though.

If this was a random process, we would have the same chance of 0.5 to go left or down. We would ask for the probability that in 40 coin tosses we got 20 heads and 20 tails. The answer for this is in the binomial distribution. We would write this as $$ P = \binom{40}{20} 0.5^20 0.5^20 \,. $$ The probabilities are not that interesting, but the binomial coefficient is what we need here. It tells us the number of ways to do 40 binary choices such that we get 20 lefts out of it. That is exactly the number of routes that we have. Evaluating it gives us 137,846,528,820, which is the correct answer.