Moreau's necklace-counting function

From Wikipedia, the free encyclopedia

You have new messages (last change).

In combinatorial mathematics, Moreau's necklace-counting function

M(\alpha,n)={1\over n}\sum_{d\,|\,n}\mu\left({n \over d}\right)\alpha^d

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.

See also Lyndon word.

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../m/o/r/Moreau%27s_necklace-counting_function.html"