ネックレス多項式 – Wikipedia

Posted on January 30, 2020 by lordneo

組合せ数学において、ネックレス多項式 (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) によって研究された関数と密接な関係にあるが、同じというわけではない。モローはネックレスの個数を数えたが、ネックレス多項式は非周期的なネックレスの個数を数える。

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

$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$ の最小公倍数として、

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