Suppose you have an $n \times m$ matrix where each element of the matrix represents some physical position. A person starts in the top left of the matrix and wants to reach the bottom right of the matrix. This person can only move right or down. What is the number of paths that reach the bottom right corner? What is the number of paths that reach any given cell?
I know that there's a combinatorics solution to the first question. The number of paths that reach the bottom right corner is $C(n + m – 2, m – 1)$. There's also a recursive solution that we can use to find the number of paths that reach the bottom right corner:
Suppose that $g_{ij}$ represents the ___________________. Then we have the recurrence $g_{ij} = g_{i-1,j} + g_{i,j-1}$ for the interior cells and $g_{ij} = 0 = 1$ when $i = 0$ or $j = 0$.
Oddly, I don't actually know what the _____________ should be here, but this recurrence gives $g_{nm}$ = number of paths from the top left to bottom right corner. At first I thought $g_{ij}$, in general, was the number of paths that go through cell $(i,j)$, but that's not correct because the number of paths that go through cell (0,0) is the same as the number of paths that go through (n,m). So what does $g_{ij}$ actually mean physically?
I think this naturally leads to my next question. Except for $g_{nm}$, $g_{ij}$ doesn't tell us the number of paths that go through (i,j). So how do we actually compute the number of paths that go through some (i,j)?
Best Answer
$g_{i,j}$ is the number of paths that go to $(i,j)$. That is, $g_{i,j}$ is the number of paths that start at $(0,0)$ and stop at $(i,j)$. To get the number of paths that go from the top corner to the bottom corner through $(i,j)$, you need to multiply the number of paths from $(0,0)$ to $(i,j)$ by the number of paths from $(i,j)$ to the bottom corner.
So the answer is
$$g_{i,j}g_{(n-i),(m-j)} = {i+j-2\choose j-1}{n+m-i-j-2\choose m-j-1}$$