In combinatorial mathematics, the necklace polynomials, or (Moreau's) necklace-counting function are the polynomials M(α,n) in α such that
α
n
=
∑
d
|
n
d
M
(
α
,
d
)
.
By Möbius inversion they are given by
M
(
α
,
n
)
=
1
n
∑
d
|
n
μ
(
n
d
)
α
d
where μ is the classic Möbius function.
The necklace polynomials are closely related to the functions studied by C. Moreau (1872), 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 (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.);
the dimension of the degree n piece of the free Lie algebra on α generators ("Witt's formula");
the number of monic irreducible polynomials of degree n over a finite field with α elements (when α is a prime power);
the exponent in the cyclotomic identity;
The number of Lyndon words of length n in an alphabet of size α.
