Bijections in Dyck Paths

Question

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.

Answer 1

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.

Answer 2

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