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!
Best Answer
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$.