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...
  
  .