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?
Solution
This is a basic combinatorics problem. In any path, we'll have to take \(20\) steps down, and \(20\) steps to the right, for a total of \(40\) steps. When we're selecting which of those \(40\) should be downward steps, we have \(40\) choices for the first, \(39\) choices for the second (since we can't pick the same step twice), \(38\) choices for the third, and so on until we have \(21\) choices for the twentieth. Multiplying all these together gives a total of \(\frac{40!}{20!}\) possible choices, where \(n!\) scans as "\(n\) factorial": \(1 \times 2 \times \cdots \times n\). However, we're not quite done yet, because we could have arrived at each path in \(20!\) different ways (by choosing which of the \(20\) specified steps to choose first, which of the remaining \(19\) to choose second, and so forth). Dividing gives us a grand total of \(\frac{40!}{20!20!}\) possible paths through the grid. A number of this form is called a binomial coefficient, and the answer can be written as \(\binom{40}{20}\), pronounced "\(40\) choose \(20\)."
Python Code
from math import comb
p15 = lambda x=20, y=20: comb(x + y, x)