Relations between two applications of Catalan Numbers

Question

Say I am looking at how many different balanced parenthesis I can make. Then I look at how many ways n triangles can be made with a n+2 polygon. Because they both use Catalan numbers, I know they are bijective. What I am having trouble understanding is HOW they are bijective. Does anyone have an answer?

Answer 1

I suppose we are talking about convex polygons on $n+2$ vertices.

Index vertices sequentially, I will give them indices in the next way $0, 0, 1, 2, \ldots, n$

Algo $1$ (From triangulation to parenthesis):

• Mark $0-0$ edge as "seen"
• Start at vertex $1$ (at each vertex go over all the outgoing edges in a clockwise manner, i.e. the indexing was done in the positive direction)
• If the edge under inspection, closes the triangle with two other marked edges. Mark the edge as ')' (and write it down).
• Otherwise, ignore the edge. Unless this is the edge of the polygon itself, in this case Mark it as '(' (and write it down). Proceed to the next vertex on the polygon.

E.g. The number in parenthesis denotes the index of the edge during the algorithm execution. Now, ignoring the $0$th edge write out 'o' for open parenthesis and 'c' for close we get '(())(((()())))'

[Need to prove all legal parenthesis are produced. In sketch, convex hull edges could be 'o', except between the right $0$ and $n$, and between two $0$s. So those are $n$. There are $n$ triangles, so there are $n-1$ inner edges, none could be 'o', and $1$ convex hull edge marked as 'c': so there are $n$ 'c's. Legality probably stems from triangulation (open for scrutiny). Different triangulations obviously produce different strings]

The other direction, is basically building triangles according to the string, in the opposite direction. You are closing the triangles if two other sides are set, and the edge starts at the current vertex. If there is an open parenthesis - you proceed on CH edge to the next vertex.