2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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}.} $$

$\endgroup$
2
  • $\begingroup$ @user It takes d steps to reach the first diagonal, 2(k-1)d steps to move between the diagonals k-1 times, then d steps to return to 0, for a total of 2kd. When you reflect this, you get a path which ends at a deviation of +2kd. Such a path will have n+kd up steps and n-kd right steps. $\endgroup$ Commented Mar 16, 2019 at 17:07
  • $\begingroup$ Thank you! Now I got it. $\endgroup$ Commented Mar 16, 2019 at 17:38

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.