Example 3 (Euler's Partition) Using diagonals to partition a convex $n$-sided polygon into $n-2$ triangles, how many different methods are there?
【Analysis】Let $E_{k}$ denote the number of triangulations of a convex $k$-gon, and it is stipulated that $E_{2}=1$.
Since every edge of a polygon must belong to a triangulation triangle, consider the edge $A_{1} A_{n}$ of the $n$-gon $A_{1} A_{2} \cdots A_{n}$ in the triangulation, denoted as $\triangle A_{n} A_{1} A_{k}$, as shown in Figure 1.

Thus, one side of $\triangle A_{n} A_{1} A_{k}$ is a triangulation of a $k$-gon, and the other side is a triangulation of an $(n+1-k)$-gon, which have $E_{k}$ and $E_{n+1-k}$ triangulations, respectively. Therefore, the number of triangulations of the convex $n$-gon containing the triangle $\triangle A_{n} A_{1} A_{k}$ is $E_{k} E_{n+1-k}$.
Note that $k$ can take values $2,3, \cdots, n-1$.
Thus, we obtain the recurrence relation
$E_{n}=E_{2} E_{n-1}+E_{3} E_{n-2}+\cdots+E_{n-1} E_{2}$.
The core step of this method is: $\triangle A_{n} A_{1} A_{k}$ divides the original polygon into two smaller polygons, thereby forming subproblems isomorphic to the original problem, which establishes the recursion, known as "division recursion".

Next, consider whether there is another way to divide the original polygon? Using a diagonal of the original polygon, such as the diagonal $A_{1} A_{k}$ from $A_{1}$. The difference is that the original division relies on the fact that the triangulation must contain $\triangle A_{n} A_{1} A_{k}$, but when using the diagonal $A_{1} A_{k}$ for division, it cannot be guaranteed that "the triangulation must contain the diagonal $A_{1} A_{k}$". Therefore, more division methods need to be enumerated.

Assume that the triangulation of the convex $n$-gon $A_{1} A_{2} \cdots A_{n}$ contains a diagonal from vertex $A_{1}$. As shown in Figure 2, let this diagonal be $A_{1} A_{k}(3 \leqslant k \leqslant n-1)$. Then one side of this diagonal is a triangulation of a $k$-gon, and the other side is a triangulation of an $(n+2-k)$-gon. Thus, the number of triangulations of the convex $n$-gon containing the diagonal $A_{1} A_{k}$ is $E_{k} E_{n+2-k}$.
Note that $k$ can take values $3,4, \cdots, n-1$.
Therefore, the number of triangulations of the convex $n$-gon containing a diagonal from vertex $A_{1}$ is $E_{3} E_{n-1}+E_{4} E_{n-2}+\cdots+E_{n-1} E_{3}$.

By symmetry, the number of triangulations containing a diagonal from vertex $A_{j}(j=1,2, \cdots, n)$ is also
$$
E_{3} E_{n-1}+E_{4} E_{n-2}+\cdots+E_{n-1} E_{3} .
$$

Thus, the total number of triangulations of the convex $n$-gon is
$$
n\left(E_{3} E_{n-1}+E_{4} E_{n-2}+\cdots+E_{n-1} E_{3}\right) \text {. }
$$

The above calculation has repetitions. Because each diagonal has two vertices, it is counted twice; and the triangulation of a convex $n$-gon contains $n-2$ triangles (by the sum of the interior angles of a polygon), thus it contains $n-3$ diagonals (since $k$ non-intersecting diagonals divide the polygon into $k+1$ parts), which are counted $n-3$ times.
Thus, each triangulation is counted $2(n-3)=2 n-6$ times.
Therefore, $E_{n}=\frac{n}{2 n-6}\left(E_{3} E_{n-1}+E_{4} E_{n-2}+\cdots+\right.$
$$
\left.E_{n-1} E_{3}\right) \text {. }
$$

Using equations (1) and (2), we can find $E_{n}$. Note that equations (1) and (2) "implicitly" share many similarities. Replacing $n$ with $n+1$ in equation (1) gives
$$
E_{n+1}=E_{2} E_{n}+E_{3} E_{n-1}+\cdots+E_{n-1} E_{3}+E_{n} E_{2} .
$$

Rearranging it, we get
$$
E_{n+1}-2 E_{n}=E_{3} E_{n-1}+E_{4} E_{n-2}+\cdots+E_{n-1} E_{3} \text {. }
$$

Substituting into equation (2), we get
$$
\begin{array}{l}
E_{n+1}-2 E_{n}=\frac{2 n-6}{n} E_{n} \\
\Rightarrow E_{n+1}=\frac{4 n-6}{n} E_{n} .
\end{array}
$$

Iterating sequentially, we get
$$
\begin{array}{l}
E_{n+1}=(4 n-6)(4 n-10) \cdots \frac{2 E_{2}}{n!} \\
=2^{n-1} \cdot \frac{(2 n-3)!!}{n!} \\
=2^{n-1} \cdot \frac{(2 n-2)!!\cdot(2 n-3)!!}{(2 n-2)!!\cdot n!} \\
=\frac{(2 n-2)!}{(n-1)!\cdot n!}=\frac{C_{2 n-2}^{n-1}}{n} .
\end{array}
$$

Thus, $E_{n}=\frac{\mathrm{C}_{2 n-4}^{n-2}}{n-1}$, where $E_{n+2}=C_{n}=\frac{\mathrm{C}_{2 n}^{n}}{n+1}$ is known as the Catalan number.