Moreau's necklace-counting function
Encyclopedia
In combinatorial
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 necklaces
    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...

     (also called Lyndon word
    Lyndon word
    In 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 algebra
    Free Lie algebra
    In 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 field
    Finite field
    In 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 word
    Lyndon word
    In 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 multiple
    Least common multiple
    In 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...

    .
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK