How to use the necklace and bracelet count calculator
- Enter the number of beads around the loop and the number of colors.
- Read the count of necklaces, where turning the loop gives the same necklace.
- Read the count of bracelets, where turning and flipping the loop over both give the same bracelet.
- For small cases, scan the list of every necklace, written from its smallest rotation.
Formula
Necklaces = (1 / n) x sum over divisors d of n of phi(d) k^(n / d)
Bracelets, n odd: (necklace sum + n k^((n + 1) / 2)) / (2n)
Bracelets, n even: (necklace sum + (n / 2)(k^(n / 2) + k^(n / 2 + 1))) / (2n)
Aperiodic necklaces = (1 / n) x sum of mu(d) k^(n / d)
Here the necklace sum is the sum in the first line before dividing by n. phi is Euler's totient function and mu is the Moebius function. The method is Burnside's lemma: average the number of colorings each turn or flip leaves unchanged.
Small loops and a larger one
With 4 beads and 3 colors there are 3^4 = 81 colorings of fixed positions, but only 24 necklaces and 21 bracelets. Of the 24 necklaces, 18 never repeat when turned. With 6 beads and 2 colors the counts are 14 necklaces and 13 bracelets, and 8 beads in 3 colors give 834 necklaces and 498 bracelets.
12 beads in 4 colors give 1,398,500 necklaces and 704,370 bracelets, out of 16,777,216 fixed colorings. For 5 beads in 3 colors the answers are 51 necklaces and 39 bracelets.
Necklace or bracelet
A necklace can be rotated but not flipped over, so a pattern and its mirror image count separately unless one is a rotation of the other. A bracelet can be rotated and also flipped, so mirror images collapse into one. That is why bracelets are always fewer than or equal to necklaces.
For arrangements in a row instead of a loop see the multiset permutation calculator and the combinations and permutations calculator. To plan real beads, the bead strand calculator finds lengths and counts.
The list and the check
For small cases the page builds every necklace in dictionary order with the FKM algorithm, writes each one from its smallest rotation, and marks which of them are also the smallest representative of their mirror pair. The counts from that list are shown next to the formulas and always agree.
Assumptions and limits
- Beads of one color are identical and positions are around a circle with no clasp or marked starting point.
- The number of beads and colors each go up to 100. Counts are exact whole numbers, however large.
- Lists appear only when there are at most 300,000 colorings and 4,000 necklaces, and show the first 200 rows.
- The aperiodic count excludes patterns that repeat when turned, such as ABAB.
Frequently asked questions
How many different necklaces can you make with n beads and k colors?
Use the Burnside formula: add phi(d) k^(n/d) over the divisors d of n, then divide by n. For 4 beads and 3 colors that gives (81 + 9 + 6) / 4 = 24.
What is the difference between a necklace and a bracelet?
A necklace is counted up to rotation only. A bracelet is counted up to rotation and reflection, so it can be flipped over. 4 beads in 3 colors make 24 necklaces and 21 bracelets.
Why is the count smaller than k to the power n?
Many of the k^n colorings are the same loop seen from a different starting bead. Dividing out those rotations, and for bracelets the flips, leaves the truly different patterns.
What does aperiodic mean?
An aperiodic or primitive necklace does not repeat itself when turned by less than a full circle. ABAB repeats after two beads, so it is periodic, while AABB is not.