Dyck paths is Catalan

Statement

The number of Dyck path of length $2 n$ is equal to the Catalan numbers.

Below are three proofs:

generating functions
reflection method - a bit more combinatorial in nature, we are finding the number of lattice paths and subtracting away the ones that aren't Dyck paths
cyclic shifts - we count all the paths and then split into cosets

Proof 1 (Generating functions)

First, we show the following relation:

\tilde{C_{n}} = \sum_{k = 1}^{n} {\tilde{C}}_{k - 1} \cdot {\tilde{C}}_{n - k}, {\tilde{C}}_{0} = 1

Let's think about when the Dyck path first touches $x$ -axis and call this $2 k$ . Let's count the number of paths that first touches the $x$ -axis at this point.

We can break this path into two parts left and right:

We see that what happens on the right of $2 k$ is just another Dyck path of length $2 (n - k)$ . Thus, the number of such paths is given by ${\tilde{C}}_{n - k}$
On the left however, this path must never touch the $x$ -axis (as we assumed that the path first touches the $x$ -axis at the point $2 k$ ). This also means that we know what the endpoints (as in the first and last move) of this path looks like: the first move is up and the last move (to reach the $x$ -axis at $2 k$ ) is down. If we move the $x$ -axis up to $y = 1$ , then we note that the portion above this is a Dyck path of length $2 (k - 1)$ (taking away the two end segments). Thus, there are ${\tilde{C}}_{k - 1}$ number of paths here.

Summing over all possible $k$ , we have ${\tilde{C}}_{n} = \sum_{k = 1}^{n} {\tilde{C}}_{k - 1} \cdot {\tilde{C}}_{n - k}$ as desired.

Now consider the generating function

f (x) = \sum_{n = 0}^{\infty} {\tilde{C}}_{n} x^{n}

fun fact: this power series converges for $| x | < \frac{1}{4}$

We now claim that $f (x)$ satisfies the functional equation:

f = x f^{2} + 1

This is evidently true for $[x^{0}] f (x)$ as ${\tilde{C}}_{0} = 1$ and $x f^{2}$ is divisible by $x$ .
Note that two identities
- $[x^{n}] (f \cdot f) = \sum_{k = 1}^{n} [x^{k}] f \cdot [x^{n - k}] f$
- $[x^{n}] (x f) = [x^{n - 1}] f$ for $n \geq 1$ (and for $n = 0$ , it is 0)
Applying these two, we have
$[x^{n}] (x f \cdot f) = \sum_{k = 1}^{n} [x^{k - 1}] f \cdot [x^{n - k}] f$
which we know by the above relation is equal again to $[x^{n}] f$ .

Now, we can use the quadratic equation to obtain the two solutions

f (x) = \frac{1 \pm \sqrt{1 - 4 x}}{2 x}

To figure out which solution it is, note that $f (0) = 1$ .

$lim_{x \to 0} \frac{1 + \sqrt{1 - 4 x}}{2 x} = \infty$
$lim_{x \to 0} \frac{1 - \sqrt{1 - 4 x}}{2 x} = 1$ (by L'Hopital's) <- so it's this one

Then (applying the generalized binomial theorem), we have

\begin{aligned} {\tilde{C}}_{n} = [x^{n}] f (x) & = - \frac{1}{2} [x^{n + 1}] (1 - 4 x)^{1 / 2} \\ = - \frac{1}{2} (\binom{1 / 2}{n + 1}) (- 4)^{n + 1} \\ = - \frac{1}{2} \cdot \frac{1}{2} \cdot (\frac{1}{2} - 1) \dots (\frac{1}{2} - n) \cdot \frac{(- 4)^{n + 1}}{(n + 1)!} \\ = \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{3}{2} \cdot \frac{5}{2} \cdot \dots \frac{2 n - 1}{2} \cdot \frac{4^{n + 1}}{(n + 1)!} \\ = \frac{1}{2^{n + 1}} \cdot \frac{(2 n)!}{2^{n} n!} \cdot \frac{4^{n + 1}}{(n + 1)!} \\ = \frac{1}{n + 1} \cdot (\binom{2 n}{n}) \end{aligned}

Proof 2 (reflection method)

We first notice that there are $(\binom{2 n}{n})$ number of paths from $A = (0, 0)$ to $B = (2 n, 0)$ . We'll call these paths lattice paths. We will count the number of non-Dyck paths, ie. the number of paths that intersect with the line $y = - 1$ .

Suppose we have a non-Dyck path $P$ . Let $x$ be the first time it intersects with $y = - 1$ . We construct the path $P^{'}$ as follows:

from $A$ to $x$ , it is the same as $P$
from $x$ to $B$ , we reflect the directions
Notice that this path ends at $B^{'} = (2 n, - 2)$ since it has $n - 1$ up steps and $n + 1$ down steps.

Now, we claim that this construction $P \to P^{'}$ is a bijection between all non-Dyck paths $A \to B$ and all lattice paths $A \to B^{'}$ . We show this by exhibiting an inverse, which would be reflecting the directions again after we find $x$ , the first time the path intersects with $y = - 1$ .

Now there are $(\binom{2 n}{n - 1})$ ways of constructing lattice paths $A \to B^{'}$ (pick n-1 ups, n+1 downs), so to obtain the number of Dyck paths, we have

\begin{aligned} {\tilde{C}}_{n} & = (\binom{2 n}{n}) - (\binom{2 n}{n - 1}) \\ = \frac{2 n \dots (n + 1)}{n!} - \frac{2 n \dots (n)}{(n + 1)!} \\ = (\binom{2 n}{n}) (1 - \frac{n}{n + 1}) \\ = \frac{1}{n + 1} (\binom{2 n}{n}) \end{aligned}

as desired.

Proof 3 (cyclic shifts)

Motivation

First, we observe that

\frac{1}{n + 1} (\binom{2 n}{n}) = \frac{1}{2 n + 1} (\binom{2 n + 1}{n})

and we can interpret $(\binom{2 n + 1}{n})$ as the number of lattice points with $n$ up steps and $n + 1$ down steps. In other words, paths from $(0, 0) \to (2 n + 1, - 1)$ . The number of Dyck paths are equal to the number of lattice paths that go below the $x$ -axis only at the last step. We'll call these paths Dyck- paths. We'll also denote up and down with + and - respectively.

We can cyclically shift the path:

"+ - - + - "
"- - + - +"
"- + - + -"
"+ - + - -"
"- + - - +"

This gives us $2 n + 1$ different lattice paths $(0, 0) \to (2 n + 1, - 1)$ .

Proof

We finish the proof if we can prove these two facts:

All paths obtained from cyclically shifting are different
Exactly one of them is a Dyck- path

Since we can create an equivalence class of paths that can be obtained by cyclic shifting, which partition the space of all paths into classes of size $n + 1$ , and each of these equivalence classes has exactly one representative that is a Dyck- path. Thus, $\frac{1}{n + 1}$ of the number of paths is a Dyck- path.

Mark the first (global) minimum as $x$ . We claim that whenever we shift, the position of $x$ decreases, unless $x = 1$ , then $x$ becomes $2 n + 1$ .

For $x > 1$ , when we move the first segment to the end, the rest of the graph all gets shifted up or down one, so it follows that there is no point before $x$ that is less than or equal to $x$ (as we assumed that $x$ is the first minimum), and there can't be a lower point after $x$ as the last point will always be $- 1$ .

If $x = 1$ , then this means that the minimum is $- 1$ and that the first move is down. When we move this move to the end, any other point that takes on a height -1 becomes 0. The only $- 1$ is at the end.