Project Euler Problem 15 is reproduced below.
Starting in the top left corner of a 22 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 2020 grid?
This problem doesn’t really require any programming. A bit of combinatorial thinking is all that’s needed to obtain an elegant solution.
Let’s begin by generalizing the problem an planar integer grid
We want to find all the “routes” from the point to the point that only involve moving down or moving to the right. By route, I mean a finite sequence of grid points such that and
Implicitly, we define . To each route, we can associate a unique string of length consisting of the letters , for down, and , for right. For example, the route in the upper-left image above can be represented as . Note that any string describing a route has ‘s and ‘s. Conversely, any such string describes a route, so the correspondence between routes and strings is bijective. Our problem is now reduced to counting the number of strings of length with ‘s and ‘s. Note that the fixed length constraint implies that we only need to know the location of the ‘s.
This counting problem is one you and I have seen many times before: how many ways to select objects from objects, where order doesn’t matter. In our case, it’s how many ways to select locations to place the ‘s out of possible locations. The answer is given by the binomial coefficient
If , then the answer is
Another way to approach this problem is by considering ordered integer partitions. An ordered integer partition of a natural number is a -tuple such that
So, what’s the connection to the problem described above? Well, we can describe each route by how many points we move to the right on each row of the grid. The only constraint is that we have to move points to the right. Starting at the top, the grid has rows. Denote the number of points we move to the right on the row by . Then and
Our problem is now to count the number of such integer partitions, which we will do using generating functions. Consider the geometric series , which can represented as
If we take the cauchy product of two power series and , we obtain a power series whose coefficients are given by
If , then gives the number of nonnegative integer -vectors whose coordinates sum to . If we take the Cauchy product of power series , then the coefficients of the resulting power series are
If , then gives the number of nonnegative integer -vectors whose coordinates sum to . Since the cauchy product corresponds to multiplying absolutely convergent power series together, we can write
Hence, we can compute the coefficient by taking the derivative of the derivative of the LHS, evaluating at , and dividing by . Indeed,
Using this result, we see that the number of routes on an grid is