バーンサイドの補題 ～いかにして対称性を考慮した数え上げ問題を解くか～

はじめに

対称性を考慮した数え上げ問題に対して、バーンサイドの補題を実際に適用して解いてみます。

この記事で書くこと

• 群の作用の説明
• バーンサイドの補題の記述
• 具体的な計算例

この記事で書かないこと

• 群の定義の説明
• 置換（互換、巡回置換）の説明
• 同値関係の説明
• 写像の用語の説明
• 定理の証明

置換群の用語はぜひ調べていただけるとありがたいです。一方で、群の定義や同値関係等の用語が分からなかったら読み飛ばしてください。用語が分からなくても具体例を追うことはできるように書いているつもりです。もちろん、簡単に調べていただけると、より分かりやすいかなと思います。

バーンサイドの補題の主張

まず、バーンサイドの補題の主張を述べます。用語の説明は後ほど行います。

バーンサイドの補題 [1, p258 THEOREM 13.1]

有限群 $G$ が集合 $X$ に作用しているとします。$G$ の各元 $g$ に対して、 $g$ によって固定される
$X$の元全体の集合を $\mathrm{Fix(g)}$ とおきます。つまり、 $\mathrm{Fix(g)} = \{ x \in X \mid g \cdot x = x \}$ です。
このとき、 軌道の数 $|X / G|$ は

$$|X / G| = \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix(g)}|$$

と表されます。

バーンサイドの補題の証明は[1]を参照してください。

以下では、定理の主張に出てくる「作用」、「軌道」、「 $\mathrm{Fix(g)}$ 」について順番に説明します。

対称性を考慮した数え上げ問題

突然ですが問題です。次の問題を以下では「三角形着色問題」といいます。

正三角形の頂点にそれぞれ球が一つずつ置いてあります。各頂点に置かれた3つの球をそれぞれ白色、黒色、赤色のいずれかで塗ります。塗り方の総数はいくつあるでしょうか？ただし、回転や反転させることで一致する塗り方は同じものとみなします。

この問題は対称性を考慮した数え上げ問題で、バーンサイドの補題を用いて解くことができます。

しかし、まずは定理を適用する前に愚直に数え上げてみます。

対称性を考慮せずに配置を数え上げると、次のように $3^3 = 27$ 通りが得られます。

このうち、回転や反転させて一致するものをまとめて列挙してみます。

$$\{ T1 \}, \{ T2 \}, \{ T3 \}, \{ T4, T5, T6 \}, \{ T7, T8, T9 \}, \{ T10, T11, T12 \}, \{ T13, T14, T15 \}, \\ \{ T16, T17, T18 \}, \{ T19, T20, T21 \}, \{ T22, T23, T24, T25, T26, T27 \} \tag{☆}$$

つまり、これは次を意味します。

• $T1$ と回転や反転させて一致するものはありません。 $T2, T3$ も同様です。
• $T4, T5, T6$ は回転させることで一致します。 $T7, T8, T9$ から $T19, T20, T21$ も同様です。
• $T22, T23, T24, T25, T26, T27$ は回転もしくは反転することで一致します。

したがって、上の問題の答えは列挙した集合の個数として $10$ 通りであることが分かりました。

群の作用

さて、以下では三角形着色問題を通して、バーンサイドの補題の主張を理解することを目標にします。三角形着色問題を具体例として群論の用語を説明します。

着色された三角形の集合を $X$ と置きます。つまり、

$$X = \{ T1 , T2 , T3 , T4, T5, T6 , T7, T8, T9 , T10, T11, T12, T13, T14, T15 , T16, T17, \\ T18 , T19, T20, T21 , T22, T23, T24, T25, T26, T27 \}$$

と置きます。

まず、$X$ の元である着色された三角形たちを「回転や反転させる」ということを置換群を用いて表します。

例えば、下図のように、$T25$ を反時計回りに $\pi/3$ 回転させると $T27$ に一致します。
このことを置換群を用いて表します。

上のように正三角形の頂点の位置に番号を付けます。
一番上の位置は $1$ 、左下の位置は $2$ 、右下の位置は $3$ です。番号は平面上に固定されていると考えてください。

観察してみると、反時計回りに $\pi / 3$ 回転させると、$1$ の位置にある球が $2$ の位置に移ります。
さらに、 $2$ の位置にある球が $3$ の位置に、 $3$ の位置にある球が $1$ の位置に移ります。

巡回置換 $a$ を $a = (1 \ 2 \ 3)$ とおくと、反時計回りに $\pi / 3$ 回転させることは、 $i = 1, 2, 3$ に対して、$i$ の位置にあった球を $a(i)$ の位置に移動させる、と書くことができます。

このとき、$T25$ を反時計回りに $\pi / 3$ 回転させて $T27$ を得たことを、$T25$ に $a$ を作用させて
$T27$ を得た、といいます。

