α色の利用可能な色からn色のビーズを選んだネックレスの数を数えます。
組合せ 数学 において、 ネックレス多項式 、あるいは モローのネックレス計数関数は、 C. モロー (1872) によって導入され、 α 色の利用可能な色から選ばれた n色のビーズが周期的に並べられた異なるネックレスの数を数える。通常の グラフ彩色 問題 とは異なり、ネックレスは非周期的 (繰り返し部分列で構成されていない) であると想定され、回転まで (ネックレスの周りでビーズを回転させても同じネックレスとして数える)、反転はしない (ビーズの順序を逆にすると別のネックレスとして数える) まで数えられる。この計数関数は、自由リー代数の次元と有限体上の既約多項式の個数も記述する。
意味 ネックレス多項式は、 変数の多項式の族であり 、
ま （ α 、 ん ）
{\displaystyle M(\alpha,n)}
α
{\displaystyle \alpha}
α
ん
=
∑
d
|
ん
d ま （ α 、 d ） 。
{\displaystyle \alpha ^{n}\ =\ \sum _{d\,|\,n}d\,M(\alpha ,d).}
メビウス反転 により、 これらは次のように表される。
ま （ α 、 ん ）
=
1 ん
∑
d
|
ん
μ
（
ん d
）
α
d
、
{\displaystyle M(\alpha ,n)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)\alpha ^{d},}
ここで、 は古典的な メビウス関数 です 。
μ
{\displaystyle \mu}
一般ネックレス多項式 または 一般ネックレスカウント関数 と呼ばれる密接に関連するファミリーは次のとおり です。
いいえ （ α 、 ん ）
=
∑
d
|
ん
ま （ α 、 d ）
=
1 ん
∑
d
|
ん
φ
（
ん d
）
α
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}
アプリケーション ネックレス多項式 とは 次のようになります。
ま （ α 、 ん ）
{\displaystyle M(\alpha,n)}
いいえ （ α 、 ん ）
{\displaystyle N(\alpha,n)}
非周期ネックレス （または同等の リンドンワード ）の数。 これは、 α 色の 利用可能な色を持つ n 色のビーズを周期的に配置したものです。2 つのこのようなネックレスは、回転（反射は考慮しない）によって関連している場合、等しいとみなされます。 非周期と は、回転対称性がなく、 n つ の異なる回転を持つネックレスを指します。同様に、は 周期的なネックレスも含めたネックレスの数を示します。これは、 ポリア理論を 使用して簡単に計算できます。
いいえ （ α 、 ん ）
{\displaystyle N(\alpha,n)}
α 生成子上の 自由リー代数 の次数 n 成分の次元 （「ウィットの公式」 [1] ）、またはそれと同等の長さ nの ホール語 の数 。それに対応して、自由 ジョルダン代数の次数 n 成分 の次元となるはずである 。
いいえ （ α 、 ん ）
{\displaystyle N(\alpha,n)}
α 個の元を持つ 有限体 上の n 次単項既約多項式の数 ( が素数ベキの場合)。同様に、は 素数 (既約のベキ) である多項式の数です。
α =
p
d
{\displaystyle \alpha =p^{d}}
いいえ （ α 、 ん ）
{\displaystyle N(\alpha,n)}
円分等式 の指数 : 。
1
1 − α ず
=
∏
じゅう = 1
∞
（
1
1 −
ず
じゅう
）
ま （ α 、 じゅう ）
{\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 基底 ( 正規基底 ) となる ような 元を選ぶことができる。ここで σは フロベニウス自己同型 である 。すると、関数 の同値類として見たネックレスを 既約多項式
α
ん
{\displaystyle \alpha^{n}}
x ∈ ら
{\displaystyle x\in L}
{ x 、 σ x 、 。 。 。 、
σ
ん − 1
x }
{\displaystyle \{x,\sigma x,...,\sigma ^{n-1}x\}}
σ ええ =
ええ
α
{\displaystyle \sigma y=y^{\alpha }}
ふ : { 1 、 。 。 。 、 ん } → ふ
{\displaystyle f:\{1,...,n\}\rightarrow F}
ϕ （ T ） = （ T − ええ ） （ T − σ ええ ） ⋯ （ T −
σ
ん − 1
ええ ） ∈ ふ [ T ]
{\displaystyle \phi (T)=(Ty)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F[T]}
のために 。
ええ = ふ （ 1 ） x + ふ （ 2 ） σ x + ⋯ + ふ （ ん ）
σ
ん − 1
x
{\displaystyle y=f(1)x+f(2)\sigma x+\cdots +f(n)\sigma ^{n-1}x}
f の異なる巡回再配置 、つまり同じネックレス同値類の異なる代表は、 の因子の巡回再配置を生み出す ので、この対応は明確に定義されます。 [3]
ϕ （ T ）
{\displaystyle \phi (T)}
関係 ま そして いいえ M と N の多項式は、 定数として
算術 関数の ディリクレ畳み込み によって簡単に関連付けることができます。
ふ （ ん ） ∗ グ （ ん ）
{\displaystyle f(n)*g(n)}
α
{\displaystyle \alpha}
M の式 は 、
ん ま （ ん ） = μ （ ん ） ∗
α
ん
{\displaystyle n\,M(n)\,=\,\mu (n)*\alpha ^{n}}
N の式は となります 。
ん いいえ （ ん ） = φ （ ん ） ∗
α
ん
= ん ∗ μ （ ん ） ∗
α
ん
{\displaystyle n\,N(n)\,=\,\varphi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}}
関数は 完全に乗法で あるため、 それらの関係は または それと同等になります 。
いいえ （ ん ） = 1 ∗ ま （ ん ）
{\displaystyle N(n)\,=\,1*M(n)}
ん いいえ （ ん ） = ん ∗ （ ん ま （ ん ） ）
{\displaystyle n\,N(n)\,=\,n*(n\,M(n))}
ふ （ ん ） = ん
{\displaystyle f(n)=n}
これらのうち 2 つが 3 つ目を意味します。例:
ん ∗ μ （ ん ） ∗
α
ん
= ん いいえ （ ん ） = ん ∗ （ ん ま （ ん ） ） ⟹ μ （ ん ） ∗
α
ん
= ん ま （ ん ）
{\displaystyle n*\mu (n)*\alpha ^{n}\,=\,n\,N(n)\,=\,n*(n\,M(n))\quad \Longrightarrow \クワッド \mu (n)*\alpha ^{n}=n\,M(n)}
ディリクレ代数における消去によって。
例
ま （ 1 、 ん ）
= 0
もし
ん > 1
ま （ α 、 1 ）
= α
ま （ α 、 2 ）
=
1 2
（
α
2
− α ）
ま （ α 、 3 ）
=
1 3
（
α
3
− α ）
ま （ α 、 4 ）
=
1 4
（
α
4
−
α
2
）
ま （ α 、 5 ）
=
1 5
（
α
5
− α ）
ま （ α 、 6 ）
=
1 6
（
α
6
−
α
3
−
α
2
+ α ）
ま （ α 、 p ）
=
1 p
（
α
p
− α ）
もし
p
素数である
ま （ α 、
p
いいえ
）
=
1
p
いいえ
（
α
p
いいえ
−
α
p
いいえ − 1
）
もし
p
素数である
{\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 ）
アイデンティティ 多項式は、Metropolis & Rota によって与えられたさまざまな組み合わせ恒等式に従います。
M
(
α
β
,
n
)
=
∑
lcm
(
i
,
j
)
=
n
gcd
(
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
)
=
n
gcd
(
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
)
=
n
m
j
n
M
(
β
,
j
)
.
{\displaystyle M(\beta ^{m},n)=\sum _{\operatorname {lcm} (j,m)=nm}{\frac {j}{n}}M(\beta ,j).}
参考文献
^ 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 版)。 ケンブリッジ大学出版局 。pp. 79, 84。ISBN 978-0-521-59924-5 . MR 1475463. Zbl 0874.20040. ^
エイミー・グレン、(2012) リンドン語の組合せ論 、メルボルン講演 ^
アダルベルト・ケルバー（1991） 有限群作用による代数的組合せ論 、[1]
Moreau, C. (1872)、「Sur les permutations circulaires disdistines (個別の円順列について)」、 Nouvelles Annales de Mathématiques 、Série 2 (フランス語)、 11 : 309–31、 JFM 04.0086.01 メトロポリス、N. ; ロータ、ジャンカルロ (1983)、「ウィットベクトルとネックレス代数」、 数学の進歩 、 50 (2): 95–125、 doi : 10.1016/0001-8708(83)90035-X 、 ISSN 0001-8708、 MR 0723197、 Zbl 0545.05009 ロイテナウアー、クリストフ (1988)。 「循環と多項式の既約性」。 アン。 Sc.数学。ケベック州 。 12 (2): 275–285。 
![{\displaystyle \phi (T)=(Ty)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F[T]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbf842dde54703efe59e92be0782d577343182d7)
![{\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{ }}p{\text{ が素数の場合}}\\[6pt]M(\alpha ,p^{N})&={\tfrac {1}{p^{N}}}(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})&{\text{ }}p{\text{ が素数の場合}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/292126a531959390c96638c886930866d5120c4f)
