ネックレス多項式

組合せ数学において、ネックレス多項式、あるいはモローのネックレス計数関数は、C. モロー ( 1872 ) によって導入され、α 色の利用可能な色からn色のビーズを選び、周期的に配置するネックレスの個数を数える。通常のグラフ彩色問題とは異なり、ネックレスは非周期的（部分列の繰り返しではない）と仮定し、回転（ネックレスの周りでビーズを回転させても同じネックレスとして数える）まで数えるが、反転（ビーズの順序を逆にすると別のネックレスとして数える）までは数えない。この計数関数は、自由リー代数の次元と有限体上の既約多項式の個数も記述する。

意味

ネックレス多項式は、 変数に関する多項式の族であり、 M（α、n）{\displaystyle M(\alpha,n)}α{\displaystyle \alpha}

αn ＝ ∑d|ndM（α、d）。{\displaystyle \alpha ^{n}\ =\ \sum _{d\,|\,n}d\,M(\alpha ,d).}

メビウス反転により、これらは次のように与えられる。

M（α、n） ＝ 1n∑d|nμ（nd）αd、{\displaystyle M(\alpha ,n)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)\alpha ^{d},}

ここで、 は古典的なメビウス関数です。 μ{\displaystyle \mu}

一般ネックレス多項式または一般ネックレスカウント関数と呼ばれる密接に関連するファミリーは次のとおりです。

北（α、n） ＝ ∑d|nM（α、d） ＝ 1n∑d|nφ（nd）αd、{\displaystyle N(\alpha ,n)\ =\ \sum _{d\,|\,n}M(\alpha ,d)\ =\ {\frac {1}{n}}\sum _{d\,|\,n}\varphi \!\left({n \over d}\right)\alpha ^{d},}

ここで、 はオイラーのトーティエント関数です。 φ{\displaystyle \varphi }

アプリケーション

ネックレス多項式は次のようになります。 M（α、n）{\displaystyle M(\alpha,n)}

  • 非周期ネックレス（またはリンドン語）の数。これは、 α色の利用可能な色を持つn個の色付きビーズを周期的に配置したものです。2つのネックレスは、回転（反射は考慮しない）によって関連している場合、等しいとみなされます。非周期とは、回転対称性がなく、 n個の異なる回転を持つネックレスを指します。同様に、周期的なネックレスも含めたネックレスの数を示します。これはポリア理論を用いて簡単に計算できます。北（α、n）{\displaystyle N(\alpha,n)}
  • α生成子上の自由リー代数のn次成分の次元（「ウィットの公式」[ 1 ] ）、あるいはそれと同値で長さnのホール語の数。同様に、自由ジョルダン代数のn次成分の次元は、北（α、n）{\displaystyle N(\alpha,n)}
  • α個の元を持つ有限体上のn次モニック既約多項式の個数（ が素数 のべき乗である場合）。同様に、は素数（既約 のべき乗）である多項式の個数である。α＝pd{\displaystyle \alpha =p^{d}}北（α、n）{\displaystyle N(\alpha,n)}
  • 円分恒等式の指数: 。11−αz ＝ ∏j＝1∞（11−zj）M（α、j）{\displaystyle \textstyle {1 \over 1-\alpha z}\ =\ \prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{\!M(\alpha ,j)}}

これらの様々なタイプのオブジェクトはすべて同じ多項式で数えられるが、それらの正確な関係は不明である。例えば、既約多項式とリンドン語の間には標準的な一対一関係は存在しない。 [ 2 ]しかし、次のように非標準的な一対一関係が存在する。α個の元を持つ体F上の任意のn次モニック既約多項式に対して、その根は元を持つガロア拡大体Lに存在する。LのF基底（正規基底）となるような元を選ぶことができる。ここでσはフロベニウスの自己同型である。すると、関数の同値類として見なされるネックレスを既約多項式αn{\displaystyle \alpha^{n}}×∈L{\displaystyle x\in L}{×、σ×、。。。、σn−1×}{\displaystyle \{x,\sigma x,...,\sigma ^{n-1}x\}}σy＝yα{\displaystyle \sigma y=y^{\alpha }}f:{1、。。。、n}→F{\displaystyle f:\{1,...,n\}\rightarrow F}

ϕ（T）＝（T−y）（T−σy）⋯（T−σn−1y）∈F[T]{\displaystyle \phi (T)=(Ty)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F[T]} のために 。y＝f（1）×+f（2）σ×+⋯+f（n）σn−1×{\displaystyle y=f(1)x+f(2)\sigma x+\cdots +f(n)\sigma ^{n-1}x}

fの異なる巡回並べ替え、つまり同じネックレス同値類の異なる代表は、 の因子の巡回並べ替えを生み出すので、この対応は明確に定義されている。[ 3 ]ϕ（T）{\displaystyle \phi (T)}

MとNの関係

