In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by C. Moreau (1872), is the family of polynomials \( {\displaystyle M(\alpha ,n)} \) in the variable \( \alpha \) such that
\( {\displaystyle \alpha ^{n}\ =\ \sum _{d\,|\,n}d\,M(\alpha ,d).} \)
By Möbius inversion they are given by
\( {\displaystyle M(\alpha ,n)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)\alpha ^{d},} \)
where μ {\displaystyle \mu } \mu is the classic Möbius function.
A closely related family, called the general necklace polynomial or general necklace-counting function, is:
\( {\displaystyle N(\alpha ,n)\ =\ \sum _{d|n}M(\alpha ,d)\ =\ {\frac {1}{n}}\sum _{d\,|\,n}\phi \!\left({n \over d}\right)\alpha ^{d},} \)
where \( \phi is Euler's totient function.
Relations between M and N
The above formulas are easily related in terms of Dirichlet convolution of arithmetic functions \( {\displaystyle f(n)*g(n)} \) , regarding \( \alpha \) as a constant.
The formula for M gives \( {\displaystyle n\,M(n)\,=\,\mu (n)*\alpha ^{n}}, \)
The formula for N gives \( {\displaystyle n\,N(n)\,=\,\phi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}}. \)
Their relation gives \( {\displaystyle N(n)\,=\,1*M(n)} \) or equivalently \( {\displaystyle n\,N(n)\,=\,n*(n\,M(n))} \), since n is completely multiplicative.
Any two of these imply the third, for example:
\( {\displaystyle n*\mu (n)*\alpha ^{n}\,=\,n\,N(n)\,=\,n*(n\,M(n))\quad \Longrightarrow \quad \mu (n)*\alpha ^{n}=n\,M(n)} \)
by cancellation in the Dirichlet algebra.
Examples
\( {\displaystyle {\begin{array}{ccll}M(1,n)&=&0&{\text{ if }}n>1\\[6pt]M(\alpha ,1)&=&\alpha \\[6pt]M(\alpha ,2)&=&{\tfrac {1}{2}}(\alpha ^{2}-\alpha )\\[6pt]M(\alpha ,3)&=&{\tfrac {1}{3}}(\alpha ^{3}-\alpha )\\[6pt]M(\alpha ,4)&=&{\tfrac {1}{4}}(\alpha ^{4}-\alpha ^{2})\\[6pt]M(\alpha ,5)&=&{\tfrac {1}{5}}(\alpha ^{5}-\alpha )\\[6pt]M(\alpha ,6)&=&{\tfrac {1}{6}}(\alpha ^{6}-\alpha ^{3}-\alpha ^{2}+\alpha )\\[6pt]M(\alpha ,p)&=&{\tfrac {1}{p}}(\alpha ^{p}-\alpha )&{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha ,p^{N})&=&{\tfrac {1}{p^{N}}}(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})&{\text{ if }}p{\text{ is prime}}\end{array}}} \)
Identities
Main article: Necklace ring
The polynomials obey various combinatorial identities, given by Metropolis & Rota:
\( {\displaystyle 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,
\( {\displaystyle 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),} \)
which also implies:
\( {\displaystyle M(\beta ^{m},n)=\sum _{\operatorname {lcm} (j,m)=nm}{\frac {j}{n}}M(\beta ,j).} \)
Cyclotomic identity
Main article: Cyclotomic identity
\( {\displaystyle {1 \over 1-\alpha z}\ =\ \prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{M(\alpha ,j)}} \)
Applications
The necklace polynomials \( {\displaystyle M(\alpha ,n)} appear as:
The number of aperiodic necklaces (or equivalently Lyndon words) which can be made by arranging n colored beads having α available colors. Two such necklaces are considered equal if they are related by a rotation (but not a reflection). Aperiodic refers to necklaces without rotational symmetry, having n distinct rotations. The polynomials \( {\displaystyle N(\alpha ,n)} \) give the number of necklaces including the periodic ones: this is easily computed using Pólya theory.
The dimension of the degree n piece of the free Lie algebra on α generators ("Witt's formula"[1]). Here \( {\displaystyle N(\alpha ,n)} \) should be the dimension of the degree n piece of the corresponding free Jordan algebra.
The number of monic irreducible polynomials of degree n over a finite field with α elements (when \( {\displaystyle \alpha =p^{d}} \) is a prime power). Here \( {\displaystyle N(\alpha ,n)} \) is the number of polynomials which are primary (a power of an irreducible).
The exponent in the cyclotomic identity.
References
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 978-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 0723197, Zbl 0545.05009
Reutenauer, Christophe (1988). "Mots circulaires et polynomies irreductibles". Ann. Sc. Math. Quebec. 12 (2): 275–285.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
