In combinatorial mathematics, the necklace polynomials, or (Moreau's) necklace-counting function are the polynomials M(α,n) in α such that
By Möbius inversion they are given by
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");
- 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 α.
- M(α,1) = α
- M(α,2) = (α2 − α)/2
- M(α,3) = (α3 − α)/3
- M(α,4) = (α4 − α2)/4
- M(α,5) = (α5 − α)/5
- M(α,6) = (α6 − α3 − α2 + α)/6
- M(α,pn) = (αpn − αpn − 1)/pn for p prime
- where (i,j) is the highest common factor of i and j and [i,j] is their least common multiple.
- 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.
- Moreau, C. (1872), "Sur les permutations circulaires distinctes (On distinct circular permutations)", Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale, Sér. 2 (in French) 11: 309–31, JFM 04.0086.01
- Metropolis, N.; Rota, Gian-Carlo (1983), "Witt vectors and the algebra of necklaces", Advances in Mathematics 50 (2): 95–125, doi:10.1016/0001-8708(83)90035-X, ISSN 0001-8708, MR 723197, Zbl 0545.05009