MとNの多項式は、定数として 扱われる算術関数のディリクレ畳み込みによって簡単に関連付けられます。f（n）∗グラム（n）{\displaystyle f(n)*g(n)}α{\displaystyle \alpha}

  • Mの式は次のようになる。nM（n）＝μ（n）∗αn{\displaystyle n\,M(n)\,=\,\mu (n)*\alpha ^{n}}
  • Nの式は となります。nN(n)=φ(n)∗αn=n∗μ(n)∗αn{\displaystyle n\,N(n)\,=\,\varphi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}}
  • それらの関係は または と等価です。これは、関数 が完全に乗法であるためです。N(n)=1∗M(n){\displaystyle N(n)\,=\,1*M(n)}nN(n)=n∗(nM(n)){\displaystyle n\,N(n)\,=\,n*(n\,M(n))}f(n)=n{\displaystyle f(n)=n}

これらのうち 2 つは 3 つ目を意味します。例:

n∗μ(n)∗αn=nN(n)=n∗(nM(n))⟹μ(n)∗αn=nM(n){\displaystyle n*\mu (n)*\alpha ^{n}\,=\,n\,N(n)\,=\,n*(n\,M(n))\quad \Longrightarrow \quad \mu (n)*\alpha ^{n}=n\,M(n)}

ディリクレ代数における消去によって。

例

M(1,n)=0 if n>1M(α,1)=αM(α,2)=12(α2−α)M(α,3)=13(α3−α)M(α,4)=14(α4−α2)M(α,5)=15(α5−α)M(α,6)=16(α6−α3−α2+α)M(α,p)=1p(αp−α) if p is primeM(α,pN)=1pN(αpN−αpN−1) if p is prime{\displaystyle {\begin{aligned}M(1,n)&=0{\text{ if }}n>1\\[6pt]M(\alpha ,1)&=\alpha \\[6pt]M(\alpha ,2)&={\tfrac {1}{2}}(\alpha ^{2}-\alpha )\\[6pt]M(\alpha ,3)&={\tfrac {1}{3}}(\alpha ^{3}-\alpha )\\[6pt]M(\alpha ,4)&={\tfrac {1}{4}}(\alpha ^{4}-\alpha ^{2})\\[6pt]M(\alpha ,5)&={\tfrac {1}{5}}(\alpha ^{5}-\alpha )\\[6pt]M(\alpha ,6)&={\tfrac {1}{6}}(\alpha ^{6}-\alpha ^{3}-\alpha ^{2}+\alpha )\\[6pt]M(\alpha ,p)&={\tfrac {1}{p}}(\alpha ^{p}-\alpha )&{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha ,p^{N})&={\tfrac {1}{p^{N}}}(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})&{\text{ if }}p{\text{ is prime}}\end{aligned}}}

長さ0から始まる整数列はα=2{\displaystyle \alpha =2}

1、2、1、2、3、6、9、18、30、56、99、186、335、…（OEISのシーケンスA001037）

アイデンティティ

多項式はメトロポリスとロータによって与えられた様々な組み合わせ恒等式に従います。

M(αβ,n)=∑lcm⁡(i,j)=ngcd(i,j)M(α,i)M(β,j),{\displaystyle M(\alpha \beta ,n)=\sum _{\operatorname {lcm} (i,j)=n}\gcd(i,j)M(\alpha ,i)M(\beta ,j),}

ここで「gcd」は最大公約数、「lcm」は最小公倍数です。より一般的には、

M(αβ⋯γ,n)=∑lcm⁡(i,j,…,k)=ngcd(i,j,⋯,k)M(α,i)M(β,j)⋯M(γ,k),{\displaystyle M(\alpha \beta \cdots \gamma ,n)=\sum _{\operatorname {lcm} (i,j,\ldots ,k)=n}\gcd(i,j,\cdots ,k)M(\alpha ,i)M(\beta ,j)\cdots M(\gamma ,k),}

これはまた次のことを意味します:

M(βm,n)=∑lcm⁡(j,m)=nmjnM(β,j).{\displaystyle M(\beta ^{m},n)=\sum _{\operatorname {lcm} (j,m)=nm}{\frac {j}{n}}M(\beta ,j).}

参考文献

  1. ^ Lothaire, M. (1997).単語の組合せ論. 数学とその応用百科事典. 第17巻. Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, JE; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, MP; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Roger Lyndonによる序文（第2版）. Cambridge University Press . pp. 79, 84. ISBN 978-0-521-59924-5。MR  1475463。Zbl  0874.20040。
  2. ^ エイミー・グレン（2012）リンドン語の組合せ論、メルボルン講演
  3. ^ アダルベルト・ケルバー（1991）有限群作用による代数的組合せ論、 [1]
「 https://en.wikipedia.org/w/index.php?title=Necklace_polynomial&oldid=1319423579」より取得