# Number of triangulationss of a polygon that each triangle has at least one edge with polygon

What is the number of triangulations of a polygon that each triangle has at least one edge with polygon?

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

For example for $n=6$ we have $12$.

• Oct 30 '17 at 15:03
• @samjoe for n=6 we have 12 Oct 30 '17 at 15:04
• @samjoe I want Triangulation of a convex n-gon so that all triangles share a side with the polygon Oct 30 '17 at 15:05
• Sorry for the confusion! I didn't understand correctly what was being asked. I recommend you to edit your question and add the links there too! Sorry again. Oct 30 '17 at 15:24

## 1 Answer

There are $n-2$ triangles in a triangulation of an $n$-sided polygon. Each of them must share at least one side with the polygon, and there are $n$ sides to go around, which means that $n-4$ of them share one side (call these triangles type 1), and $2$ of them share two sides (call these two triangles type 2).

Pick one of the type-2 triangles to be the "starting" triangle. The starting triangle has one exposed diagonal, which is shared by one of the type-1 triangles. There are two ways to place the type-1 triangle: its polygon side can be clockwise or counterclockwise from the type-2. Once we've done that, we have another exposed diagonal left, which is another two-fold choice to make.

So for each of the type-1 triangles, we have $2$ choices, for $2^{n-4}$ ways to make those choices total. This gives $n \cdot 2^{n-4}$ triangulations since there's $n$ ways to place the starting triangle. However, each of them is counted twice, because we could have picked either type-2 triangle to be the starting triangle. So the overall answer is $n \cdot 2^{n-5}$.