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:
… excerpt ends here. Continue reading the full article.
