Catalan numbers in polygons

Question

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

Answer 1

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.

Answer 2

I don’t have a solution, but I do have an answer that illustrates a useful tool for attacking such problems.

It’s not hard to find pictures online of the $14$ triangulations of a hexagon, and here are the $42$ triangulations of a heptagon. If we let $t_n$ be the number of triangulations such that every triangle shares at least one side with the $n$-gon, we find that $t_3=1$, $t_4=2$, $t_5=5$, $t_6=12$, and $t_7=28$. Looking up the sequence $1,2,5,12,28$ in OEIS, we get A045623 as the first hit. If $a_n=t_{n+3}$ for $n\ge 0$, that sequence is listed as the number of $1$s in all compositions of $n+1$, but in the COMMENTS it is noted that $a_n$ is indeed our $t_n$. The FORMULA section of the entry offers the recurrence

$$a_{n+1}=2a_n+2^{n-1}$$

for $n>0$, with $a_0=1$ and $a_2=2$; this translates to

$$t_{n+1}=2t_n+2^{n-4}$$

for $n>3$, with $t_3=1$ and $t_4=2$. It also offers the closed form $a_n=(n+3)2^{n-2}$ for $n\ge 1$ and $a_0=1$, which translates to $t_n=n2^{n-5}$ for $n\ge 4$ and $t_3=1$; this can of course be derived from the recurrence.

I’ve not yet seen an argument for either the recurrence or the closed form, and I may not find much time to think about. If I do come up with one, however, I’ll add it (if no one has beaten me to it).