コンテンツにスキップ

ネックレス多項式

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

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

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 - α)/2$
$M (α, 3) = (α 3 - α)/3$
$M (α, 4) = (α 4 - α 2)/4$
$M (α, 5) = (α 5 - α)/5$
$M (α, 6) = (α 6 - α 3 - α 2 + α)/6$
$M (α, p n) = (α p n - α p n - 1)/ p n$ ,　ただし $p$ は素数。
$(i, j)$ を $i$ と $j$ の最大公約数、 $[i, j]$ を $i$ と $j$ の最小公倍数として、

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

　

関連項目

ネックレス環（英語版）

参考文献

^ ^a ^b 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. MR1475463. Zbl 0874.20040

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
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

「https://ja.wikipedia.org/w/index.php?title=ネックレス多項式&oldid=62972487」から取得