0
$\begingroup$

Given an unlimited number of beads of n different types, how many circular necklaces are there, with the length of p (a prime number), that can be created by connecting the beads together?

Note that two necklaces are identical if we can get one of the necklaces by rounding the other necklace.

I have an approach; First we count how many necklaces there to exist with the length of p and of n different beads and then we divide all the possibilities by the number of equivalence classes. I believe that there are 360/p different equivalence classes.

I am not certain whether this is the right approach, and also is this the right number of equivalence classes?

Disclaimer: I am asking this question for a friend who does not know how to use this site and cannot formulate a question that is comprehensible in English, so I apologize for any vague point.

$\endgroup$
3
2
$\begingroup$

This problem is well-known in combinatorics, you can look for example here: https://en.wikipedia.org/wiki/Necklace_(combinatorics)

The number of necklaces with $m$ beads and $n$ colors is $\frac{1}{m}\sum_{d|m}\phi(m/d)n^d$, where the sum is over all $d$ dividing $m$, and $\phi $ is Euler's totient function. When $m=p$ is a prime the sum has only two terms and it simplifies to $\frac{1}{p}(n^p+n p-n)$

$\endgroup$
1
$\begingroup$

If we first ignore the equivalences, we choose among $n$ types for each of $p$ bead positions $0,1,\ldots,p-1$. This gives us $n^p$ distinct necklaces that we can describe as $p$-tuples $a=(a_0,a_1,\ldots,a_{p-1})$ where $a_i\in\{0,2,\ldots,n-1\}$.

For a necklace $a$ we define $R(a)=(a_1,a_2,\ldots,a_{p-1},a_0)$ as rotated (by one position) necklace. The equivalence class $[a]$ of a necklace $a$ is the set of all necklaces of the form $R^k(a)$, $k\in\Bbb Z$. How big is $[a]$? Clearly $R^p$ is the identity map, hence the equivalence consists really only of the $R^k(a)$, $0\le k<p$. But even these need not all be different. Assume $R^i(a)=R^j(a)$ for some $i,j$ with $0\le i<j<p$. Then with $d:=j-i$, we also have $a=R^d(a)$ as well as $a=R^{kd\bmod p}(a)$. As $d$ is not a multilple of $p$, there exists $k$ with $kd\bmod p=1$. It follows that $a=R(a)$ and then also $a=R^2(a)=R^3(a)=\ldots$, i.e., $[a]$ consists of $a$ only. We conclude that $[a]$ either consists of $p$ distinct necklaces or of only one necklace. Clearly, the latter happens precisely for the $n$ "constant" necklaces $(c,c,\ldots,c)$. So to count all equivalence clases, we count the $n$ constant necklaces and then note that the remaining $n^p-n$ necklaces come in groups of $p$. We end up with $$ n+\frac{n^p-n}p.$$ Incidentally, this expression must give an integer so that as a side-effect we have shown that $n^p-n$ is a multiple of $p$ if $n\in\Bbb N$ and $p$ is prime. (Fermat's little theorem).

$\endgroup$
1
$\begingroup$

The closure mechanism (with a ring and a spike) gives such necklaces a beginning and an end. Striping one bead after the other over the spike onto the necklace you have $p$ choices from $n$ types of beads, makes $n^p$ "different" necklaces.

When the necklace is closed the closure is not seen any more. This implies that the necklaces differing just by one of the $p$ rotations should be counted as the same. This leads to the conjecture that there are $N'={1\over p}n^p$ different necklaces. Now this $N'$ is (usually) not an integer. Where is the mistake?

There are $n$ special necklaces having all $p$ beads of the same color. Rotating such necklaces does not produce other necklaces and therefore overcounting. It follows that the correct number of different necklaces is $$N={1\over p}(n^p-n) + n\ .$$ This $N$ is an integer, by Fermat's little theorem.

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