3
$\begingroup$

Suppose that $z \in \mathbb{Z}^+, n > z$. How many lattice paths are there from $(0, 0)$ to $(n, n)$ that do not go above the line $y = x + z$?

This problem seems very similar to the usual Dyck path problem where we need to figure out the number of lattice paths that do not go over $y = x$. However, I can't seem to figure out the logic that would go behind finding the paths that don't cross an abstract linear transformation of the diagonal by the factor $z$.

Here's what I have done so far:

I know that there are $\binom{2n}{n}$ total lattice paths in total from: $(0, 0)$ to $(n, n)$. I figured out a formula that would work well is total paths - bad paths. I have tried using André's reflection method which is also used to calculate the variants of this kind of problem but it was to no avail.

Any help to find a bijection that represents the number of bad paths would be appreciated. I think the final solution after subtracting the bad paths should be: $$\binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1}\binom{2n}{n}$$

Please let me know if I am wrong.

$\endgroup$
2
  • 1
    $\begingroup$ You may also be interested in the article Lattice Path Enumeration by C. Krattenthaler, which handles linear boundaries of slope $1$ in Section $10.3$. $\endgroup$
    – joriki
    May 24 '20 at 18:37
  • $\begingroup$ I'll have a look, thanks :) $\endgroup$ May 24 '20 at 18:39
4
$\begingroup$

I find it a bit easier to think in terms of paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$ that consist of $n$ up-steps (steps from $\langle k,\ell\rangle$ to $\langle k+1,\ell+1\rangle$) and $n$ down-steps (steps from $\langle k,\ell\rangle$ to $\langle k+1,\ell-1\rangle$). An up-step in this version corresponds to a step to the right in your version, and a down-step corresponds to a step upwards in your version. Your boundary condition becomes a requirement that my path not drop below the line $y=-z$.

We can use a slight modification of one of the usual arguments for counting the paths that don’t drop below the line $y=0$.

As in your version, there are altogether $\binom{2n}n$ paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$, and the problem is to count the ‘bad’ ones, i.e., the ones that do drop below the line $y=-z$. Suppose that we have a bad path $\pi$. There is a first point at which $\pi$ reaches the line $y=-z-1$; if it has made $u$ up-steps at that point, it must have made $u+z+1$ down-steps and so have reached the point $\langle 2u+z+1,-z-1\rangle$. Reflect the remainder of $\pi$ (i.e., the part to the right of this point) in the line $y=-z-1$. That part of $\pi$ has $n-u$ up-steps and $n-u-z-1$ down-steps, so its reflection has $n-u$ down-steps and $n-u-z-1$ up-steps. This means that it must end at the point

$$\langle 2u+z+1,-z-1\rangle+\langle2n-2u-z-1,-z-1\rangle=\langle 2n,-2z-2\rangle\;.$$

Conversely, any path from $\langle 0,0\rangle$ to $\langle 2n,-2z-2\rangle$ must hit the line $y=-z-1$, and if we reflect the part of it to the right of that intersection in the line $y=-z-1$, we get a path from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$ that drops below the line $y=-z$. Thus, we have a bijection between our bad paths and all paths from $\langle 0,0\rangle$ to $\langle 2n,-2z-2\rangle$. Each of these paths has $n-z-1$ up-steps and $n+z+1$ down-steps, so there are $\binom{2n}{n+z+1}$ of them. Thus, there are

$$\binom{2n}n-\binom{2n}{n+z+1}=\binom{2n}n-\binom{2n}{n-z-1}$$

good paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$.

$\endgroup$
4
  • 2
    $\begingroup$ Funny that we both started our answers by saying what we find easier to think about :-) $\endgroup$
    – joriki
    May 24 '20 at 18:20
  • 2
    $\begingroup$ @joriki: And not even the same thing! :-) $\endgroup$ May 24 '20 at 18:22
  • 1
    $\begingroup$ I appreciate the detailed solutions. @joriki solution just fit a bit better in my brain lol. $\endgroup$ May 24 '20 at 18:28
  • 2
    $\begingroup$ @PL: That’s fine; multiple good solutions may help someone else later on. $\endgroup$ May 24 '20 at 18:30
2
$\begingroup$

You can indeed use the reflection method. I find the reflection method slightly easier to understand if we talk about “touching” instead of “going above”. Not going above the diagonal $y=x$ is equivalent to not touching $y=x+1$, and this is the line in which we reflect the bad paths that do touch it. This maps $(0,0)$ to $(-1,1)$, which leads to the count of $\binom{(n-(-1))+(n-1)}{n-(-1)}=\binom{2n}{n+1}$ of bad paths.

Analogously, not going above $y=x+z$ is equivalent to not touching $y=x+z+1$, so this is the line in which we need to reflect the bad paths that touch it. This maps $(0,0)$ to $(-z-1,z+1)$, so the number of bad paths is

$$ \binom{n-(-z-1)+(n-(z+1))}{n-(-z-1)}=\binom{2n}{n+z+1}\;. $$

As a check, note that this is $\binom{2n}{n+1}$ for $z=0$ and $1$ and $0$ for $z=n-1$ and $z=n$, respectively, as it should be.

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