ネックレス多項式

組合せ数学において、ネックレス多項式 (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]。