Necklace polynomial

In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by C. Moreau (1872), counts the number of distinct necklaces of

n

{\displaystyle n}

colored beads chosen out of

k

{\displaystyle k}

available colors, arranged in a cycle. Unlike the usual problem of graph coloring, the necklaces are assumed to be aperiodic (not composed from a repeated subsequence), 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 the dimensions in a free Lie algebra and the number of irreducible polynomials over a finite field.

Definition

The necklace polynomials are a family of polynomials

M

n

(

k

)

{\displaystyle M_{n}(k)}

in the variable

k

{\displaystyle k}

such that

k

n

=

∑

d

|

n

d

M

d

(

k

)

.

{\displaystyle k^{n}\ =\ \sum _{d\,|\,n}d\,M_{d}(k).}

By Möbius inversion they are given by

M

n

(

k

)

=

1

n

∑

d

|

n

μ

(

n

d

)

k

d

,

{\displaystyle M_{n}(k)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)k^{d},}

where

μ

{\displaystyle \mu }

is the classic Möbius function.

A closely related family, called the general necklace polynomial or general necklace-counting function, is:

N

n

(

k

)

=

∑

d

|

n

M

d

(

k

)

=

1

n

∑

d

|

n

φ

(

n

d

)

k

d

,

{\displaystyle N_{n}(k)\ =\ \sum _{d\,|\,n}M_{d}(k)\ =\ {\frac {1}{n}}\sum _{d\,|\,n}\varphi \!\left({n \over d}\right)k^{d},}

where

φ

{\displaystyle \varphi }

is Euler's totient function.

Applications

The necklace polynomials

M

n

(

k

)

{\displaystyle M_{n}(k)}

appear as:

The number of aperiodic necklaces (or equivalently Lyndon words), which are cyclic arrangements of

n

{\displaystyle n}

colored beads having

k

{\displaystyle k}

available colors. Two such necklaces are considered equal if they are related by a rotation (not considering reflections). Aperiodic refers to necklaces without rotational symmetry, having

n

{\displaystyle n}

distinct rotations. Correspondingly,

N

n

(

k

)

{\displaystyle N_{n}(k)}

gives the number of necklaces including the periodic ones: this is easily computed using Pólya theory.