Moreau's necklace-counting function
Encyclopedia
In combinatorial
mathematics, the necklace polynomials, or (Moreau's) necklace-counting function are the polynomials in α such that
By Möbius inversion they are given by
where is the classic Möbius function
.
The necklace polynomials are closely related to the functions studied by , though they are not quite the same: Moreau counted the number of necklaces, while necklace polynomials count the number of aperiodic necklaces.
The necklace polynomials appear as:
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics, the necklace polynomials, or (Moreau's) necklace-counting function are the polynomials in α such that
By Möbius inversion they are given by
where is the classic Möbius function
Möbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...
.
The necklace polynomials are closely related to the functions studied by , though they are not quite the same: Moreau counted the number of necklaces, while necklace polynomials count the number of aperiodic necklaces.
The necklace polynomials appear as:
- the number of aperiodic necklacesNecklace (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...
(also called Lyndon wordLyndon wordIn mathematics, in the areas of combinatorics and computer science, a Lyndon word is a string that is strictly smaller in lexicographic order than all of its rotations...
s) that can be made by arranging 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.); - the dimension of the degree piece of the free Lie algebraFree Lie algebraIn mathematics, a free Lie algebra, over a given field K, is a Lie algebra generated by a set X, without any imposed relations.-Definition:Given a set X, one can show that there exists a unique free Lie algebra L generated by X....
on generators - the number of monic irreducible polynomials of degree over a finite fieldFinite fieldIn abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
with elements (when is a prime power). - the exponent in the cyclotomic identity.
- The number of Lyndon wordLyndon wordIn mathematics, in the areas of combinatorics and computer science, a Lyndon word is a string that is strictly smaller in lexicographic order than all of its rotations...
s of length n in an alphabet of size α.
Values
for prime- where (i,j) is the highest common factor of i and j and [i,j] is their least common multipleLeast common multipleIn arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
.