さて、変換後に三角形の各頂点がどの位置に移るのかが決まれば、回転や反転は一意に定まります。逆に、三角形を三角形に移す回転や反転が一つ与えられたとき、三角形の各頂点が位置に移るのかが決まります。この意味で、集合 $\{1, 2, 3\}$ の置換は三角形の回転や反転を表しています。

他に三角形の回転や反転を表す置換はいくつあるでしょうか？残りを全て列挙することが目標です。

例えば、 巡回置換 $b = (1 \ 3 \ 2)$ は三角形を時計回りに $\pi / 3$ 回転させることを表します。
さらに、互換 $r = (1 \ 2)$ は位置 $3$ の頂点と対辺の中点を結ぶ直線に対する反転を表します。
互換 $s = (1 \ 3)$ と $t = (2 \ 3)$ も下図のような反転を表します。
三角形を移動させないような恒等置換 $e = (1)(2)(3)$ も忘れてはいけません。恒等置換も後ほど活きてきます。

以上の6つの置換が三角形を回転や反転させて元の三角形に一致させる置換全てです。
$G = \{ e, a, b, r, s, t \}$ と置きます。このとき、 $G$ は置換の積（写像としての合成）に関して群をなします。特に、$G$ は 3次対称群 $S^3$ と一致します。

この群 $G$ は三角形の対称性に関する情報を含むような群とみなせます。そこで、$G$ を三角形のシンメトリー群といいます。

先ほど定義した置換が三角形に及ぼす作用を $G$ の各元に対しても定義します。
着色された三角形 $x \in X$ に対して、三角形のシンメトリー群の要素 $g \in G$ を作用させるとは、$i = 1, 2, 3$に対して$x$ の位置 $i$ に置かれた球を位置 $g(i)$ に移すこと、として定義します。この作用によって得られる着色された三角形を $g \cdot x \in X$ と表します。

このとき、三角形のシンメトリー群 $G$ と着色された三角形の集合 $X$ に対して、

• $G$ の単位元である恒等置換 $e$ と任意の $x \in X$ に対して、 $e \cdot x = x$ である。
• $g, h \in G$ と任意の $x \in X$ に対して、 $g \cdot (h \cdot x) = (gh) \cdot x$ である。

という二つの性質が成り立ちます。後者は着色された三角形 $x$ の位置 $i$ に置かれた球を
$h(i)$ に移してから、さらに、$g(h(i))$ に移すことと、$x$ の位置 $i$ に置かれた球を $gh(i)$ に移すことが同じことであることから従います。実際、$g(h(i)) = gh(i)$ が成り立ちます。

さて、三角形から離れて一般の群作用についても定義しておきます。

$G$ を群、 $X$ を集合とします。任意の $g \in G$ と任意の $x \in X$ について、$X$ の元 $g \cdot x$ が定まり、次が成り立つとき、 $G$ は $X$ に作用するといいます。

• $G$ の単位元 $e$ と任意の $x \in X$ に対して、 $e \cdot x = x$ が成り立つ。
• 任意の $g, h \in G$ と任意の $x \in X$ に対して、 $g \cdot (h \cdot x) = (gh) \cdot x$ が成り立つ。

既に確認したように、三角形のシンメトリー群 $G$ は着色された三角形の集合 $X$ にこの意味でも作用します。

三角形の集合以外に対する置換群の作用についてはhttp://dopal.cs.uec.ac.jp/okamotoy/lect/2022/dme/
にいくつかの例が挙げられています。考えたい対象に応じて、対称性を表す置換群をその都度考えることになります。

軌道

さて、続いては三角形のシンメトリー群が着色された三角形の集合に作用するときの、軌道について考えます。一言で述べると、軌道とは対称性を考慮すると同じものとみなせるものの集まりのことです。三角形のシンメトリー群が作用する着色された三角形の集合においては、上の(☆)で列挙した回転や反転させることで同一視できる集合たち

$$\{ T1 \}, \{ T2 \}, \{ T3 \}, \{ T4, T5, T6 \}, \{ T7, T8, T9 \}, \{ T10, T11, T12 \}, \{ T13, T14, T15 \}, \\ \{ T16, T17, T18 \}, \{ T19, T20, T21 \}, \{ T22, T23, T24, T25, T26, T27 \}$$

それぞれが軌道です。

着色された三角形に対して「回転や反転させることで同一視できる」ことを置換群とその作用を用いて表します。

着色された三角形 $x, y \in X$ がシンメトリー群 $G$ の作用に関して同等であるとは、ある置換 $g \in G$ が存在して、$x$ に $g$ を作用させることで $y$ が得られること、つまり、$g \cdot x = y$ が成り立つこと、と定めます。

すなわち、シンメトリー群の作用（回転や反転）によって一致する着色された三角形は同じものとみなす、ということです。これが対称性を考慮するということです。

さらに、「着色された三角形 $x, y \in X$ がシンメトリー群 $G$ の作用に関して同等である」ことは $X$ 上の同値関係となっています。証明は省略します。大切なこととして、この同値関係に関する同値類が $X$ の分割になっている、ということです。

さて、着色された三角形の軌道について、具体的に考えてみます。もう一度着色された三角形たちと、シンメトリー群 $G$ の図を載せます。

$T22$ とシンメトリー群 $G = \{e, a, b, r, s, t\}$ の作用に関して同等である着色された三角形はいくつあるでしょうか？
答えは先ほど列挙したように、上の $\{ T22, T23, T24, T25, T26, T27 \}$ の6つです。この6つの元を持つ集合が $T22$ の同値類です。つまり、

• $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$ が成り立ちます。

$r, s, t$ の作用に関して同等であることは、反転に関して一致していることを表すことに注意してください。

同様にして、軌道をすべて集めた集合を $X / G$ と書くと、

$$X / G = \{ \{ T1 \}, \{ T2 \}, \{ T3 \}, \{ T4, T5, T6 \}, \{ T7, T8, T9 \}, \{ T10, T11, T12 \}, \{ T13, T14, T15 \}, \\ \{ T16, T17, T18 \}, \{ T19, T20, T21 \}, \{ T22, T23, T24, T25, T26, T27 \} \}$$

が得られます。なぜ、$X / G$ と書くかというと、これは $G$ の作用に関する同一視に関して、集合をギュッと縮めている、割っているというイメージです。詳しくは、同値関係と商集合について調べてみてください。
このとき、着色された三角形の集合 $X$ の各元がいずれかの軌道にちょうど一回ずつ表れています。このことを軌道が $X$ を分割している、といいます。

軌道は回転や反転に関して一致する着色された三角形の集合でした。したがって、異なる軌道の数が「回転や反転させることで一致する塗り方を同じものとみなしたときの、三角形の塗り方の総数」を表しています。すなわち、三角形着色問題の答えは $|X / G|$ です。ただし、有限集合 $A$ の要素の個数を $A$ と表します。

さて、三角形の集合を離れて、一般の群作用に関して軌道を定義します。

群 $G$ が集合 $X$ に作用しているとします。このとき、$x, y \in X$ に対して、二項関係 $\sim_G$ を

$$x \sim_G y \Leftrightarrow \text{ある} \ g \ \text{が存在して、} \ y = g \cdot x \ \text{を満たす。}$$

と定めます。すると、$\sim_G$ は $X$ 上の同値関係となり、$x \in X$ の $\sim_G$ に関する同値類を $x$ の軌道といいます。

$\mathrm{Fix}(g)$ とバーンサイドの補題

もう一度バーンサイドの補題を述べます。

バーンサイドの補題 [1, p258 THEOREM 13.1]

有限群 $G$ が集合 $X$ に作用しているとします。$G$ の各元 $g$ に対して、 $g$ によって固定される
$X$の元全体の集合を $\mathrm{Fix(g)}$ とおきます。つまり、 $\mathrm{Fix(g)} = \{ x \in X \mid g \cdot x = x \}$ です。
このとき、 軌道の数 $|X / G|$ は

$$|X / G| = \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix(g)}|$$

と表されます。

残りは、$\mathrm{Fix}(g)$ について説明すると、バーンサイドの補題を適用できます。
これまでと違ってまず一般の群作用に対して $\mathrm{Fix}(x)$ を定義します。

群 $G$ が集合 $X$ に作用している状況で、$G$ の各元 $g$ に対して、 $g$ によって固定される$X$の元全体の集合を $\mathrm{Fix(g)}$ とおきます。つまり、 $\mathrm{Fix(g)} = \{ x \in X \mid g \cdot x = x \}$ です。

さて、これまでと同様にして、三角形のシンメトリー群 $G = \{e, a, b, r, s, t\}$ が着色された三角形の集合 $X$ に作用している状況で、$G$ の各元 $g$ に対して $\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 \}$ です。

さあ、いよいよ三角形着色問題に対して、バーンサイドの補題を適用できます。
バーンサイドの補題より、「回転や反転させることで一致する塗り方を同じものとみなしたときの、三角形の塗り方の総数」、すなわち、軌道の数 $|X / G|$ は

$$\begin{align*} |X / G| & = \frac{1}{|G|} \sum_{g \in G} |\mathrm{Fix}(g)| \\ & = \frac{1}{6} \{\mathrm{Fix}(e) + \mathrm{Fix}(a) + \mathrm{Fix}(b) + \mathrm{Fix}(r) + \mathrm{Fix}(s) + \mathrm{Fix}(t)\} \\ & = \frac{1}{6} \{ 27 + 3 + 3 + 9 + 9 + 9 \} \\ & = 10 \end{align*}$$

となります。これは、愚直に列挙した塗り方の総数と一致しています。

おわりに

以上でバーンサイドの補題の説明を終わります。ここまで読んでくださってありがとうございました。本当はポリアの数え上げ定理が書きたかったのですが、バーンサイドの補題の説明でかなり長くなってしまいました。ポリアの数え上げ定理の記事もそのうちに書きたいです。

もっと詳しく知りたい方のために、文献を挙げます。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).