Catalan numbers in polygons

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?

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.

• Wow, thank you! That was perfectly clear. Dec 22 '20 at 12:23

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