0
$\begingroup$

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 ?

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ Reworded: How many necklaces and bracelets (necklaces for part b and bracelets for part c) of length $p$ with $p$ prime can be made with beads of two possible colors such that there are at least three beads of the first color used. $\endgroup$ – JMoravitz Feb 5 '20 at 19:47
  • 1
    $\begingroup$ Almost exactly the same question was posted just a week ago but then deleted when I answered it. a) Does this happen to be from an ongoing contest? If so, are you aware of the contest problem policy? b) If it isn't, and I post an answer, do you promise not to delete the question? :-) $\endgroup$ – joriki Feb 5 '20 at 19:47
  • $\begingroup$ @joriki it is not a contest problem. I haven't seen the other post / don't see why it was deleted. This is a problem from a university class :) $\endgroup$ – Student_514 Feb 5 '20 at 19:51
1
$\begingroup$

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

$\endgroup$

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.