Triangulations of n-gon

5.5k Views Asked by At

How many ways are there to triangulate a regular convex n-gon, if two triangulations are regarded as being the same if they can be made to coincide by a rotation of the polygon?

I found that for a hexagon that there are 14 triangulations but there are triangulations that are just rotations of the others. Thus the number of unique triangulations is 4.

1

There are 1 best solutions below

0
On

The total number of triangulations of the $n$-gon is $C_{n-2}$, where $C_n:=\frac{1}{n+1}{2n \choose n}$ is the $n$-th Catalan number (http://oeis.org/A000108). If no triangulation was equivalent to a rotation of itself then the number of equivalence classes would be $C_{n-2}/n$. We only need to calculate how much that changes taking symmetry into account. Symmetry clearly adds to this amount because it makes some orbits of triangulations have size less than $n$, thus increasing the number of orbits.

There are only two types of triangulations that are symmetric by rotation:

  • If $n=2k$ is even, then there are triangulations using a diameter and with both halves equal modulo 180 degrees rotation. The number of them is $k C_{k-1}$: there are $k$ choices of the diameter and $C_{k-1}$ choices to triangulate one half, since this half is a $k+1$-gon. In our previous count these triangulations were counted as if they formed $C_{k-1}/2$ orbits, while they actually form $C_{k-1}$, which means we have to add $C_{k-1}/2$.

  • If $n=3l$ is a multiple of three, then there are triangulations using a central equilateral triangle and with the three remaining parts equal modulo 120 degrees rotation. The number of them is $l C_{l-1}$: $l$ choices of the triangle and $C_{l-1}$ choices to triangulate one of the three remaining parts, since this part is an $l+1$-gon. In our previous count these triangulations were counted as if they formed $C_{l-1}/3$, while they actually form $C_{l-1}$, which means we have to add $2C_{l-1}/3$.

With this in mind, we have the following four possibilities for the total number of triangulations of the $n$-gon, modulo rotation:

  • if $n$ is prime with 6, the number is $C_{n-2}/n$. For example, this gives $1$ for the pentagon, $6$ for the heptagon, and $442$ for the $11$-gon.

  • if $n=2k$ is prime with $3$, we get $C_{2k-2}/2k + C_{k-1}/2$. For example, this gives $1$ for the square, $132/8+5/2=19$ for the octagon, and $1430/10 + 14/2 = 150$ for the decagon.

  • if $n=3l$ is prime with $2$, we get $C_{3l-2}/3l + 2C_{l-1}/3$. For example, this gives $1$ for the triangle and $429/9+4/3=49$ for the nonagon.

  • if $n=6m$ is a multiple of six we have to add both contributions, and get $C_{6m-2}/6m + C_{3m-1}/2 + 2C_{2m-1}/3$. For example, this gives $14/6 + 2/2 + 2/3 = 4$ for the hexagon and $16796/12 + 42/2 + 10/3 = 1424$ for the $12$-gon.

Said in a more compact form, the formula is

$$\frac1n C_{n-2} + \frac12 C_{n/2-1} + \frac23 C_{n/3-1},$$ where $C_n$ = Catalan$(n)$ (A000108) and terms are omitted if their subscripts are not integers.

This is http://oeis.org/A001683