Moreau's necklace-counting function
- Moreau's necklace-counting function
In combinatorial mathematics, Moreau's necklace-counting function
:
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.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Moreau — is a surname of French origin that may refer to: People Basil Anthony Marie Moreau (1799–1873), French priest Charles Paul Narcisse Moreau French soldier and mathematician (and possible chess player). Christophe Moreau (born 1971), French cyclist … Wikipedia
Necklace polynomial — In combinatorial mathematics, the necklace polynomials, or (Moreau s) necklace counting function are the polynomials M(α,n) in α such that By Möbius inversion they are given by where μ is the classic Möbius function. The necklace polynomials are… … Wikipedia
Necklace (combinatorics) — In combinatorics, a k ary necklace of length n is an equivalence class of n character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads of up to k different colors … Wikipedia
Necklace problem — The necklace problem is a problem in recreational mathematics, solved in the early 21st century. Contents 1 Formulation 2 Solution 3 References 4 See also … Wikipedia
Charles Paul Narcisse Moreau — Colonel Charles Paul Narcisse Moreau (born 1837 September 14, Paris, died 1916 July 6) was a French soldier. He was made a chevalier of the French Legion of Honor in 1872, and an officier in July 1893. Spinrad (2008a, 2008b) gave some… … Wikipedia
List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is … Wikipedia
List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… … Wikipedia
Cyclotomic identity — In mathematics, the cyclotomic identity states that where M is Moreau s necklace counting function, and μ(·) is the classic Möbius function of number theory. The name comes from the denominator, 1 − z j, which is the product of… … Wikipedia
Lyndon word — In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a certain type of string over an alphabet. Several equivalent definitions are possible.A k ary Lyndon word of length n is an n character string over an alphabet… … Wikipedia
