# How many circular necklaces can be made with the length of p (a prime number), that can be created by connecting n different types of beads together

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.

• Wher does the number $360$ come from? Jun 15 '19 at 12:05
• Are necklaces that are mirror images identical? Because one can flip a necklace in 3-dimensional space... Jun 15 '19 at 12:33
• See also the necklace-counting proof of Fermat's little theorem. Jun 15 '19 at 12:38

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)$$

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. But even these need not all be different. Assume $$R^i(a)=R^j(a)$$ for some $$i,j$$ with $$0\le i. 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).

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.