In the technical combinatorial sense, an -ary necklace of length is a string of characters, each of possible types. Rotation is ignored, in the sense that is equivalent to for any .
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.