Lattice Paths¶
Let $f(m, n)$ equal the number of routes in an $m \times n$ grid. Intuitively, if you start at the top left corner, you immediately have two choices - you can go down or right. If you go down, there are $f(m-1,n)$ routes in the $(m - 1) \times n$ subgrid; if you go right, there are $f(m,n-1)$ routes in the $m \times (n-1)$ subgrid. Therefore $$f(m,n) = f(m-1,n) + f(m,n-1)$$
There are two trivial base cases: $f(m,0) = 1$ for any $m$ and $f(0,n) = 1$ for any $n$. From these facts, you can write a simple memoized recursive function to solve this problem.
from functools import cache
@cache
def f(m, n):
if m == 0:
return 1
if n == 0:
return 1
return f(m - 1, n) + f(m, n - 1)
Then the answer is given by
f(20,20)
137846528820
However, we can do better and give a non-recursive formula for $f$. It turns out, for an $m \times n$ grid, there are $\binom{m+n}{m}$ possible routes. Here's an outline of how you can prove this inductively:
- Prove $f(m, 0) = \binom{m+0}{m} = 1$ for all $m$
- Prove $f(0, 0) = \binom{0 + 0}{0} = 1$
- Assuming $f(j, 0) = \binom{j+0}{j} = 1$ for some $j$, prove $f(j+1,0) = \binom{j+1+0}{j+1} = 1$
- Assuming there exists some $k$ such that for all $m$, $f(m, k) = \binom{m + k}{m}$, prove $f(m, k+1) = \binom{m + k + 1}{m}$ for all $m$
- Prove $f(0, k+1) = \binom{0+k+1}{0} = 1$
- Assuming $f(j, k+1) = \binom{j+k+1}{j}$ for some $j$, prove $f(j+1,k+1) = \binom{j+k+2}{j+1}$
Note that there are three inductive proofs here - an overall induction on $m$ and nested inductions in both the base case and the induction step (yo dawg, I heard you like induction...).
One useful identity for proving this, particularly in step 2, comes from Pascal's triangle: $$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
Relevant sequences¶
Copyright (C) 2025 filifa¶
This work is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license and the BSD Zero Clause license.