Problem 15: Lattice Paths

This problem can be elegantly solved using combinatorics:

To reach the bottom-right corner of an $n \times n$ grid, you must make exactly $2n$ moves: $n$ moves to the right and $n$ moves downward.

Each path can be thought of as a sequence consisting of $n$ R’s (right moves) and $n$ D’s (down moves). For example, for a $2 \times 2$ grid, one possible path is RRDD and another is RDRD.

If you list out all possible orders of the $2n$ moves, there would be $(2n)!$ total ways to arrange them. However, since all the R’s are identical to each other, and all the D’s are identical to each other, we’re overcounting. Swapping two R’s doesn’t create a new path, and neither does swapping two D’s.

To fix this, we divide by $n!$ for the repeated R’s and another $n!$ for the repeated D’s. That gives:

$$\text{Number of paths} = \frac{(2n)!}{n! \, n!}$$

Interestingly, this can be rewritten in terms of the binomial coefficient, which counts how many ways you can choose $b$ items out of $a$.

So we can write the general formula as:

$$\text{Number of paths} = \binom{2n}{n}$$

For a $20 \times 20$ grid, we substitute $n = 20$:

$$\text{Number of paths} = \binom{40}{20} = \frac{40!}{20! \, 20!}$$

In terms of Python:

import math
paths = math.comb(40, 20)
print(paths)
  

Running the above code leads to an answer of $137846528820$