Moreau's necklace-counting function
|
|
In combinatorial mathematics, Moreau's necklace-counting function
- <math>M(\alpha,n)={1\over n}\sum_{d\,|\,n}\mu\left({n \over d}\right)\alpha^d<math>
where μ is the classic Möbius function, counts the number of "necklaces" asymmetric under rotation (also called "Lyndon words") that can be made by arranging n beads the color of each of which is chosen from a list of α colors. One respect in which the word necklace may be misleading is that if one picks such a "necklace" up off the table and turns it over, thus reversing the roles of clockwise and counterclockwise, one gets a different "necklace", counted separately, unless the necklace is symmetric under such reflections.
This function is involved in the cyclotomic identity.
References
- C. Moreau. Sur les permutations circulaires distincts. Nouv. Ann. Math., volume 11, pages 309-314, 1872.
- Nicholas Metropolis & Gian-Carlo Rota. Witt Vectors and the Algebra of Necklaces. Advances in Mathematics, volume 50, number 2, pages 95-125, 1983.