Last November I have solved Problem 15 of Project Euler (a counting problem involving paths in square grids), and, although the problem admits a simple solution, some of the solutions presented in their forums are very complicated. Thus, I thought it would be a good idea to present my solution, as I consider it very simple.
Problem statement
Starting in the top left corner of a $2{\times}2$ grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a $20{\times}20$ grid?
My solution
In order to make the problem more interesting, let us investigate the more general problem of counting the number of routes in an $n{\times}n$ grid. Our argument is based on three observations:
- all the paths have size $2{\times}n$ (the reason is obvious: you have to go right $n$ positions and down another $n$ positions);
- since we can only go right or down, we can identify every path by a string of Rs and Ds, where a R means going right and a D means going down; as an example, the paths illustrated in the problem statement are (from left to right and from top to bottom): RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
- the strings mentioned above must contain the same number of Rs and Ds.
From these three observations, we can transform the problem to the following:
How many different strings of size $2{\times}n$, consisting of $n$ Rs and n Ds, are there?
The solution is now very simple, because the positioning of $n$ Ds (or Rs) determines the positioning of the other $n$ Rs (or Ds). Hence, the number we are interested in is the number of ways in which we can choose $n$ positions from $2{\times}n$ available positions. The answer, using the traditional notation for the binomial coefficient, is:
\[
{2n \choose n} = \frac{(2n)!}{n! \times n!}~~~~.
\]
Instantiating n with 20, we get the answer to the initial problem of the $20{\times}20$ grid.
Generalization to $m{\times}n$ grids
The generalization to an $m{\times}n$ grid is also simple. The only difference is that the strings have length $m+n$. Using the same reasoning as above, the number of paths through an ${m{\times}n}$ grid is:
\[
{m+n \choose n} = \frac{(m+n)!}{m!\times n!}~~~~.
\]
Final note: If you want to access the forum of the problem, you have to solve it.