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

 A: 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}$.
