Necklace polynomial

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

\alpha^n = \sum_{d\,|\,n} d \, M(\alpha, d).

By Möbius inversion they are given by

 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]


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^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)
where "gcd" is greatest common divisor and "lcm" is least common multiple.

See also[edit]


  1. ^ a b Lothaire, M. (1997). Combinatorics on words. Encyclopedia of Mathematics and Its Applications 17. Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.). Cambridge University Press. pp. 79,84. ISBN 0-521-59924-5. MR 1475463. Zbl 0874.20040.