The number of monotone lattice paths in the vicinity of the diagonal.

Inspired by a discussion, I would like to pose the following problem. What is the number of monotone lattice paths from $(0,0)$ to $(n,n)$ which do not deviate from the diagonal more than by $d$ steps.

As was shown in the cited answer the problem can be easily solved for the case $d>n/2$ by the reflection principle. Can this method be somehow adapted to the case where a path can cross both "forbidden" diagonals?


I will count the lattice paths who never deviate by $d$ or more steps. The deviation of a path at a point is its $y$-coordinate minus its $x$-coordinate at that point.

  1. Start with all of the paths, $\binom{2n}{n}$

  2. Subtract the bad paths which at some point deviate by $\pm d$, which by the reflection principle is $2\binom{2n}{n-d}$.

  3. Add back in the doubly subtracted paths which at some point have a deviation of $+d$, and at another point have a deviation of $-d$. Applying the reflection principle twice, the number of such paths is $2\binom{2n}{n-2d}$. For example, let's count paths which at some point deviate by $+d$, then at a later point deviate by $-d$. You reflect at the first time they deviate by $-d$, and then reflect at the first time they deviate by $+d$. The result is a path of length $2n$ who at the end deviates by $+4d$. This path has $n+2d$ up steps and $n-2d $ right steps.

  4. Now, paths which go from $+d$ to $-d$ back to $+d$ will be doubly subtracted in step $2$, then doubly added back in in step $3$. These must be subtracted out. Same for $-d\to +d\to -d$, so we subtract $2\binom{2n}{n-3d}$ (where we reflect three times to get this).

  5. However, paths which go from $+d$ to $-d$ to $+d$ to $-d$ were subtracted twice in $2$, added twice in $3$, then subtracted twice in $4$. These must be added back in, so $\dots$

You see the pattern. The result is $$ \boxed{\binom{2n}n+2\sum_{k=1}^{\lfloor n/d\rfloor}(-1)^k\binom{2n}{n-kd}.} $$