Necklace polynomial

In combinatorial mathematics, the necklace polynomials, or (Moreau's) necklace-counting function are the polynomials M(α,n) in α such that

${\displaystyle \alpha ^{n}=\sum _{d\,|\,n}d\,M(\alpha ,d).}$

By Möbius inversion they are given by

${\displaystyle M(\alpha ,n)={1 \over n}\sum _{d\,|\,n}\mu \left({n \over d}\right)\alpha ^{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"[1]);
• 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 α.[1]

Values

{\displaystyle {\begin{aligned}M(1,n)&=0{\text{ if }}n>1\\M(\alpha ,1)&=\alpha \\[6pt]M(\alpha ,2)&=(\alpha ^{2}-\alpha )/2\\[6pt]M(\alpha ,3)&=(\alpha ^{3}-\alpha )/3\\[6pt]M(\alpha ,4)&=(\alpha ^{4}-\alpha ^{2})/4\\[6pt]M(\alpha ,5)&=(\alpha ^{5}-\alpha )/5\\[6pt]M(\alpha ,6)&=(\alpha ^{6}-\alpha ^{3}-\alpha ^{2}+\alpha )/6\\[6pt]M(\alpha ,p)&=(\alpha ^{p}-\alpha )/p{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha ,p^{N})&=(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})/p^{N}{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha \beta ,n)&=\sum _{\operatorname {lcm} (i,j)=n}\gcd(i,j)M(\alpha ,i)M(\beta ,j)\end{aligned}}}
where "gcd" is greatest common divisor and "lcm" is least common multiple.