I am faced with the following problem:
Let p ≥ 3 be a prime number, and mark p points at equal distance on
the circumference of a circle like in the pictures below (where p =
7). We can trace polygons by choosing a certain amount of those points
as vertices, and connecting them with non-intersecting straight lines.
With three parts:
a) How many different polygons can we form if we consider that a different choice of vertices leads to a different polygon?
This is straightforward: you can have polygons with three vertices, 4 vertices […] up until p vertices, and the amount of polygons you can draw of a given number of vertices k is $p \choose k$. Hence the answer is ${p \choose 3} + {p \choose 4} + {…} + {p \choose p-1} + {p \choose p}$
b) How many different polygons can we form if we count all different rotations of the same polygon as a single polygon?
Well, any given polygon can be rotated up to $p-1$ times. Hence each polygon counted from a) is actually being counted 7 times. We adjust for this by dividing through the answer in a) by p, and get the answer as $\frac{p \choose 3}{p} + \frac{p \choose 4}{p} + {…} + \frac{p \choose p-1}{p} + \frac{p \choose p}{p} = \frac{p \choose 3}{p} + \frac{p \choose 4}{p} + {…} + \frac{p \choose p-2}{p} + 1 + 1$.
I think all the above makes sense, but I am struggling with the third part:
c) How many different polygons can we form if we count all isometric polygons (all rotations and reflections of the same polygon) as the same ?
And I don't know how to proceed from here. I'm guessing there has to be some pattern to the number of reflections+rotations that any polygon of k vertices has along p points. However, I've tried playing around with small examples and I can't seem to find any generalizable pattern, and I've been stumped for longer than I'd like to admit. Any help would be greatly appreciated.
Best Answer
The polygons are in correspondence with the subsets of the vertices with at least $3$ elements. Thus, as JMoravitz noted in a comment, this can be viewed as counting binary necklaces and bracelets of length $p$ with at least three beads of the first colour, where the first colour signifies a vertex that’s included and the second colour signifies a vertex that isn’t included in the polygon.
For part a), there is no symmetry to take into account, so the result is just $2^p-\binom p2-\binom p1-\binom p0$. (Your result is correct, you just didn't use the fact that $\sum_k\binom pk=2^k$, the total number of subsets of the set of $k$ vertices.)
For part b), with rotational symmetry, you failed to properly account for the fact that the polygon that includes all vertices has only one rotational equivalent, not $p$. Your final result is correct, but only because you replaced $\frac{\binom pp}p=\frac1p$ by $1$. If you count correctly, you have $2^p-\binom p2-\binom p1-\binom p0-\binom pp$ polygons that form classes of $p$ rotational equivalents each, and $\binom pp=1$ polygon that’s in a class of its own, so the total count is
$$ \frac{2^p-\binom p2-\binom p1-\binom p0-\binom pp}p+1=\frac{2^p-2}p-\frac{p+1}2\;. $$
For part c), with rotational and reflectional symmetry, it becomes easier to perform the count using Burnside’s lemma. The general result is given in the Wikipedia article linked to above. In your case, since $p$ is an odd prime, there are
\begin{eqnarray} B_2(p) &=& \frac12N_2(p)+\frac12\cdot2^{\frac{p+1}2} \\ &=& \frac12\cdot\frac1p\left(1\cdot2^p+(p-1)\cdot2^1\right)+2^{\frac{p-1}2} \\ &=& \frac{2^{p-1}-1}p+1+2^{\frac{p-1}2} \end{eqnarray}
binary bracelets. We need to subtract the $1$ bracelet with $0$ elements of the second colour, the $1$ bracelet with $1$ element of the second colour and the $\frac{p-1}2$ bracelets with $2$ elements of the second colour, so the number of polygons up to rotations and reflections is
$$ \frac{2^{p-1}-1}p+2^{\frac{p-1}2}-\frac{p+1}2\;. $$