Project Euler Problem 15

Lattice Paths

Starting in the top left corner of a $2 \times 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 \times 20$ grid?

This is a pretty classic combinatorics problem. To travel from the top-left corner to the bottom-right corner of an $n \times m$ grid, we need to make exactly $n$ moves to the right and $m$ moves down for a total of $n + m$ moves. The order of these moves doesn't matter, but there are many choices.

Arranging $n$ right moves and $m$ down moves is equivalent to choosing which $n$ of the $n + m$ moves will be right moves (or which $m$ will be down moves). This is given by the binomial coefficient

\binom{n+m}{n} = \binom{n+m}{m} = \frac{(n+m)!}{n! m!}

For the $20 \times 20$ grid we get $\binom{40}{20}$. So we don't really need to write any code but in Julia this looks like

function count_lattice_paths(n, m)
    return binomial(n+m, n)
end

which computes the answer in 1.041 ns.