Necklace polynomial

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]

Values

Some of the polynomials include

{\begin{aligned}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)&=(\alpha ^{p}-\alpha )/p&{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha ,p^{N})&=(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})/p^{N}&{\text{ if }}p{\text{ is prime}}\\[6pt]\end{aligned}}

Identities

The polynomials obey various combinatorial identities, given by Metropolis & Rota:

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. More generally,

M(\alpha \beta \cdots \gamma ,n)=\sum _{\operatorname {lcm} (i,j,\cdots ,k)=n}\gcd(i,j,\cdots ,k)M(\alpha ,i)M(\beta ,j)\cdots M(\gamma ,k)

For common values, one has

M(\beta ^{m},n)=\sum _{\operatorname {lcm} (j,m)=nm}{\frac {j}{n}}M(\beta ,j)

Cyclotomic identity

The cyclotomic identity is:

{1 \over 1-\alpha z}=\prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{M(\alpha ,j)}

References

^ ^a ^b Lothaire, M. (1997). Combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 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" (PDF), Advances in Mathematics, 50 (2): 95–125, doi:10.1016/0001-8708(83)90035-X, ISSN 0001-8708, MR 0723197, Zbl 0545.05009

[L7984-1] Lothaire, M. (1997). Combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 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.

[1]

Values

Identities

Cyclotomic identity

See also

References