Geometric Interpretation of Catalan Number

Question

There seems to be a simple recurrence relation for Catalan Numbers:

$$C_{n+1} = \frac{4 n+2}{n+2} C_n$$

Any geometric interpretation in terms of Dyck Paths?

https://mathworld.wolfram.com/DyckPath.html

Answer 1

There is a beautiful geometric interpretation of the identity $(n+2)C_{n+1}=2(2n+1)C_{n}$ in terms of triangulations, see e.g. this historical account.

The idea can be translated to Dyck paths (where it gets slightly less beautiful in my opinion). In the following, I will write Dyck paths as parenthesis expresseions, where „(„ means taking a step to the right and „)“ means taking a step up.

We first note that we can define Dyck paths recursively as $D=(D_1)D_2$, where $D_1$ and $D_2$ are (potentially empty) subpaths of the Dyck path $D$. Using this, we can show that a Dyck path of length $2n$ has $2n+1$ subpaths, $n+1$ of which are empty (where the entire path is also counted). Let us look more closely at the empty subpaths. An empty subpath $0$ can be of two forms, namely $\ldots ((0)D_2)\ldots$ or $\ldots ((D_1)0)\ldots$. In particular, we can interpret the empty subpaths as vertices in the Dyck path, where the first form corresponds to a „peak“ and the second form corresponds to a vertex between two up-steps.

We now consider two sets $B_1$ and $B_2$. The set $B_1$ consists of Dyck paths of length $2n+2$ with one empty subpath marked. It follows that $B_1$ has cardinality $(n+2)C_{n+1}$. The set $B_2$ consists of Dyck paths of length $2n$ with one subtree marked and oriented left or right. It follows that the cardinality of $B_2$ is $2(2n+1)C_{n}$. We get a bijection between $B_1$ and $B_2$ as follows: let $0$ be the marked empty subpath in the Dyck path in $B_1$. If it is of the form $\ldots((0)D_2)\ldots$, map to $\ldots (D_2)\ldots$, with $D_2$ oriented left. Similarly, map $\ldots ((D_1)0)\ldots$ to $\ldots (D_1)\ldots$ with $D_1$ oriented left. As this is reversible, we have a bijection and thus $(n+2)C_{n+1}=2(2n+1)C_{n}$.

Geometrically, the bijection is the following: interpret the empty subpath as a vertex $v$ as above. If the vertex $v$ is a peak, just delete the peak, mark the subpath after the peak and orient it to the left. If the vertex $v$ is of the second type, consider the subpath ending at that vertex (that is, walk down-left on the diagonal with slope 1 and stop at the first vertex $w$ you encounter. The subpath is the path between those two vertices $w$ and $v$). Now, delete the right-step after $w$ and the up-step before $v$, mark the remaining subpath and orient it to the right.