0
$\begingroup$

We want to find a formula (not involving $\prod$ or $\sum$) for the number of lattice paths between $(0, 0)$ and $(n, n)$ which are entirely contained in the half-plane $y ≥ x − 2$. For example, for $n = 3$ the number of such lattice paths is 19.

I started by noticing that this contains all of the paths that are contained in the upper half-plane $y ≥ x$ which is simply the Catalan number $C_n$. By rigorously finding the number of lattice paths subject to this condition for a few for $n$, I am fairly confident that the formula is $C_n+C_{n+1}$, but I am unsure how to get this extra term. I've tried using Dyck paths but nothing is coming to me. Any help would be great!

$\endgroup$
1
$\begingroup$

I find it easier to think in terms of paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$ up-steps $\langle 1,1\rangle$ and down-steps $\langle 1,-1\rangle$. In those terms we want the number of paths that do not drop below the line $y=-2$. Consider a ‘bad’ path $\pi$, one that does drop below that line. There is a first point $\langle k,-3\rangle$ at which it does so. Reflect the rest of $\pi$ in the line $y=-3$ to get a path $\pi'$. If the last $n-k$ steps of $\pi$ consist of $r$ up-steps and $s$ down-steps, then $r-s=3$, and $r+s=n-k$. The last $n-k$ steps of $\pi'$ will consist of $s$ up-steps and $r$ down-steps, so $\pi'$ will terminate at $\langle 2n,-6\rangle$, and if $\pi'$ is any path from $\langle 0,0\rangle$ to $\langle 2n,-6\rangle$, we can recover a unique bad path $\pi$ that gives rise to it in this way. A path from the origin to $\langle 2n,-6\rangle$ must have $n-3$ up-steps and $n+3$ down-steps, so there are $\binom{2n}{n-3}$ of them and therefore $\binom{2n}{n-3}$ bad paths. Since there are $\binom{2n}n$ paths altogether, there are

$$\binom{2n}n-\binom{2n}{n-3}$$

paths that never drop below the line $y=-2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.