An 
-ary necklace of length 
is an equivalence class
of strings of 
characters, each of 
possible types, under cyclic
permutation, where 
and 
are positive
integers. Thus 
is equivalent to 
for 
.
In fixed necklaces, reversal of strings is respected, so they represent circular collections of beads in which the necklace
may not be picked up out of the plane (i.e., opposite orientations
are not considered equivalent). The number of fixed necklaces
of length 
composed of 
types of beads 
is given by
 |
(1)
|
where 
are the divisors
of 
with 
, 
,
..., 
, 
is the number of divisors
of 
, and 
is the totient function.
For free necklaces, opposite orientations (mirror images) are regarded as equivalent, so the necklace can be picked up out
of the plane and flipped over. The number 
of such necklaces composed of 
beads, each of 
possible colors, is given by
 |
(2)
|
For 
and 
an odd prime, this simplifies
to
 |
(3)
|
A table of the first few numbers of necklaces for 
and 
follows. Note that 
is larger than 
for 
. For 
, the necklace 110100 is inequivalent to its mirror
image 001011, accounting for the difference of 1 between 
and 
. Similarly, the two necklaces 0010110 and 0101110 are
inequivalent to their reversals, accounting for the difference of 2 between 
and 
.
 |  |  |  |
| Sloane | A000031 | A000029 | A027671 |
| 1 | 2 | 2 | 3 |
| 2 | 3 | 3 | 6 |
| 3 | 4 | 4 | 10 |
| 4 | 6 | 6 | 21 |
| 5 | 8 | 8 | 39 |
| 6 | 14 | 13 | 92 |
| 7 | 20 | 18 | 198 |
| 8 | 36 | 30 | 498 |
| 9 | 60 | 46 | 1219 |
| 10 | 108 | 78 | 3210 |
| 11 | 188 | 126 | 8418 |
| 12 | 352 | 224 | 22913 |
| 13 | 632 | 380 | 62415 |
| 14 | 1182 | 687 | 173088 |
| 15 | 2192 | 1224 | 481598 |
Ball and Coxeter (1987) consider the problem of finding the number of distinct arrangements of 
people in a ring such that no person
has the same two neighbors two or more times. For 8 people, there are 21 such arrangements.
