Recursivley count triangulations of a convex polygon
I am trying to find a recursive number of different triangulations of a convex polygon with $n$ vertices.
After some searching I found that the number can be expressed using catalan numbers, this useless for me as I need a recursive expression.
Any hints will be usefull :)
Solution 1:
The first idea, which comes to my (and probably yours) mind, is to choose a fixed vertex of the polygon, draw a diagonal from this vertex, and then consider two smaller polygons to the left and to the right of this diagonal. These two sub-polygons can be triangulated independently, and then the number of triangulations for the whole polygon with this particular diagonal will be equal to the product of the number of triangulations for both sub-polygons. Then we move one vertex of the diagonal to a new position and calculate this product again and again, adding all such products. The picture below illustrates this approach for a polygon with 10 vertices, where $T_5$ and $T_7$ are numbers of triangulations for two sub-polygons.
However it's easy to see, that this approach won't enumerate all possible triangulations, and also some triangulations will be double-counted.
The correct way to decompose a polygon was invented by French mathematician Gabriel Lame in 1838. He suggested to split a polygon into two smaller sub-polygons by a triangle with fixed base. So, instead of a single vertex we choose a single polygon edge, and consider all triangles, which can be drawn using this edge and some vertex ("moving vertex") of the polygon. For each such triangle we consider triangulations of sub-polygons to the left and to the right of this triangle. It can be shown, that this decomposition gives us all possible triangulations, and each triangulation is counted only once. The picture below shows one such triangle and two sub-polygons in the polygon with 10 vertices.
Resulting recursive expression for $T_n$ will be a sum of products $T_k \cdot T_{n-k+1}$ for all $k \in [2,n-1]$ (assuming, that $T_2=1$).
For more information about Gabriel Lame work please see this historical note. Also there is a remarkable video-lecture about this subject.