Example 2.4.6 A convex $n$-sided polygon, by inserting non-intersecting diagonals inside, is divided into some triangular regions. How many different ways are there to do this?
Let $h(n)$ denote the number of ways to divide a convex $(n+1)$-gon into triangles, with the convention that $h(1)=1$.
It is easy to see that $h(2)=1, h(3)=2$.
For $n \geqslant 4$, consider a convex $(n+1)$-gon $A_{1} A_{2} \cdots A_{n+1}$, and fix one of its sides $A_{1} A_{n+1}$. Choose any other vertex $A_{k+1} (k=1,2, \cdots, n-1)$. Draw lines from $A_{k+1}$ to $A_{1}$ and $A_{n+1}$ to form a triangle $T$, which divides the convex $(n+1)$-gon into three parts: $T, R_{1}, R_{2}$, where $R_{1}$ is a convex $(k+1)$-gon and $R_{2}$ is a convex $(n-k+1)$-gon. Therefore, $R_{1}$ can be divided in $h(k)$ ways, and $R_{2}$ can be divided in $h(n-k)$ ways, so
$$
\begin{array}{c}
h(n)=\sum_{k=1}^{n-1} h(k) \cdot h(n-k), \\
h(n)-2 h(1) h(n-1)=\sum_{k=2}^{n-2} h(k) \cdot h(n-k) .
\end{array}
$$

We will now prove that $\sum_{k=2}^{n-2} h(k) \cdot h(n-k)=\frac{2(n-3)}{n} h(n-1)$.
Choose any diagonal $A_{1} A_{k+1}$ of a convex $n$-gon, which divides the $n$-gon into two parts: $r_{1}$ and $r_{2}$, where $r_{1}$ is a convex $(k+1)$-gon and $r_{2}$ is a convex $(n-k+1)$-gon. Thus, the number of triangulation schemes with $A_{1} A_{k+1}$ as the dividing line is $h(k) h(n-k) (2 \leqslant k \leqslant n-2)$, so the number of triangulations from $A_{1}$ to all diagonals is
$$
\sum_{k=2}^{n-2} h(k) h(n-k) ;
$$
$A_{1}$ can be replaced by $A_{2}, A_{3}, \cdots, A_{n}$, so the total number of triangulations is
$$
n \cdot \sum_{k=2}^{n-2} h(k) h(n-k) \text {. }
$$

Note that there is overcounting here: one, the same diagonal is counted twice with its associated two vertices; two, a triangulation consists of $n-3$ diagonals, and each of these $n-3$ diagonals is counted once for the same triangulation. Therefore,
$$
\begin{array}{l}
h(n-1)=\frac{n}{2(n-3)} \sum_{k=2}^{n-2} h(k) h(n-k), \\
\sum_{k=2}^{n-2} h(k) h(n-k)=\frac{2(n-3)}{n} h(n-1), \\
h(n)=2 h(1) h(n-1)+\frac{2(n-3)}{n} h(n-1)=\frac{4 n-6}{n} h(n-1) \text {. } \\
\text { Let } n \cdot h(n)=E(n) \text {, } \\
\text { then } E(n)=(4 n-6) \frac{E(n-1)}{n-1}=\frac{(2 n-2)}{n-1} \frac{(2 n-3)}{n-1} E(n-1) \\
=\frac{2 n-2}{n-1} \frac{2 n-3}{n-1} \frac{2 n-4}{n-2} \frac{2 n-5}{n-2} E(n-2) \\
=\cdots=\frac{2 n-2}{n-1} \frac{2 n-3}{n-1} \frac{2 n-4}{n-2} \frac{2 n-5}{n-2} \cdots \frac{4 \times 3}{2 \times 2} \frac{2 \times 1}{1 \times 1} E(1) \\
=\frac{(2 n-2)!}{(n-1)!(n-1)!}=\mathrm{C}_{2 n-2}^{n-1} \text {, } \\
\therefore \quad h(n)=\frac{1}{n} \mathrm{C}_{2 n-2}^{n-1} \text {. } \\
\end{array}
$$