A Square Grid Path Problem

Last November I 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×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:

1. all the paths have size $2\times n$ (the reason is obvious: you have to go right $n$ positions and down another $n$ positions);

2. since we can only go right or down, we can identify every path by a string of Rs and Ds, where an 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;

3. 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:

$$(\genfrac{}{}{0ex}{}{2n}{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:

$$(\genfrac{}{}{0ex}{}{m+n}{n})=\frac{(m+n)!}{m!\times n!}.$$

Final note: If you want to access the forum of the problem, you have to solve it.