[Math] Number of Lattice Paths from $(0,0)$ to $(n, n)$ without going over $y=x$

catalan-numberscombinatorics

This is a question that was asked at the start of the section on Catalan Numbers in my book. I'm having trouble answering it.

My Work

All of the legal paths (ones which do not cross over $y=x$) must begin with a move right and end with a move up. Further, any time the number of upward moves exceeds the number of downward moves, the path becomes illegal. So it would seem, the answer is the total number of paths from $(0,0)$ to $(n,n)$ – (Total illegal paths). The number of paths from $(0,0)$ to $(n,n)$ is $\binom{2n}{n}$. The number of illegal paths I'm slightly less clear on. How do I compute the number of illegal paths?

Best Answer

There are a few ways to solve this question, each of which uses a different, but very useful, counting principle. We wish to count the paths that stay weakly below the line $y=x$ (they can touch the line, but not go above)

1) Reflection Principle

First, we consider the total number of paths that exist from $(0,0)$ to $(n,n)$, which is ${2n}\choose{n}$, since we must take exactly $n$ up steps, each of which we denote by a $u$, and $n$ right steps, each of which we denote by an $r$, and so this simply corresponds to the ${2n}\choose{n}$ ways we can rearrange a string with $n$ $u$s and $n$ $r$s.

Next, we consider the paths that DO go above the line $y=x$ (the bad paths). We note that for each such path, there exists a unique first upstep that brings the path above the line (it could even be the first step). We draw a line of slope $1$ passing through the end of this unique up step, and reflect the path up to that step about the line, giving a path from $(-1,1)$ to $(n,n)$. (See picture)

A bad path reflected after its first bad upstep

Now, we've shown that any bad path can be mapped onto a path from $(-1,1)$ to $(n,n)$. It is indeed true (but you should convince yourself of this) that any path from $(-1,1)$ to $(n,n)$ can be mapped onto a bad path from from $(0,0)$ to $(n,n)$. Hence, there are the same number of bad paths from from $(0,0)$ to $(n,n)$ as the number of all paths from $(-1,1)$ to $(n,n)$, which by the argument above is ${2n}\choose{n-1}$=${2n}\choose{n+1}$.

Hence the number of paths that stay below the line $y=x$ is (after some manipulation): $${{2n}\choose{n}} - {{2n}\choose{n-1}}=\dfrac{1}{n+1}{{2n}\choose{n}}$$

2) Generating Functions

If you are comfortable with generating functions, we can let $g(x)$ be the generating function for paths that stay below the line $y=x$. Let us call paths that stay below the line good paths. Then we can note that each path that is below the line $y=x$ can be broken into two after the first return to the axis. A Dyck path broken into the the part up until the first return to the axis, and another Dyck path

Now if we let $x^{1/2}$ be the weight of each step, then the first part of the path can be written as $x g(x)$, as it is a right step ($x^{1/2}$), followed by a good path ($g(x)$), followed be an up step ($x^{1/2}$). The second part of the path is just another good path ($g(x)$). The only path that cannot be written this way is the lone good path that does not start with a right step, namely, the empty path from $(0,0)$ to $(0,0)$, who's generating series is just $x^0=1$. Hence we have that $$g(x) = x g(x) \cdot g(x)+1=x g(x)^2+1 $$

Solving for $g(x)$ gives: $$g(x) = \dfrac{1 \pm \sqrt{1-4x} }{2x}$$

One can then use the generalized binomial theorem to find the series:

$$g(x) = \sum_{n=0}^{\infty} a_n x^n$$

and you should get $a_n = \dfrac{1}{n+1} {{2n}\choose{n}}$, and of course by our construction, $a_n$ counts the good paths from $(0,0)$ to $(n,n)$.

3) Cycle Lemma

Using the Cycle Lemma (http://www.cs.tau.ac.il/~nachumd/papers/CL.pdf) one can map the good paths from $(0,0)$ to $(n,n)$ to dominating strings of $n+1$ $0$s and $n$ $1$s, where $0$s represent right steps and $1$s represent up steps. The cycle lemma tells us that of the $2n+1$ cyclic permutation of each such possible string, only $(n+1)-n=1$ of them are dominating. and hence since there are ${2n+1}\choose{n}$ possible strings, the total number of dominating strings, which corresponds to the good paths, is:

$$\dfrac{1}{2n+1} {{2n+1}\choose{n}} = \dfrac{1}{n+1} {{2n}\choose{n}}$$