(The Return of the Cicada)

The Cicada always moves by taking steps exclusively to the North or to the East. The Ant lives $n$ steps further North and $n$ steps further East, but this time a river follows the straight line (diagonal) between the two friends, which the Cicada cannot cross: she can go to the bank, but must remain “above” or “below” the diagonal. How many paths does she have now?

![](https://cdn.mathpix.com/cropped/2024_05_10_346641170ac76390eef3g-077.jpg?height=1102&width=1145&top_left_y=631&top_left_x=455)

A traversable path between $C$ and $F$.
We have seen that it is easy, with the movement mode of the Cicada, to count the number of paths it could take between two points, without considering the river.

Thus, there are a total of $\binom{n}{n+n}=\binom{n}{2 n}$ paths between $C$ and $F$ if we forget the river. We draw the plan of the situation on a grid. Let's count the paths that, for example, start below the diagonal but exceed it at some point.

Draw the superdiagonal: any invalid path necessarily passes through one of its vertices. For an invalid path, we call $\mathrm{C}$ its first point on the superdiagonal, and we consider the path that coincides with this one up to $C$, and with its reflection with respect to the superdiagonal after $\mathrm{C}$, as indicated in the figure below.

We can retrieve the initial path by applying the same transformation to the new path: it is an involutive transformation. The new path arrives at $F^{\prime}$, the reflection of $F$ with respect to the superdiagonal. Conversely, consider a path from $C$ to $F^{\prime}$. By applying the same transformation, we obtain an invalid path from $C$ to $F$: the correspondence between the invalid paths from $C$ to $F$ and the paths from $C$ to $F^{\prime}$ is bijective.

![](https://cdn.mathpix.com/cropped/2024_05_10_346641170ac76390eef3g-078.jpg?height=1102&width=1006&top_left_y=251&top_left_x=525)

We then know that there are $\binom{(n+1)+(n+1)}{n-1}=\binom{2 n}{n-1}$ invalid paths to subtract from the $\binom{2 n}{n}$ total paths. We obtain the expression for $\mathcal{C}_{n}$, the $n$-th Catalan number.

$$
\mathcal{C}_{n}=\binom{2 n}{n}-\binom{2 n}{n-1}=\frac{(2 n)!}{(n!)^{2}}-\frac{(2 n)!}{(n-1)!(n+1)!}=\frac{(2 n)!}{(n!)^{2}}-\frac{n}{n+1} \times \frac{(2 n)!}{(n!)^{2}}=\frac{1}{n+1}\binom{2 n}{n}
$$

## Other Examples

We can find the Catalan numbers every time we can represent the situation by counting the "paths in the square that remain below the diagonal":

- Two candidates A and B in an election each received $n$ votes $(n \in \mathbb{N})$, however, throughout the counting, A remained in the lead, meaning that the pile of votes for B never exceeded that of the votes for A. In how many ways could the ballots have been arranged for this to happen?
- A valid parenthesization, consisting of opening and closing parentheses, is valid if it has an equal number of opening and closing parentheses, and if no closing parenthesis is ever placed before an opening one. How many valid parenthesizations of length $2 n(n \in \mathbb{N})$ exist?