ネックレス多項式のソースを表示

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

:<math>\alpha^n = \sum_{d\,\mid\,n} d \, M(\alpha, d).</math>

[[メビウスの反転公式]]によって、ネックレス多項式は
: <math> M(\alpha,n) = {1\over n}\sum_{d\,\mid\,n}\mu\left({n \over d}\right)\alpha^d </math>

となる。ここで {{math|μ}} は古典的な[[メビウス関数]]である。

ネックレス多項式は {{harvs|txt|authorlink=Charles Paul Narcisse Moreau|first=C.|last=Moreau|year=1872}} によって研究された関数と密接な関係にあるが、同じというわけではない。モローはネックレスの個数を数えたが、ネックレス多項式は非周期的なネックレスの個数を数える。

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

* 色はそれぞれ {{math|&alpha;}} 色の中から選ばれる {{mvar|n}} 個のビーズを組み合わせて作ることのできる非周期的{{仮リンク|ネックレス (組み合わせ数学)|label=ネックレス|en|necklace (combinatorics)}}（{{仮リンク|リンドンワード|en|Lyndon word}}とも呼ばれる）の個数。（「ネックレス」という用語は誤解を招くかもしれない。ネックレスをテーブルから持ち上げて裏返すと、[[時計回り]]と反時計回りが逆になり、そのような操作で対称的でない限り、異なるネックレスとなり、別々に数えられるのである。）
* {{math|&alpha;}} 個の生成元上の[[自由リー代数]]の {{mvar|n}} 次のピースの次元（「ヴィットの公式」<ref name=L7984>{{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | others=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 | title=Combinatorics on words | edition=2nd | series=Encyclopedia of Mathematics and Its Applications | volume=17 | publisher=[[Cambridge University Press]] | year=1997 | isbn=0-521-59924-5 | zbl=0874.20040 | mr = 1475463 | pages=79,84 }}</ref>）
* （{{math|α}} が素数の冪であるとき）{{math|α}} 個の元からなる[[有限体]]上の {{mvar|n}} 次の[[既約多項式#体上の既約多項式|モニック既約多項式の個数]]
* {{仮リンク|円分恒等式|en|cyclotomic identity}}の指数
* サイズ {{math|α}} のアルファベットの長さ {{mvar|n}} の{{仮リンク|リンドンワード|en|Lyndon word}}の個数<ref name=L7984/>。

==値==

*{{math|1=''M'' (α, 1) = α}}
*{{math|1=''M'' (α, 2) = (α<sup>2</sup> − α)/2}}
*{{math|1=''M'' (α, 3) = (α<sup>3</sup> − α)/3}}
*{{math|1=''M'' (α, 4) = (α<sup>4</sup> − α<sup>2</sup>)/4}}
*{{math|1=''M'' (α, 5) = (α<sup>5</sup> − α)/5}}
*{{math|1=''M'' (α, 6) = (α<sup>6</sup> − α<sup>3</sup> − α<sup>2</sup> + α)/6}}
*{{math|1=''M'' (α, ''p''<sup>''n''</sup>) = (α<sup>''p''<sup>''n''</sup></sup> − α<sup>''p''<sup>''n'' − 1</sup></sup>)/''p''<sup>''n''</sup>}},　ただし {{mvar|p}} は素数。
*{{math|(''i'', ''j''&thinsp;)}} を {{mvar|i}} と {{mvar|j}} の[[最大公約数]]、{{math|[''i'', ''j''&thinsp;]}} を {{mvar|i}} と {{mvar|j}} の[[最小公倍数]]として、
::<math>M(\alpha\beta, n)=\sum_{[i,j]=n}(i,j)M(\alpha,i)M(\beta,j). </math>　

==関連項目==

*{{仮リンク|ネックレス環|en|Necklace ring}}

==参考文献==
{{reflist}}
*{{citation | last1=Moreau | first1=C. |authorlink=Charles Paul Narcisse Moreau | title=Sur les permutations circulaires distinctes (On distinct circular permutations) | url=http://www.numdam.org/item?id=NAM_1872_2_11__309_0 | language=French | jfm=04.0086.01 | year=1872 | journal=[[Nouvelles Annales de Mathématiques|Nouvelles annales de mathématiques, journal des candidats aux écoles polytechnique et normale]], Sér. 2 | volume=11 | pages=309–31}}
*{{Citation | last1=Metropolis | first1=N. | author1-link=Nicholas Metropolis | last2=Rota | first2=Gian-Carlo | author2-link=Gian-Carlo Rota | title=Witt vectors and the algebra of necklaces | doi=10.1016/0001-8708(83)90035-X | mr=723197 | zbl=0545.05009 | year=1983 | journal=Advances in Mathematics | issn=0001-8708 | volume=50 | issue=2 | pages=95–125}}

{{DEFAULTSORT:ねつくれすたこうしき}}
[[Category:組合せ論]]
[[Category:数学に関する記事]]