# Triangulation of a convex n-gon so that all triangles share a side with the polygon

So I was reading A Path to Combinatorics for Undergraduates by Titu Andreescu and Zuming Feng, and I came across this question:

Let n be an integer greater than $4$, and let $P_1 P_2 \ldots P_n$ be a convex $n$ sided polygon. Zachary wants to draw $n-3$ diagonals that partition the region enclosed by the polygon into $n-2$ triangular regions and that may intersect only at the vertices of the polygon, In addition, he wants each triangular region to have at least $1$ side that is also a side of the polygon. In how many ways can Zachary do this?

After researching a bit i found out that $C_{n-2}$ (the $(n-2)^{\text{th}}$ Catalan number) counts the number of triangulations for a convex n-sided polygon, but I don't know how to account for the triangulations that have triangles which don't have a side in common with the polygon. I would really appreciate it if someone could help me solve the problem.

• Think about a triangle transcribed in a hexagon, these triangulations should appear similar May 31, 2017 at 4:26

The answer is $$n \cdot 2^{n-5}$$. Fix the side $$P_1P_2$$ and we first observe that this side must appear in one of the triangles. Let's say that it appears in the triangle $$P_1P_2P_i$$, with $$3 \le i \le n$$. This triangle divides the $$n$$-agon in two polygons (or one when $$i = 3$$ or $$i = n$$), one with $$i - 1$$ sides and the other with $$n - i - 2$$ sides.

Assume first that $$i = 3$$ (the case $$i = n$$ is similar). The remaining polygon is $$P_1P_3P_4 \ldots P_n$$ and we should triangulate it. The side $$P_1P_3$$ should be present in one of the triangles and the third vertex of this triangle must be $$P_4$$ or $$P_n$$, otherwise, we would get a triangle without any side in common with the original polygon. So we have $$2$$ possibilities at this point and if we continue with a similar reasoning, it's easy to see that we will have $$2^{n-4}$$ possibilities if $$i = 3$$.

If $$i = n$$, we also have $$2^{n-4}$$ possibilities and if $$3 < i < n$$, we now have indeed two polygons and by a similar argument, we have $$2^{i-4} \cdot 2^{n-i-1} = 2^{n-5}$$ possibilities for each $$i$$.

Therefore the total number of triangulations with the required property is $$2^{n-4} + (n-4)2^{n-5} + 2^{n-4} = n \cdot 2^{n-5}.$$

Here is a slightly different reasoning from the older answer presented here. We will prove that there is $$n\cdot 2^{n-5}$$ ways to triangulate a convex $$n$$-sided polygon in such way that every triangle has a side common with the polygon.

Each triangulation has at least one ear. (If $$n>3$$ a polygon has at least $$2$$ ears. If we consider the dual graph of triangulation, it is easy show that $$t_2-t_0=2$$, where $$t_2$$ is the number of ears and $$t_0$$ is the number of triangles which have $$0$$ common sides with the polygon. $$t_0=0$$ is our case, so there are exactly $$2$$ ears if $$n>3$$. We won’t really use this fact though. Or rather, we will prove the same statement in the process.)

There are $$n$$ ways of choosing where the first ear of triangulation will be for a convex polygon, since any pair of neighbour edges can be chosen. Let us call the farthest vertices of these edges A and B. It is clear that there must be a diagonal drawn either from A or from B (but not both). Moreover, if a diagonal is drawn from A, its other end is the vertex next to B. And vice versa, if a diagonal is drawn from B, its other end is the vertex next to A.

The very same reasoning as for diagonal AB can be made for a new diagonal. And so on. Each time there is exactly $$2$$ ways to choose next diagonal. This process will end when we won’t be able to draw a diagonal. This means we reached a second ear.

The overall number of diagonals in triangulation is $$n-3$$. There was $$n$$ ways to choose the first one and $$2$$ ways to choose any other. The answer is not $$n\cdot 2^{n-4}$$ though since every triangulation is counted $$2$$ times: starting from both its ears. Finally the answer is $$n\cdot 2^{n-4}\cdot 1/2= n\cdot 2^{n-5}$$.