[Math] Catalan numbers and triangulations

Question

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.

Answer 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)