Necklace polynomial

Summary

In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by (txt), counts the number of distinct necklaces of $n$ colored beads chosen out of $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.