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.


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/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.