バーンサイドの補題 ~いかにして対称性を考慮した数え上げ問題を解くか~
はじめに
対称性を考慮した数え上げ問題に対して、バーンサイドの補題を実際に適用して解いてみます。
この記事で書くこと
- 群の作用の説明
- バーンサイドの補題の記述
- 具体的な計算例
この記事で書かないこと
- 群の定義の説明
- 置換(互換、巡回置換)の説明
- 同値関係の説明
- 写像の用語の説明
- 定理の証明
置換群の用語はぜひ調べていただけるとありがたいです。一方で、群の定義や同値関係等の用語が分からなかったら読み飛ばしてください。用語が分からなくても具体例を追うことはできるように書いているつもりです。もちろん、簡単に調べていただけると、より分かりやすいかなと思います。
バーンサイドの補題の主張
まず、バーンサイドの補題の主張を述べます。用語の説明は後ほど行います。
バーンサイドの補題の証明は[1]を参照してください。
以下では、定理の主張に出てくる「作用」、「軌道」、「
対称性を考慮した数え上げ問題
突然ですが問題です。次の問題を以下では「三角形着色問題」といいます。
この問題は対称性を考慮した数え上げ問題で、バーンサイドの補題を用いて解くことができます。
しかし、まずは定理を適用する前に愚直に数え上げてみます。
対称性を考慮せずに配置を数え上げると、次のように
このうち、回転や反転させて一致するものをまとめて列挙してみます。
つまり、これは次を意味します。
-
と回転や反転させて一致するものはありません。T1 も同様です。T2, T3 -
は回転させることで一致します。T4, T5, T6 からT7, T8, T9 も同様です。T19, T20, T21 -
は回転もしくは反転することで一致します。T22, T23, T24, T25, T26, T27
したがって、上の問題の答えは列挙した集合の個数として
群の作用
さて、以下では三角形着色問題を通して、バーンサイドの補題の主張を理解することを目標にします。三角形着色問題を具体例として群論の用語を説明します。
着色された三角形の集合を
と置きます。
まず、
例えば、下図のように、
このことを置換群を用いて表します。
上のように正三角形の頂点の位置に番号を付けます。
一番上の位置は
観察してみると、反時計回りに
さらに、
巡回置換
このとき、
さて、三角形の各頂点がどの位置に移るのかが決まれば、回転や反転は一意に定まります。逆に、回転や反転が一つ与えられたとき、三角形の各頂点が位置に移るのかが決まります。この意味で、集合
他に三角形の回転や反転を表す置換はいくつあるでしょうか?残りを全て列挙することが目標です。
例えば、 巡回置換
さらに、互換
互換
三角形を移動させないような恒等置換
以上の6つの置換が三角形を回転や反転させて元の三角形に一致させる置換全てです。
この群
先ほど定義した置換が三角形に及ぼす作用を
着色された三角形
このとき、三角形のシンメトリー群
-
の単位元である恒等置換G と任意のe に対して、x \in X である。e \cdot x = x -
と任意のg, h \in G に対して、x \in X である。g \cdot (h \cdot x) = (gh) \cdot x
という二つの性質が成り立ちます。後者は着色された三角形
さて、三角形から離れて一般の群作用についても定義しておきます。
既に確認したように、三角形のシンメトリー群
三角形の集合以外に対する置換群の作用についてはhttp://dopal.cs.uec.ac.jp/okamotoy/lect/2022/dme/
にいくつかの例が挙げられています。考えたい対象に応じて、対称性を表す置換群をその都度考えることになります。
軌道
さて、続いては三角形のシンメトリー群が着色された三角形の集合に作用するときの、軌道について考えます。一言で述べると、軌道とは対称性を考慮すると同じものとみなせるものの集まりのことです。三角形のシンメトリー群が作用する着色された三角形の集合においては、上の(☆)で列挙した回転や反転させることで同一視できる集合たち
それぞれが軌道です。
着色された三角形に対して「回転や反転させることで同一視できる」ことを置換群とその作用を用いて表します。
着色された三角形
すなわち、シンメトリー群の作用(回転や反転)によって一致する着色された三角形は同じものとみなす、ということです。これが対称性を考慮するということです。
さらに、「着色された三角形
さて、着色された三角形の軌道について、具体的に考えてみます。もう一度着色された三角形たちと、シンメトリー群
答えは先ほど列挙したように、上の
-
に恒等置換T22 を作用させることによって、e 自身が得られます、すなわちT22 が成り立ちます。これはe \cdot T22 = T24 がそれ自身と同等であることを表しています。T22 -
に回転T22 を作用させることによってa が得られます、すなわち、T24 が成り立ちます。a \cdot T22 = T24 - 同様に、
が成り立ちます。b \cdot T22 = T23 - 同様に、
が成り立ちます。r \cdot T22 = T27 - 同様に、
が成り立ちます。s \cdot T22 = T26 - 同様に、
が成り立ちます。t \cdot T22 = T25
同様にして、軌道をすべて集めた集合を
が得られます。なぜ、
このとき、着色された三角形の集合
軌道は回転や反転に関して一致する着色された三角形の集合でした。したがって、異なる軌道の数が「回転や反転させることで一致する塗り方を同じものとみなしたときの、三角形の塗り方の総数」を表しています。すなわち、三角形着色問題の答えは
さて、三角形の集合を離れて、一般の群作用に関して軌道を定義します。
\mathrm{Fix}(g) とバーンサイドの補題
もう一度バーンサイドの補題を述べます。
残りは、
これまでと違ってまず一般の群作用に対して
さて、これまでと同様にして、三角形のシンメトリー群
-
です。なぜなら、恒等置換\mathrm{Fix}(e) = X を作用させてもe は変化しないからです。つまり、任意のx に対して、x \in X が成り立ちます。e \cdot x = x - 反時計回りの
回転\pi / 3 によって、固定されるa の部分集合はX です。図で確かめてみてください。\mathrm{Fix}(a) = \{ T1, T2, T3 \} - 同様に
です。\mathrm{Fix}(b) = \{ T1, T2, T3 \} - 反転
によって、固定されるr の部分集合はX です。こちらも図で確かめてみてください。\mathrm{Fix}(r) = \{ T1, T2, T3, T5, T8, T11, T14, T17, T20 \} - 同様に
です。\mathrm{Fix}(s) = \{ T1, T2, T3, T6, T9, T12, T15, T18, T21 \} - 同様に
です。\mathrm{Fix}(t) = \{ T1, T2, T3, T4, T7, T10, T13, T16, T19 \}
さあ、いよいよ三角形着色問題に対して、バーンサイドの補題を適用できます。
バーンサイドの補題より、「回転や反転させることで一致する塗り方を同じものとみなしたときの、三角形の塗り方の総数」、すなわち、軌道の数
となります。これは、愚直に列挙した塗り方の総数と一致しています。
おわりに
以上でバーンサイドの補題の説明を終わります。ここまで読んでくださってありがとうございました。本当はポリアの数え上げ定理が書きたかったのですが、バーンサイドの補題の説明でかなり長くなってしまいました。ポリアの数え上げ定理の記事もそのうちに書きたいです。
もっと詳しく知りたい方のために、文献を挙げます。http://dopal.cs.uec.ac.jp/okamotoy/lect/2022/dme/ には色々な例が載っているので読んでみると良いかもしれません。また、僕は[1]で勉強したのですが、具体例や簡単な演習問題が抱負で、さらに証明や説明も丁寧で分かりやすい良い本でとてもおすすめです。ぜひ読んでみてください。
TODO: もう一つ例を載せる
TODO: 競技プログラミングの問題を解いてみる
参考文献
[1] R.B.J.T. Allenby, Alan Slomon, How to count an introduction to combinatorics Second edition, CRC Press, 2011.
[2] 岡本 吉央, 離散数理工学, http://dopal.cs.uec.ac.jp/okamotoy/lect/2022/dme/, (閲覧日2023/09/20).
Discussion