Explanation/Intuition behind why $C_n$ counts the number of triangulations of a convex $n+2$-gon?

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.

Solution 1:

We can find a 1-1 correspondence between a triangulation of a polygon and a binary tree, by considering a triangle to be a vertex and connecting two vertices by an edge if they share a side. You fix one side of the polygon as the "root" side, and the triangle on that side becomes the root vertex of the tree.

For instance see this: http://www.cs.sunysb.edu/~jgao/CSE548-fall07/David-mount-DP.pdf, see pages 20 and 21.

Another page: http://www.ics.uci.edu/~eppstein/260/011023/