I was reading about the Catalan numbers on wikipedia, because it seems like they show up quite a bit.
I'm reading some of the examples in the applications to combinatorics section. Some of them make sense fairly easily for me. For example, I see that the number of ways to parenthesize a product of $n+1$ terms $x_0,x_1,\dots, x_n$ is $C_n$, since the final multiplication $\cdot$ based on the parentheses must show up between two factors $x_k$ and $x_{k+1}$, and the way to parenthesize those terms $x_0,\dots,x_k$ and $x_{k+1},\dots,x_n$ are $C_k$ and $C_{n-k-1}$, respectively . Since this final $\cdot$ could show up anywhere, I get the recurrence $ C_n=C_0C_{n-1}+C_1C_{n-2}+\cdots +C_{n-1}C_0 $ which is the same as the Catalan numbers, given that the initial conditions are the same.
In the same way, I see that the number of binary rooted trees with $n+1$ leaves is also given by $C_n$, since a binary tree essentially determines a parenthesization of a product of $n+1$ leaves if two leaves are enclosed in parentheses if they have the same parent node, and you follow the tree from the leaves up.
I also understand the way it counts monotonic paths not passing the diagonal, as the first time a path touches the diagonal is like the position of the final multiplication on a product of $n$ terms, and splits the product into two smaller, but essentially similar subcases.
But how does triangulating an $n+2$-gon give the same counting situation? I figured if you choose a vertex and draw a triangle with it as one of the vertices, it should give two other polygons that should suggest a recurrence relation like the one above, just like the Catalan numbers. Could someone point it out, or possibly show a way to relate it to one of the other identical counting situations which I understood? I don't quite see how this situation is the same. Thanks.