Combinatorial Necklaces and Bracelets

A combinatorial necklace is a circle of n coloured beads, with up to k different colours.

If we think of a necklace as a string of n characters from an alphabet of size k, we can say that two strings are equivalent if one can be rotated to be the same as the other i.e. aabb = abba = bbaa = baab.

A bracelet is a necklace that can be turned over i.e. strings are equivalent under reversal e.g. abcd = dcba.

Below you can see all unique necklaces or bracelets given n and k.

n: k: bracelets

Total:

Further Reading

• To generate the necklaces, I used the “FKM algorithm” due to Fredricksen, Kessler and Maiorana.
• For the bracelets, I used the algorithm described in Joe Sawada’s Generating Bracelets in constant amortized time.
• Necklace on MathWorld.
• Necklace (combinatorics) on Wikipedia.
• Information on necklaces, unlabelled necklaces, Lyndon words, De Bruijn sequences.
• Pólya Counting I (PDF).

© Jason Davies 2012.