ネックレス多項式
(Necklace polynomial から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/02/16 07:38 UTC 版)
組合せ数学において、ネックレス多項式 (necklace polynomial) あるいは（モロー (Moreau) の）ネックレス数え上げ関数 (necklace-counting function) は、以下の式が成り立つような α の多項式 M (α, n) である。
メビウスの反転公式によって、ネックレス多項式は
となる。ここで μ は古典的なメビウス関数である。
ネックレス多項式は 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 (α, pn) = (αpn − αpn − 1)/pn, ただし p は素数。
- (i, j ) を i と j の最大公約数、[i, j ] を i と 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. . . .
- 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,
- Metropolis, N.; Rota, Gian-Carlo (1983), “Witt vectors and the algebra of necklaces”, Advances in Mathematics 50 (2): 95–125, , , ,
- ネックレス多項式のページへのリンク
