Necklace polynomial


In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by, is the 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.

Relations between ''M'' and ''N''

The above formulas are easily related in terms of Dirichlet convolution of arithmetic functions, regarding as a constant.
Any two of these imply the third, for example:
by cancellation in the Dirichlet algebra.

Examples

Identities

The polynomials obey various combinatorial identities, given by Metropolis & Rota:
where "gcd" is greatest common divisor and "lcm" is least common multiple. More generally,
which also implies:

Cyclotomic identity

Applications

The necklace polynomials appear as: