## Number of triangulations

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)$$.

The number of triangulations is $$n2^{n-5}$$ for $$n\ge 4$$.  