ネックレス多項式

組合せ数学において、ネックレス多項式 (necklace polynomial) あるいは（モロー (Moreau) の）ネックレス数え上げ関数 (necklace-counting function) は、以下の式が成り立つような α の多項式 M (α, n) である。

${\displaystyle \alpha ^{n}=\sum _{d\,\mid \,n}d\,M(\alpha ,d).}$

メビウスの反転公式によって、ネックレス多項式は

${\displaystyle M(\alpha ,n)={1 \over n}\sum _{d\,\mid \,n}\mu \left({n \over d}\right)\alpha ^{d}}$

となる。ここで μ は古典的なメビウス関数である。

ネックレス多項式は C. Moreau (1872) によって研究された関数と密接な関係にあるが、同じというわけではない。モローはネックレスの個数を数えたが、ネックレス多項式は非周期的なネックレスの個数を数える。

ネックレス多項式は以下のように現れる。

• 色はそれぞれ α 色の中から選ばれる n 個のビーズを組み合わせて作ることのできる非周期的ネックレス（英語版）（リンドンワード（英語版）とも呼ばれる）の個数。（「ネックレス」という用語は誤解を招くかもしれない。ネックレスをテーブルから持ち上げて裏返すと、時計回りと反時計回りが逆になり、そのような操作で対称的でない限り、異なるネックレスとなり、別々に数えられるのである。）
• α 個の生成元上の自由リー代数の n 次のピースの次元（「ヴィットの公式」^[1]）
• （α が素数の冪であるとき）α 個の元からなる有限体上の n 次のモニック既約多項式の個数
• 円分恒等式（英語版）の指数
• サイズ α のアルファベットの長さ n のリンドンワード（英語版）の個数^[1]。

• M (α, 1) = α
• M (α, 2) = (α² − α)/2
• M (α, 3) = (α³ − α)/3
• M (α, 4) = (α⁴ − α²)/4
• M (α, 5) = (α⁵ − α)/5
• M (α, 6) = (α⁶ − α³ − α² + α)/6
• M (α, pⁿ) = (α^pn − α^{pn − 1})/pⁿ,　ただし p は素数。
• (i, j ) を i と j の最大公約数、[i, j ] を i と j の最小公倍数として、

${\displaystyle M(\alpha \beta ,n)=\sum _{[i,j]=n}(i,j)M(\alpha ,i)M(\beta ,j).}$　

• ネックレス環（英語版）

• Moreau, C. (1872), “Sur les permutations circulaires distinctes (On distinct circular permutations)” (French), Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale, Sér. 2 11: 309–31, JFM 04.0086.01, http://www.numdam.org/item?id=NAM_1872_2_11__309_0 
• 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, MR723197, Zbl 0545.05009