Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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/

share|improve this answer
    
Thank you Moron, for your explanation and links. I was googling all the wrong things it seems. –  Dani Hobbes Feb 7 '11 at 8:34
    
To whoever flagged the above comment as rude/offensive: Aryabhata had previously named his/her account Moron –  Zev Chonoles Apr 7 '12 at 23:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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