In how many different ways can a polygon with $n$ sides be divided into triangles by connecting its vertices with straight line segments?
Let $T_{n}$ denote the number of triangulations of a polygon with $n$ sides. We have $T_{3}=1$ and $T_{4}=2$.

We label the vertices $A_{1}, \ldots, A_{n}$ in a clockwise direction.

Consider the edge $\left[A_{1} A_{2}\right]$. If $A_{k}$ is the third vertex of the triangle, then there remains a polygon with $k-1$ vertices to the right (between vertices $A_{2}$ and $A_{k}$) and a polygon with $n-k+2$ vertices to the left (between vertices $A_{k}$ and $A_{1}$). Therefore, if we fix the triangle $A_{1} A_{2} A_{k}$, there are $T_{k-1} T_{n-k+2}$ triangulations in which the triangle $A_{1} A_{2} A_{k}$ is present.

We thus have the recurrence relation (setting $T_{2}=1$):

$$
T_{n}=\sum_{k=3}^{n} T_{k-1} T_{n-k+2}
$$

Change the order of summation by choosing $i=k-3$

$$
T_{n}=\sum_{i=0}^{n-3} T_{i+2} T_{n-i-1}
$$

We therefore have $T_{n}=C_{n-2}$, because $T_{2}=T_{3}=C_{0}=C_{1}=1$ and

$$
C_{n-2}=\sum_{i=0}^{(n-2)-1} C_{(i-2)+2} T_{(n-2)-(i-2)-1}
$$

## Remark:

These numbers were first introduced in the $18^{\text {th }}$ century by Leonhard Euler to solve this problem. Eugène Charles Catalan made the connection between this problem and the counting of parentheses. Historically, things unfolded in the opposite order of what we have presented here.