Bijections in Dyck Paths

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.

• 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$. – joriki May 24 '20 at 18:37
• I'll have a look, thanks :) – Pulakesh Lohiya May 24 '20 at 18:39

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.

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

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