Project Euler: Problem 15

Project Euler Problem 15 is reproduced below.

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?

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}<a_{i} \ \underline{\vee} \ b_{i-1}<b_{i}

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}

Advertisements
This entry was posted in math.CO and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s