A Dyck path of length $2 n$ is a path starting from the point $(0,0)$ in the plane, and ending at the point $(2 n, 0)$, by only taking steps to the north-west and to the south-west (moving 1 to the right and 1 vertically) without ever going below the x-axis, as shown in the following figure. How many Dyck paths of length $2 n$ are there?

![](https://cdn.mathpix.com/cropped/2024_05_10_bca2b404556ff27bef16g-65.jpg?height=328&width=1425&top_left_y=630&top_left_x=293)
Before starting the proof, note that we can obtain a recurrence relation on the number $C_{n}$ of Dyck paths of length $2 n$. Indeed, consider a Dyck path of length $n$. Then let $0 \leq k < n$ be the largest integer such that the path touches the x-axis at step $2 k$ (by a parity argument, if the path touches the x-axis, it does so at an even abscissa). For a given $k$, to construct a Dyck path of length $2 n$, it is necessary and sufficient to construct one of length $2 k$, then go up, then construct a Dyck path of length $2(n-k-1)$ that does not touch the x-axis, and then go down one step (on the image, the dotted lines should be replaced by Dyck paths). Thus, we show that $C_{n} = \sum_{k=0}^{n-1} C_{k} C_{n-k-1}$.

![](https://cdn.mathpix.com/cropped/2024_05_10_bca2b404556ff27bef16g-65.jpg?height=128&width=420&top_left_y=1501&top_left_x=1161)

With this relation, we could verify the result by induction. However, we will seek a more direct method to obtain $C_{n}$. Consider the function $f$ as follows: consider a path that is not a Dyck path but ends at $(2 n, 0)$. Let $2 k + 1$ be the smallest abscissa where the path is below the x-axis. The function $f$ associates with this path the path symmetric with respect to the x-axis between the abscissas 0 and $2 k + 1$, followed by the same path translated 2 units upwards (as illustrated below for $n=14$ on a particular path).

![](https://cdn.mathpix.com/cropped/2024_05_10_bca2b404556ff27bef16g-65.jpg?height=429&width=1514&top_left_y=2084&top_left_x=271)

![](https://cdn.mathpix.com/cropped/2024_05_10_bca2b404556ff27bef16g-66.jpg?height=623&width=1516&top_left_y=171&top_left_x=264)

We verify that this function is indeed a bijection between the paths ending at $(2 n, 0)$ that are not Dyck paths and the paths ending at $(2 n, 2)$, by constructing the inverse of $f$. Thus, we have $C_{n} = \binom{2 n}{n} - \binom{2 n}{n+1} = \frac{1}{n+1} \binom{2 n}{n}$. These are the Catalan numbers, which have numerous combinatorial interpretations!

## More Difficult Exercises