## Project Euler: Problem 15

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 $N\times N$ planar integer grid

$\displaystyle\left\{(a,b)\in\mathbb{Z}^{2}: 0\leq a,b\leq N\right\}$

We want to find all the “routes” from the point $(0,N)$ to the point $(0,N)$ that only involve moving down or moving to the right. By route, I mean a finite sequence of grid points$(a_{1},b_{1}),\ldots,(a_{2N},b_{2N})$ such that $(a_{2N},b_{2N})=(N,0)$ and

$\displaystyle a_{i-1}

Implicitly, we define $(a_{0},b_{0})=(0,N)$. To each route, we can associate a unique string of length $2N$ consisting of the letters $D$, for down, and $R$, for right. For example, the route in the upper-left image above can be represented as $RRDD$. Note that any string describing a route has $N$ $R$‘s and $N$ $D$‘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 $2N$ with $N$ $R$‘s and $N$ $D$‘s. Note that the fixed length constraint implies that we only need to know the location of the $R$‘s.

This counting problem is one you and I have seen many times before: how many ways to select $k$ objects from $n$ objects, where order doesn’t matter. In our case, it’s how many ways to select $N$ locations to place the $R$‘s out of $2N$ possible locations. The answer is given by the binomial coefficient

$\displaystyle{{2N}\choose N}=\dfrac{(2N)\cdots(N+2)(N+1)}{N!}$

If $N=20$, then the answer is

$\displaystyle{40\choose 20}=\dfrac{40\cdot39\cdot38\cdots22\cdot21}{20!}=137846528820$

Another way to approach this problem is by considering ordered integer partitions. An ordered integer partition of a natural number $n$ is a $m$-tuple $(i_{1},\ldots,i_{m})$ such that

$\displaystyle i_{1},\ldots,i_{m}\geq0\text{ and }i_{1}+\cdots+i_{m}=n$

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 $N$ points to the right. Starting at the top, the grid has $N+1$ rows. Denote the number of points we move to the right on the $k^{th}$ row by $i_{k}$. Then $i_{k}\geq0$ and

$\displaystyle i_{1}+\cdots+i_{N+1}=N$

Our problem is now to count the number of such integer partitions, which we will do using generating functions. Consider the geometric series $\displaystyle\sum_{k=0}^{\infty}z^{k}$, which can represented as

$\displaystyle\dfrac{1}{1-z}=\sum_{j=0}^{\infty}z^{j},\indent\forall\left|z\right|<1$

If we take the cauchy product of two power series $\sum a_{i}z^{i}$ and $\sum b_{j}z^{j}$, we obtain a power series $\sum c_{n}z^{n}$ whose coefficients $c_{n}$ are given by

$\displaystyle c_{n}=\sum_{i+j=n}a_{i}b_{j}$

If $a_{i}=b_{i}=1$, then $c_{n}$ gives the number of nonnegative integer $2$-vectors whose coordinates sum to $n$. If we take the Cauchy product of $k$ power series $\sum a_{i}^{(1)}z^{i},\ldots,\sum a_{i}^{(k)}z^{i}$, then the coefficients of the resulting power series are

$\displaystyle c_{n}=\sum_{i_{1}+\cdots+i_{k}=n}a_{i_{1}}^{(1)}\cdots a_{i_{k}}^{(k)}z^{n}$

If $a_{i}^{(1)}=\cdots=a_{i}^{(k)}=1$, then $c_{n}$ gives the number of nonnegative integer $k$-vectors whose coordinates sum to $n$. Since the cauchy product corresponds to multiplying absolutely convergent power series together, we can write

$\displaystyle\left(1-z\right)^{-k}=\sum_{n=0}^{\infty}c_{n}z^{n},\indent\forall\left|z\right|<1$

Hence, we can compute the $n^{th}$ coefficient $c_{n}$ by taking the derivative of the $n^{th}$ derivative of the LHS, evaluating at $z=0$, and dividing by $n!$. Indeed,

$\displaystyle\dfrac{(k+n-1)!}{(k-1)!}=\dfrac{d^{n}}{dz^{n}}\left(1-z\right)^{-k}\vert_{z=0}=n!c_{n}\Longrightarrow c_{n}={{k+n-1}\choose {k-1}}$

Using this result, we see that the number of routes on an $N\times N$ grid is

$\displaystyle{{(N+1)+N-1}\choose{(N+1)-1}}={{2N}\choose N}$