I'm stuck on such problem: triangulation of the $n$-gon is division of said $n$-gon into $(n-2)$ triangles whose sides are either sides of the $n$-gon or certain non-intersecting diagonals. How many triangulations of the $n$-gon are there? How many of these are there such that every triangle has at least one side that is also a side of the $n$-gon?
The first part is easy – I've managed to deliver a Catalan number recursive expression and then found a formula for $n^{\text{th}}$ Catalan number which is $$ C_{n} = \frac{1}{n+1} {2n \choose n}.$$
What about the second part? Shall it be done by subtracting some set from $n$-th Catalan number ? What should it look like?
Thank you in advance 🙂
Best Answer
I'll show how we can do this for an $n$-gon in $n2^{n-5}$ ways. First, pick two adjacent sides of the $n$-gon, and add a diagonal to complete the triangle. There are $n$ ways to pick these sides (just pick the vertex they share). The diagonal that we added shares a vertex with two other sides of the $n$-gon (excluding the ones we started with) and can form a triangle with either of them by adding a new diagonal. We can repeat this process on the newest diagonal added until we've triangulated the $n$-gon. The picture below shows an example for the hexagon.
There were $n$ ways to choose the starting diagonal, and we had two ways of adding each of the $n-4$ subsequent diagonals. This counts $n2^{n-4}$ triangulations. However, for any triangulation obtained this way, we could start with the last diagonal added and obtain the same triangulation, so we counted each triangulation twice. Hence, there are $n2^{n-5}$ such triangulations.