Solving a counting problem by correcting an estimate

31 Views Asked by At

Note: I know that this question has been asked before, but I am trying to see if I can make my notation a little less cumbersome, and if this approach can be salvaged to any benefit. I'm aware of other solution strategies for this problem.

Consider an $n \times m$ grid of points. We want to find the number of distinct paths between $(0, 0)$ and $(n - 1, m - 1)$ such that we're only moving "up" or to the "right". More precisely, we're interested in counting the number of finite sequences $S_n$ of 2-tuples beginning with $(0, 0)$ and ending with $(n - 1, m - 1)$, for which given $(i, j) \in S_n$, $i < n$ and $j < m$, the next point in the sequence is either $(i + 1, j)$ or $(i, j + 1)$.

The desired sequences are of length $\ell = n + m - 1$.

Visualization showing examples of valid paths

I know about a few different solutions to this problem, but I'm interested in whether my approach can be salvaged. Let $\lvert \omega \rvert$ be the desired number. The approach is to estimate $\lvert \omega \rvert$ with $2^{\ell - 2}$ and add a correction term, since we have two choices for the next point for at most the first $\ell - 2$ points in the sequence. For the remaining points, there is only one possible subsequent points.

The challenge I'm running into is that I'm not sure how to characterize the correction.

My motivation for approaching the problem in this way is that the usual solutions aren't very intuitive for me. I'm used to thinking about these problems as involving a sequence of choices, and overcounting, and either subtracting or dividing out the error, but I can't see a clear way to do that in this case.