When I say that an $r$-sided simple (i.e., not self-intersecting) polygon is inscribed into an $n$-sided regular polygon, I mean that every vertex of the simple $r$-gon is also a vertex of the regular $n$-gon. Let $M(r,n)$ stand for the number of different simple $r$-gons that can be inscribed into a regular $n$-gon. What is the formula for $M(r,n)$? I assume that, if $P$ and $Q$ are two $r$-sided simple polygons, and $Q$ can be obtained from $P$ by means of a rotation, then $P=Q$. (Without this assumption, $M(r,n)$ would obviously be equal to ${n \choose r}$.)
I solved some small cases with Maple, obtaining results like $M(4,6)=3$, $M(5,7)=3$ and $M(7,12)=66$. These results suggest that, if $r$ and $n$ are relatively prime (their gcd is $1$), then $M(r,n)=\frac{1}{n}{n \choose r}$. Is this hypothesis true? And what is the formula for $M(r,n)$ in the case $gcd(r,n)>1$? For $r=4$ and $n=6$, the formula $M(r,n)=\frac{1}{n}{n \choose r}$ gives the result $\frac{1}{6}\cdot 15=\frac{5}{2}$, which is of course wrong. The result $M(4,6)=3$ can be seen even without Maple. Suppose that, during a counterclockwise tour, the vertices of the regular hexagon appear in the order $A$, $B$, $C$, $D$, $E$, $F$. Then the three inscribable quadrilaterals are $ADEF$, $ACEF$ and $ACDF$.
Best Answer
$$M(r, n) = \frac{1}{n} \sum_{d \,\mid\, \gcd(r,n)} \varphi(d) \binom{n/d}{r/d}$$ See OEIS A047996 for references.