Necklace polynomial

In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by , counts the number of distinct necklaces of n colored beads chosen out of α available colors. The necklaces are assumed to be aperiodic (not consisting of repeated subsequences), and counted up to rotation (rotating the beads around the necklace counts as the same necklace), but without flipping over (reversing the order of the beads counts as a different necklace). This counting function also describes, among other things, the dimensions in a free Lie algebra and the number of irreducible polynomials over a finite field. The necklace polynomials are a family of polynomials in the variable such that By Möbius inversion they are given by where is the classic Möbius function. A closely related family, called the general necklace polynomial or general necklace-counting function, is: where is Euler's totient function. The necklace polynomials appear as: The number of aperiodic necklaces (or equivalently Lyndon words) which can be made by arranging n colored beads having α available colors. Two such necklaces are considered equal if they are related by a rotation (but not a reflection). Aperiodic refers to necklaces without rotational symmetry, having n distinct rotations. The polynomials give the number of necklaces including the periodic ones: this is easily computed using Pólya theory. The dimension of the degree n piece of the free Lie algebra on α generators ("Witt's formula"). Here should be the dimension of the degree n piece of the corresponding free Jordan algebra. The number of distinct words of length n in a Hall set. Note that the Hall set provides an explicit basis for a free Lie algebra; thus, this is the generalized setting for the above. The number of monic irreducible polynomials of degree n over a finite field with α elements (when is a prime power). Here is the number of polynomials which are primary (a power of an irreducible). The exponent in the cyclotomic identity.