Write down $9$ $\times$'s, like this
$$ \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times$$
These determine $8$ gaps, plus $2$ "endgaps." We either choose $6$ gaps to put a $\circ$ into, or choose one of the two endgaps, plus $5$ real gaps to put a $\circ$ into. This can be done in
$$\binom{8}{6}+2\binom{8}{5}$$
ways.
To make a real hexagon inscribed in our $15$-gon out of the pattern of $\circ$ and $\times$, take a fixed vertex of the given $15$-gon, put the leftmost of our $15$ "letters" into it, and the rest counterclockwise as we travel to the right. The $\circ$ will be the vertices of the hexagon.
The method generalizes to $k$-gons in $n$-gons.
Number of triangulations of convex n-gon
is the (n − 2)
nd Catalan number. This is maximum possible number of triangulations.
Let's consider following n-gon
:
(n, 0), (0, 0), (1, 1), (2, 4), ..., (i, i^2), ..., (n - 2, (n - 2)^2).
All vertices of the polygon except first belong to parabola.
Each triangulation of n-gon
has n - 3
diagonals.
The only convex vertices are first, second and last. Any diagonal with both ends on the parabola is invalid (lies outside of polygon). So we have only n - 3
valid diagonals connecting vertices: (1, 3), (1, 4), ..., (1, n - 1)
. These diagonals make up one and only one triangulation.
Best Answer
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