Number of triangulations
Task number: 3451
How many ways are there to divide a regular \(n\)-gon with vertices \(1,…,n\) into triangles such that cuts are along non-intersecting chords and also each triangle has at least one side in common with the \(n\)-gon?
For example, we can divide a pentagon into three triangles \((1{,}2,3)\), \((1{,}3,5)\) and \((3{,}4,5)\).
(Dividing into triangles is called triangulation, though in the general case we do not require each triangle to have a common side with the original polygon.)
Hint
Fix one of the triangles and add the others to it one by one.
Solution
Each such triangulation contains \(n-2\) triangles, so there exist exactly two vertices which do not belong to any chord. Call one of these vertices \(u\) – this can be done in \(n\) ways and we draw this triangle with \(u\) at the top. Now we will add \(n-4\) triangles. For each of them we can choose one of two possibilities, i.e. whether the common side is on the path leading from vertex \(u\) to the right or left. The last triangle joins these two paths. We can achieve each configuration in two ways, sincne we can choose the vertex \(u\) in two ways.
For example, we can obtain the given division of a pentagon by first choosing \(u=2\). Then we draw the triangle \((1{,}2,3)\), then we attach \((1{,}3,5)\) on the left side and we finish with \((3{,}4,5)\).
Answer
The number of triangulations is \(n2^{n-5}\) for \(n\ge 4\).
