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?

https://projecteuler.net/problem=15

This problem is actually pretty cool – it doesn’t need any programming to solve. Well, maybe a calculator. At first glance, this problem might seem difficult to solve analytically. But it is not so! An important technique in problem solving is reducing problems to sub-problems. Let’s consider the lattice paths of the 1×1 grid.

There are two paths. That was easy! Now, let’s consider the 2×1 grid. One movement to the right reduces the problem to just the 1×1 grid, which we know has two paths to the bottom right corner. There is only one other open route. So for the 2×1 grid, there are 2+1=3 paths. This is also true for the 1×2 grid by way of symmetry. It’s also easy to see that any *n \times 1* or 1 \times n grid will have *n+1* paths.

Using just those pieces of information, let’s look at the 2×2 grid. One movement to the right reduces the problem to the 1×2 grid. One movement down reduces the problem to the 2×1 grid. Both of these sub-grids have 3 paths to the bottom right corner. Therefore, the 2×2 grid has 3+3=6 paths.

The pattern is now clear. Bigger and bigger grids’ solutions can be constructed in a fashion similar to Pascal’s Triangle, by adding together both sub-grids’ number of paths. In the example below, the solution for 4\times4 is 70.

This can be extended all the way to 20×20, but the numbers quickly get unwieldy to add together. Can an analytical solution, rather than a recursive solution, be found? Let’s take a different tack and come at this from a combinatorics angle. A path in the n \times n grid has 2n junctions. A movement down will eventually force a movement to the right, and vice versa. This means that only half of the junctions can be assigned to one movement. The other half of the junctions *has* to be assigned to the other movement.

Taking a route across the grid is actually choosing n junctions, out of 2n junctions, to be assigned to a specific movement. Order of these assignments doesn’t matter. The number of combinations is a binomial coefficient with 2n choose n. Plugging these into the formula for a binomial coefficient results in

\binom{2n}{n}=\frac{(2n)!}{(n!)^2} \tag{1}

Just slap n=20 down in Equation 1 and calculate.

\frac{40!}{20! \times 20!}=137846528820