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

enter image description here

  • $\begingroup$ @samjoe How?? en.wikipedia.org/wiki/File:Catalan-Hexagons-example.svg $\endgroup$ Oct 30 '17 at 15:03
  • $\begingroup$ @samjoe for n=6 we have 12 $\endgroup$ Oct 30 '17 at 15:04
  • $\begingroup$ @samjoe I want Triangulation of a convex n-gon so that all triangles share a side with the polygon $\endgroup$ Oct 30 '17 at 15:05
  • $\begingroup$ 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. $\endgroup$
    – jonsno
    Oct 30 '17 at 15:24

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.