群作用の軌道の数の公式
ポリア 列挙定理は、 レッドフィールド・ポリア定理 や ポリア計数 とも呼ばれ、 集合 に対する 群作用 の 軌道 の数に関する バーンサイドの補題 から派生し、最終的にはそれを一般化した 組合せ論 の定理である 。この定理は、 1927 年に J. ハワード・レッドフィールドによって初めて発表された。1937 年に ジョージ・ポリア によって独立に再発見され、ポリアはこれを多くの計数問題、特に 化合物 の列挙に適用することで、結果を大いに普及させた 。
ポリアの列挙定理は、 記号的組合せ論と 組合せ種 の理論に組み込まれています 。
簡略化された重み付けされていないバージョン X を 有限集合 とし 、 G を X の順列の群（または X に作用する有限対称群）とする 。 集合 X は 有限 の ビーズ 集合 を 表し 、 G は ビーズ 順列 の 選ば れ た群である。たとえば、 X が n 個 の ビーズを円形に並べた ネックレス である場合、 回転対称性 が関係するため G は 巡回群 C n である。一方、 X が n 個 の ビーズを円形に並べた ブレスレット である 場合、回転と 反射 が関係するため G は位数 2 nの 二面体群 D n である 。さらに、 Y が 色の有限集合（ビーズの色）であるため Y X が ビーズの色分けの集合であるとする（より正式には、 Y X は 関数の集合である ）。すると、群 G は Y X に作用する。ポリアの列挙定理は、ビーズの色分けの配列が G の 下で周回する軌道の数を次の式で
数える。
バツ → はい
{\displaystyle X\to Y}
|
はい
バツ
/
グ
|
=
1
|
グ
|
∑
グ ∈ グ
メートル
c （ グ ）
{\displaystyle \left|Y^{X}/G\right|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}}
ここで、 は色の数であり、 c ( g ) は、 X の順列として考えた場合の グループ要素 gの 循環 の数です 。
メートル =
|
はい
|
{\displaystyle m=|Y|}
完全版、加重版 より一般的でより重要な定理のバージョンでは、色も1つ以上の方法で重み付けされ、色の集合が有限の係数を持つ 生成関数 を持つ限り、色の数は無限になる可能性がある。一変量の場合、
ふ （ t ） =
ふ
0
+
ふ
1
t +
ふ
2
t
2
+ ⋯
{\displaystyle f(t)=f_{0}+f_{1}t+f_{2}t^{2}+\cdots }
は色のセットを生成する関数であり、 w ≥ 0 の各 整数 に対して重み wの色が f w 個存在します。多変量の場合、各色の重みは整数のベクトルであり、重みの各ベクトルを持つ色の数を集計する
生成関数 f ( t 1 , t 2 , ...)が存在します。
列挙定理では、 サイクル指数 と呼ばれる別の多変量生成関数が使用されます。
ず
グ
（
t
1
、
t
2
、 … 、
t
ん
） =
1
|
グ
|
∑
グ ∈ グ
t
1
c
1
（ グ ）
t
2
c
2
（ グ ）
⋯
t
ん
c
ん
（ グ ）
{\displaystyle Z_{G}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|G|}}\sum _{g\in G}t_{1}^{c_{1}(g)}t_{2}^{c_{2}(g)}\cdots t_{n}^{c_{n}(g)}}
ここで、 nは X の要素数であり 、 c k ( g )は X の順列としての 群要素 gの k サイクル数である 。
色の配置は、 集合 Y X （ここで、 Y は色の集合、 Y X は すべての関数 φ: X → Y の集合を表す ）に対する Gの作用の軌道である。このような配置の 重みは、 X 内のすべての xに対する φ( x ) の重みの合計として定義される。定理によれば、 重みによる色の配置の数の
生成関数 Fは次のように与えられる。
ふ （ t ） =
ず
グ
（ ふ （ t ） 、 ふ （
t
2
） 、 ふ （
t
3
） 、 … 、 ふ （
t
ん
） ）
{\displaystyle F(t)=Z_{G}(f(t),f(t^{2}),f(t^{3}),\ldots ,f(t^{n}))}
または多変量の場合:
ふ （
t
1
、
t
2
、 … ） =
ず
グ
（ ふ （
t
1
、
t
2
、 … ） 、 ふ （
t
1
2
、
t
2
2
、 … ） 、 ふ （
t
1
3
、
t
2
3
、 … ） 、 … 、 ふ （
t
1
ん
、
t
2
ん
、 … ） ） 。
{\displaystyle F(t_{1},t_{2},\ldots )=Z_{G}(f(t_{1},t_{2},\ldots ),f(t_{1}^{2},t_{2}^{2},\ldots ),f(t_{1}^{3},t_{2}^{3},\ldots ),\ldots ,f(t_{1}^{n},t_{2}^{n},\ldots )).}
先に示した簡略版に還元すると、 m 色あり 、すべての重みが0の場合、 f ( t ) = m となり、
|
はい
バツ
/
グ
|
= ふ （ 0 ） =
ず
グ
（ メートル 、 メートル 、 … 、 メートル ） =
1
|
グ
|
∑
グ ∈ グ
メートル
c （ グ ）
。
{\displaystyle \left|Y^{X}/G\right|=F(0)=Z_{G}(m,m,\ldots ,m)={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}.}
数え上げ木 (下記参照) と非環式分子の有名な応用では、「色付きビーズ」の配置は、実際には根付いた木の枝のような配置の配置です。したがって、色の生成関数 f は 配置の生成関数 F から導出され、ポリアの列挙定理は再帰式になります。
例
ネックレスとブレスレット
色付きキューブ 3次元の立方体の側面を m 色で着色する方法は、立方体を回転させるまで何通りあるでしょうか。立方体の回転群 Cは 、ビーズに相当する立方体の6つの側面に作用します。そのサイクル指数は
ず
Ｃ
（
t
1
、
t
2
、
t
3
、
t
4
） =
1 24
（
t
1
6
+ 6
t
1
2
t
4
+ 3
t
1
2
t
2
2
+ 8
t
3
2
+ 6
t
2
3
）
{\displaystyle Z_{C}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}\right)}
これは、立方体の 6 つの面における C の 24 個の要素のそれぞれの動作を分析することによって得られます。 詳細については、
ここを参照してください。
すべての色の重みを0とすると、
ふ （ 0 ） =
ず
Ｃ
（ メートル 、 メートル 、 メートル 、 メートル ） =
1 24
（
メートル
6
+ 3
メートル
4
+ 12
メートル
3
+ 8
メートル
2
）
{\displaystyle F(0)=Z_{C}(m,m,m,m)={\frac {1}{24}}\left(m^{6}+3m^{4}+12m^{3}+8m^{2}\right)}
さまざまなカラーリング。
3頂点と4頂点のグラフ m 頂点のグラフは 、色付きビーズの配列として解釈できます。 「ビーズ」の集合 X は 可能なエッジの集合であり、色の集合 Y = {黒、白} は存在する (黒) または存在しない (白) エッジに対応します。ポリア列挙定理を使用すると、固定数の頂点を持つ 同型 まで のグラフの数、またはこれらのグラフが持つエッジの数に応じた生成関数を計算できます。後者の目的では、黒または存在するエッジの重みは 1、存在しないまたは白のエッジの重みは 0 であると言えます。これが 色の集合の生成関数です。関連する対称群は、 m 文字の 対称 群 です。この群は、可能なエッジの集合 X に作用します。つまり、置換 φ は、エッジ {a、b} をエッジ {φ(a)、φ(b)} に変換します。これらの定義では、 m 個の頂点を持つグラフの同型クラスは、色付き配置の 集合 Y X に対するG の作用の軌道と同じであり 、グラフの辺の数は配置の重みに等しくなります。
（
メートル 2
）
{\displaystyle {\binom {m}{2}}}
ふ （ t ） = 1 + t
{\displaystyle f(t)=1+t}
グ =
S
メートル
、
{\displaystyle G=S_{m},}
3頂点上のすべてのグラフ 3頂点の非同型グラフ 3 つの頂点上の 8 つのグラフ (同型グラフを識別する前) が右側に示されています。グラフの同型クラスは 4 つあり、これも右側に示されています。
3辺の集合に作用する
群 S 3のサイクル指数は
ず
グ
（
t
1
、
t
2
、
t
3
） =
1 6
（
t
1
3
+ 3
t
1
t
2
+ 2
t
3
）
{\displaystyle Z_{G}(t_{1},t_{2},t_{3})={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{3}\right)}
（群の要素の作用のサイクル構造を調べることによって得られる。 ここを 参照）。したがって、列挙定理によれば、同型性までの3頂点グラフの生成関数は
ふ （ t ） =
ず
グ
（
t + 1 、
t
2
+ 1 、
t
3
+ 1
）
=
1 6
（
（ t + 1
）
3
+ 3 （ t + 1 ） （
t
2
+ 1 ） + 2 （
t
3
+ 1 ）
）
、
{\displaystyle F(t)=Z_{G}\left(t+1,t^{2}+1,t^{3}+1\right)={\frac {1}{6}}\left((t+1)^{3}+3(t+1)(t^{2}+1)+2(t^{3}+1)\right),}
これは次のように単純化される
ふ （ t ） =
t
3
+
t
2
+ t + 1.
{\displaystyle F(t)=t^{3}+t^{2}+t+1.}
したがって、0 ～ 3 個のエッジを持つグラフが 1 つ存在します。
4 つの頂点を持つグラフの同型クラス。 6辺の集合に作用する
群 S 4のサイクル指数は
ず
グ
（
t
1
、
t
2
、
t
3
、
t
4
） =
1 24
（
t
1
6
+ 9
t
1
2
t
2
2
+ 8
t
3
2
+ 6
t
2
t
4
）
{\displaystyle Z_{G}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}\right)}
（ こちらを 参照）したがって
ふ （ t ） =
ず
グ
（
t + 1 、
t
2
+ 1 、
t
3
+ 1 、
t
4
+ 1
）
=
（ t + 1
）
6
+ 9 （ t + 1
）
2
（
t
2
+ 1
）
2
+ 8 （
t
3
+ 1
）
2
+ 6 （
t
2
+ 1 ） （
t
4
+ 1 ）
24
{\displaystyle F(t)=Z_{G}\left(t+1,t^{2}+1,t^{3}+1,t^{4}+1\right)={\frac {(t+1)^{6}+9(t+1)^{2}(t^{2}+1)^{2}+8(t^{3}+1)^{2}+6(t^{2}+1)(t^{4}+1)}{24}}}
これは次のように単純化される
ふ （ t ） =
t
6
+
t
5
+ 2
t
4
+ 3
t
3
+ 2
t
2
+ t + 1.
{\displaystyle F(t)=t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{2}+t+1.}
これらのグラフは右側に表示されています。
根付き三分木 根付き 3 進 木 の集合 T 3 は、すべてのノード (または葉以外の頂点) が正確に 3 つの子 (葉またはサブツリー) を持つ根付き木で構成されます。小さな 3 進木が右側に示されています。n 個のノードを持つ根付き 3 進木は、次数が最大 3 の n 個の頂点を持つ根付き木と同等であることに注意してください ( 葉 を 無視した場合)。一般に、2 つの根付き木は、そのノードの子を並べ替えることで一方から他方を取得できる場合に同型です。言い換えると、ノードの子に作用するグループは対称グループ S 3 です。このような 3 進木の重みは、ノード (または葉以外の頂点) の数であると定義されます。
0、1、2、3、4 ノード (= 非リーフ頂点) 上のルート付き 3 項ツリー。ルートは青で表示され、リーフは表示されません。各ノードには、その子の数が 3 になるようにリーフが 1 つあります。 根付き三分木は、葉またはノードのいずれかである再帰オブジェクトとして見ることができ、その子は3つの根付き三分木です。これらの子はビーズと同等であり、 それらに作用する
対称群 S 3のサイクル指数は
ず
S
3
（
t
1
、
t
2
、
t
3
） =
t
1
3
+ 3
t
1
t
2
+ 2
t
3
6
。
{\displaystyle Z_{S_{3}}(t_{1},t_{2},t_{3})={\frac {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.}
ポリア列挙定理は、根付き3分木の再帰構造を、ノード数による根付き3分木の生成関数F(t)の関数方程式に変換する。これは、ノード数で重み付けされた根付き3分木を持つ3つの子を「色付け」することで実現され、色生成関数は次のように与えられ、 列挙定理により次のように与えられる。
ふ （ t ） = ふ （ t ）
{\displaystyle f(t)=F(t)}
ふ （ t
）
3
+ 3 ふ （ t ） ふ （
t
2
） + 2 ふ （
t
3
）
6
{\displaystyle {\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}}
根付き三分木の生成関数として、ノード数より1少ない重み（子の重みの合計は根を考慮しないため）が付けられ、
ふ （ t ） = 1 + t ⋅
ふ （ t
）
3
+ 3 ふ （ t ） ふ （
t
2
） + 2 ふ （
t
3
）
6
。
{\displaystyle F(t)=1+t\cdot {\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}.}
これは、 n 個のノードを持つ根付き 3 値木の 数 t n に対する次の再帰式に相当します。
t
0
= 1
t
ん + 1
=
1 6
（
∑
1つの + b + c = ん
t
1つの
t
b
t
c
+ 3
∑
1つの + 2 b = ん
t
1つの
t
b
+ 2
∑
3 1つの = ん
t
1つの
）
{\displaystyle {\begin{aligned}t_{0}&=1\\t_{n+1}&={\frac {1}{6}}\left(\sum _{a+b+c=n}t_{a}t_{b}t_{c}+3\sum _{a+2b=n}t_{a}t_{b}+2\sum _{3a=n}t_{a}\right)\end{aligned}}}
ここで、 a 、 b 、 cは 負でない整数です。
最初のいくつかの値 は
t
ん
{\displaystyle t_{n}}
1、1、1、2、4、8、17、39、89、211、507、1238、3057、7639、19241（ OEIS の配列 A000598 ）。
定理の証明 ポリア列挙定理の簡略化された形式は バーンサイドの補題 から得られます。バーンサイドの補題は、彩色の軌道の数は、 すべての順列 g に対する G の順列 g によって 固定 された の 要素の数の平均であると述べています。定理の重み付きバージョンは、重み付き列挙に対するバーンサイドの補題の洗練された形式を除いて、本質的に同じ証明を持ちます。異なる重みの軌道にバーンサイドの補題を個別に適用することは同等です。
はい
バツ
{\displaystyle Y^{X}}
より明確な表記のため、 をの生成関数 f の変数とします 。重みのベクトル が与えられたとき 、を f の対応する単項式項とします 。バーンサイドの補題を重み の軌道に適用すると 、この重みの軌道の数は
x
1
、
x
2
、 …
{\displaystyle x_{1},x_{2},\ldots }
はい
{\displaystyle Y}
ω
{\displaystyle \omega}
x
ω
{\displaystyle x^{\omega}}
ω
{\displaystyle \omega}
1
|
グ
|
∑
グ ∈ グ
|
（
はい
バツ
）
ω 、 グ
|
{\displaystyle {\frac {1}{|G|}}\sum _{g\in G}\left|(Y^{X})_{\omega ,g}\right|}
ここで は g によって固定される 重みの彩色の集合である 。すべての可能な重みを合計すると、
（
はい
バツ
）
ω 、 グ
{\displaystyle (Y^{X})_{\omega ,g}}
ω
{\displaystyle \omega}
ふ （
x
1
、
x
2
、 … ） =
1
|
グ
|
∑
グ ∈ グ 、 ω
x
ω
|
（
はい
バツ
）
ω 、 グ
|
。
{\displaystyle F(x_{1},x_{2},\ldots )={\frac {1}{|G|}}\sum _{g\in G,\omega }x^{\omega }\left|(Y^{X})_{\omega ,g}\right|.}
一方、サイクル構造を持つ グループ
要素 gは、
じ
1
（ グ ） 、
じ
2
（ グ ） 、 … 、
じ
ん
（ グ ）
{\displaystyle j_{1}(g),j_{2}(g),\ldots ,j_{n}(g)}
t
1
じ
1
（ グ ）
t
2
じ
2
（ グ ）
⋯
t
ん
じ
ん
（ グ ）
{\displaystyle t_{1}^{j_{1}(g)}t_{2}^{j_{2}(g)}\cdots t_{n}^{j_{n}(g)}}
G のサイクルインデックスに等しい 。元 g が 元を固定するのは、関数 φ が g のすべてのサイクル q で一定である場合に限る 。このようなサイクル q ごとに 、 f で列挙される集合から| q | 個の同一色の重みによる生成関数は 、
ϕ ∈
はい
バツ
{\displaystyle \phi \in Y^{X}}
ふ
（
x
1
|
q
|
、
x
2
|
q
|
、
x
3
|
q
|
、 …
）
。
{\displaystyle f\left(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots \right).}
すると、 g によって固定された点の重みによる生成関数は、 g のすべてのサイクルにわたる上記の項の積 、
すなわち
∑
ω
x
ω
|
(
Y
X
)
ω
,
g
|
=
∏
q
cycle of
g
f
(
x
1
|
q
|
,
x
2
|
q
|
,
x
3
|
q
|
,
…
)
=
f
(
x
1
,
x
2
,
…
)
j
1
(
g
)
f
(
x
1
2
,
x
2
2
,
…
)
j
2
(
g
)
⋯
f
(
x
1
n
,
x
2
n
,
…
)
j
n
(
g
)
{\displaystyle {\begin{aligned}\sum _{\omega }x^{\omega }\left|(Y^{X})_{\omega ,g}\right|&=\prod _{q{\text{ cycle of }}g}f\left(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots \right)\\&=f(x_{1},x_{2},\ldots )^{j_{1}(g)}f\left(x_{1}^{2},x_{2}^{2},\ldots \right)^{j_{2}(g)}\cdots f\left(x_{1}^{n},x_{2}^{n},\ldots \right)^{j_{n}(g)}\end{aligned}}}
これをすべてのg の 合計に代入すると、 主張どおりに置換サイクル インデックスが生成されます。
参照
参考文献
外部リンク 
