Isomorphic relation between Catalan representations

Question

There is an unanswered question at MathOverflow:

Intersecting Family of Triangulations

This article at Wikipedia explains the concept of non-intersecting partitions of a polygon:

Catalan number

So the Dyck words on $n=2$ are $XXYY$ and $XYXY$, and the corresponding $2$ $4$-gons are the polygons that connect vertices $1\to3$ and $2\to4$.

I am failing to find an isomorphism here, let alone for the higher $n$ cases.

The motive is to find an alternative explanation of the problem at MathOverflow which might lead to a more obvious and acceptable solution.

Answer 1

You can do it in a couple of steps. Start by associating with each of the $C_n$ triangulations of a regular $(n+2)$-gon a full binary tree with $n+1$ leaves. I’ll describe the association in general terms, but you can use these pictures from Wikipedia showing the $C_4=14$ triangulations of a hexagon and the $14$ full binary trees with $5$ leaves to help follow it.

The procedure is recursive. Fix one side of the $(n+2)$-gon and the unique triangle containing it to correspond to the root of the tree; in the picture that’s the top side and the dark triangle. The remaining $n+1$ sides of the $(n+2)$-gon will correspond to the leaves of the tree, and the remaining triangles will correspond to the interior nodes of the tree.

Now remove the top side and the adjacent triangle. What remains is a pair of triangulated subpolygons attached at a single vertex. (If the root triangle is adjacent to another side of the original $(n+2)$-gon, one of these polygons is degenerate, consisting of a single side of the original polygon; we consider it a $2$-gon with $2$ sides.) Say the left and right subpolygons have $\ell$ and $r$ sides, respectively; then it’s not hard to verify that $\ell+r=n+3$. Moreover, $2\le\ell,r\le n+1$, so both subpolygons have fewer sides than the original $(n+2)$-gon.

• If one of the subpolygons is a $2$-gon, it corresponds to a leaf of the associated tree: if it’s the left (right, resp.) subpolygon, then the left (right, resp.) child of the root of the tree is a leaf.

• Otherwise, it has a side that is one of the edges of the removed triangle. Make that side its root side, and repeat the process.

Reversing the association is just as easy. The process is again recursive. Given a full binary tree with $n+1$ leaves, let $\ell$ and $r$ be the numbers of leaves in the left and right subtrees, respectively. Number the sides of an $(n+2)$-gon anticlockwise from $0$ through $n+1$, starting at the top. Let $v$ be the vertex shared by sides $\ell$ and $\ell+1$, and draw in the triangle that has side $0$ as one edge and vertex $v$ as the opposite vertex.

• If this triangle does not include edge $1$ or edge $n+1$, it will lie between two subpolygons, one with $\ell+1$ edges, the other with $r+1$ edges. Each of these subpolygons has a side in common with the triangle; treat that side as the ‘top’ side. Then use the left (right, resp.) subtree of the binary tree to triangulate the left (right, resp.) subpolygon.

• If the triangle does include side $1$ or edge $n+1$, what remains will be an $(n+1)$-gon, one of whose sides is an edge of the triangle. Take that side to be its top side, and use the subtree with $n$ leaves to triangulate it.

It only remains to exhibit a correspondence between full binary trees with $n+1$ leaves and Dyck words of length $2n$. It’s convenient to use the special case of Dyck words that are correctly matched strings of parentheses.

The correspondence is quite straightforward. Start by erasing the $n+1$ leaves; what remains is always a rooted binary tree with $n$ vertices, its root being that of the original tree. Each of these $n$ vertices corresponds to one matched pair of parentheses. Start by making a matched pair of parentheses for the root. If it has a left child, put its matched pair inside the first pair, and if it has a right child, put its matched pair completely to the right of the first pair. Continue recursively in this fashion. For example, the top full binary tree in the diagram above produces the parenthesis string ()()()(); the one immediately below it produces ()()(()); and the one immediately below and to the right of that produces (())(()).

It’s clear that this construction always produces a matched string of parentheses. On the other hand, it’s equally clear that any matched string of parentheses can be coded in this way as a binary tree. Take, for instance, $n=6$ and the parenthesis string (()(()()))()() with $7$ pairs of matched parentheses. Find the right parenthesis matching the first left parenthesis; that matched pair will be the root of the tree. Break the string immediately after it to get (()(()())) and ()(). What’s inside it, ()(()()), will produce the left subtree; what’s after it, ()(), will produce the right subtree. Now repeat recursively to generate the tree. In this example you get the following tree:

                                      *  
                                     / \  
                                    /   \  
                                   /     \  
                                  *       *  
                                   \       \  
                                    \       \  
                                     *       *  
                                    /  
                                   *  
                                    \  
                                     *

Now just add the $8$ leaves required to give each node two children, and you’ll have the desired full binary tree with $8$ leaves.