Catalan numbers and triangulations

The number of ways to parenthesize an $n$ fold product is a Catalan number in the list $1,1,2,5,14,\cdots$ where these are in order of the number of terms in the product. The $n$th such number is also the numbr of ways to triangulate an $n+1$-gon.

I'm wondering whether there is a simple translation between a specific parenthesized $n$ fold product to a specific triangulation of an $n+1$-gon.

For example one parenthesized 5-fold product is $(12)(3(45))$ This then would (hopefully) be translatable to one of the $14$ triangulations of a $6$-gon.

I have tried various ways to label the vertices of the $n+1$ gon to see which parenthesized $n$ fold product a given triangulation goes with, but no luck.

Solution 1:

There is a nice bijection between both objects and binary trees:

• Given a triangulation on the polygon with vertices numbered $0$ to $n$, build a tree whose vertices are the edges of the figure, including the $n+1$ edges of the polygon and the $n-2$ internal edges. The root is the external edge connected vertex $0$ to vertex $1$. For each internal edge $e$, which borders two triangles $T_1$ and $T_2$, then supposing $T_1$ is further from the root edge $(0,1)$, then the right (left) child of $e$ is the edge of $T_1$ which is clockwise (anti-clockwise) adjacent to $e$.

• Given a parenthesization of $x_1\cdots x_n$, build a tree with one vertex for each intermediate result when performing all of the multiplications. The result $a$ has left and right children $b$ and $c$ if $a$ was computed as the product of $b$ and $c$ in that order.

For example, with $(1\,2)(3\,(4\,5))$, the tree is

     120
    /   \
   /     60
  2     /  \
 / \   3   20
1   2     /  \
         4    5

This tree corresponds to the triangultion

   1–––––0
  /|    /|\      
 / |   / | \
2  |  /  |  5
 \ | /   | /
  \|/    |/
   3–––––4

whose tree is

      (01)
     /    \
    /     (03)
  (13)    /  \
  /  \  (34) (04)
(12) (23)    /  \
           (45) (05)

Solution 2:

Here is a possible way, which makes use of the intrinsically similar recursive property of both numbers.

I'm assuming the vertices of the $(n+1)$-gon are numbered counterclockwise from $1$ to $n+1$.

Starting from a triangulation.

In every triangulation, there is one triangle containing the edge $1\to 2$. Call the third vertex $k$. The corresponding parenthesizing is going to start with $$(1\ \ldots \ k-2)(k-1\ \ldots \ n)$$ Now "on the right" of the edge $2\to k$, you have a triangulated $(k-1)$-gon. Rename its vertices from $1$ to $k-1$ starting from the lowest and iterate.

Similarly "on the left" of the edge $1\to k$ there is a triangulated $(n-k+3)$-gon. Rename its vertices from $k-1$ to $n+1$ starting from the lowest and iterate.

Starting from a parenthesized product.

• Consider the most external product, say $$(1\ \ldots \ k-2)(k-1\ \ldots \ n)$$
• Draw a triangle $1\ 2\ k$
• Iterate after renumbering the vertices accordingly as before.

Solution 3:

These are cool (as much of has to do with Catalan Numbers), but trees are not necessary in this case. Just number the edges of the hexagon clockwise (and not including) the base. Each diagonal is now the product of the other two sides of the triangle, and you'll get your product at the base. In your example, it looks like this.

          3
      -–––––---
     /|\      |\
   2/ | \     | \4      
   /  |  \    |  \
  < 12| 3(45) |45 >
   \  |    \  |  /
   1\ |     \ | /5
     \|      \|/
      ---–––––-
     (12)(3(45))