Burnside の補題を用いた数え上げ【Wathematicaアドベントカレンダー】

はじめましての方ははじめまして。Wathematica2年のchimakiと申します。Wathematica Advent Calender 2021 の12/16日の記事になります。個人的に好きなBurnsideの補題について書こうと思います。

（もくじ）

問題設定
Burnsideの補題
問題を解く
おまけ
最後に
参考資料

問題設定

問題１

立方体を $n$ 色以下で塗る場合の数は何通りあるか。ただし、回転などにより重なるものは同じとみなす。

　この問題について考えていきます。高校数学では、異なる6色で塗分ける場合の数や同じ色が隣り合わないよう異なる5色で塗る場合の数を求める問題を円順列や数珠順列の考え方を応用することで解くことができましたが、この問題においては「同じ色は隣り合わない」という制約が外れており、難しくなっています。例えば、次の2つの図のような塗り方を同じとみなす必要があります。（雑な図でごめんなさい）

f:id:chimaki_yama821:20211215172936p:plain — これらは同じ

それではこの問題について考えてみましょう。

　こういう問題は小さいnについて考察してみると何か見えてくることが多いです。しかし、n＝2の場合でもどの塗り方が回転で重なり合うのか見つけるのは容易ではありません。（ちなみn＝2の場合は10通り、n＝3の場合は57通りになります。気になる人は頑張って試してみてください、おすすめはしません）

Burnsideの補題

そこで本稿の主題であるBurnsideの補題を使うことを考えます！まずはBurnsideの補題の主張をみていきましょう。

命題の主張と解釈

　Burnsideの補題の主張は以下の通りです。

Burnsideの補題

有限群 $G$ が集合 $X$ に作用するとする。また、 $g \in G$ に対いて $g$ によって固定されるすべての $X$ の元からなる集合を $\mathrm{fix}(g)$ とする。このとき、軌道の数は $\frac{1}{|G|} \sum_{g \in G} | \mathrm{fix} (g) |$ である。

…………。何言ってるかさっぱりわかりませんね。。。

まず「群」ってなんだよ！って感じだし「作用」も分からないし、「軌道」も意味が分からない。本当にこの命題がさっきのような問題解決につながるの？って感じです。

（群論に詳しい方はこの定理を最初の問題にどう使うか考えてみてください）

具体例：正方形の頂点塗り分け

　そこで、具体的な問題を通してこの定理を解釈していきましょう。具体例を考えると分かりやすいのですが最初から立方体の面の塗分けを考えるのは難しいので次のような問題を考えてみます。

問題２

正方形の各頂点を青か黄色で塗り分ける方法は何通りあるか。ただし、回転させて同じものは同じとみなす。
（ここでは簡単のため裏返しは考えないこととします。つまり、裏返したときに同じ塗り方になっても別とみなします。）

　この問題にBurnsideの補題を応用するために適切に群 $G$ や集合 $X$ を定める必要がありますが、そこはなんとなくノリをつかめればOKです！

　まず、群 $G$ が集合 $X$ に作用しているとは、「集合 $X$ には $G$ という群によってあらわされるような対称性がある」ということです。そして結論部分である「軌道の数」とは、「群 $G$ による対称性によって同じものを同一視したときの場合の数」になります！求める場合の数がこの「軌道の数」に一致するように $G$ と $X$ を定めていきます。（要するに「群」ってやつが対称性をあらわすんだな～ってことです）

　これを上の問題2で考えましょう。正方形は $90^{\circ}, 180^{\circ}, 270^{\circ}$ 回転させてもまた同じ形になります。また、当然ですが $0^{\circ}$ 回転させる（つまり何もしない）という操作に対しても形は保たれます。

　このことから、平面上の正方形には「 $0^{\circ}, 90^{\circ}, 180^{\circ}, 270^{\circ}$ 回転」に対する対称性があるといえます。この4つの回転こそがこの問題における群 $G$ です。

　そして、今回の問題では集合 $X$ は以下の図のようなものとしましょう。

f:id:chimaki_yama821:20211212205047p:plain — 集合X　16個からなる

つまり、対称性を無視して全ての塗り方を考慮した集合を $X$ と定めるのです。このとき、例えば下の図のような $G$ から $X$ への作用があります。

f:id:chimaki_yama821:20211215172738p:plain — 作用の図

　さて、これで「有限群 $G$ が集合 $X$ に作用するとする」の部分は分かりました。では次に「 $g \in G$ に対して $g$ によって固定されるすべての $X$ の元からなる集合」という部分を見てみましょう。 $G$ は対称性を表すものなので、今回の問題では上の考察から $g \in G$ は、 $0^{\circ}$ 回転・ $90^{\circ}$ 回転・ $180^{\circ}$ 回転・ $270^{\circ}$ 回転のいずれかとなります。

　まず、「 $g = 90^{\circ}$ 回転」として考えてみます。すると、先ほどの図で定めた $X$ の元のうち、 $90^{\circ}$ 回転させても変わらないものは以下の2つになります。 $270^{\circ}$ 回転の場合も同じです。

f:id:chimaki_yama821:20211215173533p:plain — 90°、270°回転で不変な塗り方

　次に、「 $g = 180^{\circ}$ 回転」として考えてみます。これによって固定される $X$ の元は以下の4通りです。

f:id:chimaki_yama821:20211215173617p:plain — 180°回転で不変な塗り方

　最後に、 $0^{\circ}$ 回転に対して不変なものは $X$ の元全てであることに注意しておきましょう。

　以上によって、「各 $g \in G$ に対して $g$ によって固定されるすべての $X$ の元からなる集合」が分かりました。

　ではBurnsideの補題の結論の部分の解釈です。最初に述べたとおり、「軌道の数」とは「群 $G$ による対称性によって同じものを同一視したときの場合の数」になります。つまりこの問題では「回転で重なるものを同一視したときの頂点の塗り方」（求めたかったやつ！）がこれにあたるのです！そしてBurnsideの補題の主張から、これが「各 $g \in G$ に対して不変な $X$ の部分集合の要素数の和をとり、対称性の数で割ったもの」と等しくなることが分かります。

　今述べたことを図示するとこんな感じです。

f:id:chimaki_yama821:20211215174258p:plain

よって、この問題の場合の数は

$\frac{1}{4}(2×2 + 4 + 16) = 6$ 通り

と求めることができます！

　以上の例から、Burnsideの補題は次のように応用できると分かります！！

対称性のあるものの数え上げ

対称性のあるものの数え上げは、以下のようにして求められる。
1. 対称性をとらえる
2. それぞれの対称性について不変なものを数え上げる（このときは対称性を無視して全て数える）
3. 2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。

ｎ色で塗る場合

　上と同様の考え方により、頂点を $n$ 色で塗る場合の数も求めることができます！

　 $90^{\circ}, 270^{\circ}$ 回転で不変なものはどちらの場合も全ての頂点の色が同じ場合の $n$ 通りです。よって合計で $2n$ 通りとなります。

　また、 $180^{\circ}$ 回転で不変なものは対角線上の2頂点を同じ色で塗る場合の $\times n^2$ 通りです。

　そして、 $0^{\circ}$ 回転で不変なものは $n^4$ 通りです。

　以上より、求める場合の数は $\frac{1}{4} (n^4 + n^2 + 2n)$ 通りと分かります！

（余談ですが、「場合の数は必ず整数になる」ということから上の式の分母「 $n^4 + n^2 + 2n$ 」が4の倍数であることが分かります！）

問題を解く

　さて、Burnsideの補題の使い方が少しわかったところで実際に立方体の塗分けを考えていきましょう。先ほどの数え上げ方法をもう一度見直しておきます。

対称性のあるものの数え上げ

1. 立方体の対称性をとらえる

　まずは立方体の対称性について考える必要があります。これは厳密にやろうとするとむずかしいのですが、以下のように解釈できます。

立方体の対称性(A) 何もしない
(B) 向かい合う２面の中心を結ぶ直線を軸として $90^{\circ}, 180^{\circ}, 270^{\circ}$ 回転
(C) 立方体の中心とある頂点を結ぶ直線を軸として $120^{\circ}, 240^{\circ}$ 回転
(D) 立方体の中心とある辺の中点を結ぶ直線を軸として $180^{\circ}$ 回転

（分かりにくいかもしれません……この後図を使って説明するのでいったん飛ばしちゃって大丈夫です）

　これらそれぞれについて、何通りの対称軸がとれるかみてみましょう。

それぞれの操作に対する対称軸

(A) について

動かさないのは1通りしかありません。

(B) について

以下の図のように3通りあります。

f:id:chimaki_yama821:20211215175034p:plain

以下の図のように4通りあります。

f:id:chimaki_yama821:20211215175102p:plain

(D) について

6通りです。詳しくは各自で確認してみてください。

(A) ~ (D) より、対称性の数は合計で、

(A) : 1通り

(B) : 3 × 3 = 9 通り

(D) : 1 × 6 = 6 通り

であるので、1 + 9 + 8 + 6 = 24 個になります！

これで立方体の対称性が分かりました！

2. 各対称性で不変な塗り方

　次に各対称性を表す操作（回転）について不変な塗り方を数えていきましょう！

(A) について

どのような塗り方を考えても「何もしない」という操作の下では不変であるので、各面を $n$ 色で塗ることを考えることにより、 $n^6$ 通りです。

(B) について

　 $90^{\circ}, 270^{\circ}$ の場合と $180^{\circ}$ の場合で異なるので注意が必要です。

　まず、 $90^{\circ}, 270^{\circ}$ 回転によって不変になる場合を考えます。そのためには、回転軸を含む二つの面は自由に塗り、その他の4面を同じ色で塗る必要があります。よって、前者の二つの面の塗り方が $n^2$ 通り、後者の4面の塗り方が $n$ 通りなので合計 $n^3$ 通りとなります。

f:id:chimaki_yama821:20211215232755p:plain — 90°、270°回転で不変な塗り方

　次に、 $180^{\circ}$ 回転によって不変になる場合を考えます。そのためには、回転軸を含む二つの面は自由に塗り、その他の4面を向かい合う2面同士が同じ色になるように塗る必要があります。よって、前者が $n^2$ 通り、そのそれぞれに対し後者が $n^2$ 通りなので合計 $n^4$ 通りとなります。

　 $120^{\circ}, 240^{\circ}$ 回転どちらの場合でも、回転軸を上2つの頂点に対して一方の頂点側にある3面を同じ色で、他方の頂点側にある3面を同じ色で塗る必要があります。前者の選び方が $n$ 通り、そのそれぞれに対し後者が $n$ 通りなので合計 $n^2$ 通りとなります。

(D) について

　頑張ると、 $n^3$ 通りであることが分かります。（各自で考えてみてください）

以上により、各対称性を表す操作に対して不変な塗り方が求まりました！

あとはこれらに対してBurnsideの補題を適用すると答えがでます！！

3. 2で数えたものから答えを求める

　さて、仕上げです。『2で数えたものを全ての対称性について和をとり、「対称性の数」で割る。』を実際に行っていきましょう！これは以下のように求めることができます。

f:id:chimaki_yama821:20211215175700p:plain

これを整理することにより、

$\frac{1}{24}(n^6 + 3n^4 + 12n^3 + 8n^2)$ 通り

と求めることができました！！！

（なお、n = 6の場合からn = 5の場合を引くことでちょうど6色で塗る場合の数を求めることもできます）

おまけ

　いかがでしたでしょうか。Burnsideの補題が対称性のあるものの数え上げにとても役立つことが伝わったでしょうか。ちなみにこの定理は「Cauchy-Frobeniusの定理」とも呼ばれるらしいです。この定理は、「ぐ・こ・き」で知られる位数に関する定理やLagrangeの定理を使うことで証明することができます。（証明は[2], [3]に載っています。そんなに難しくないです）また、群論にある程度慣れている人だと立方体の対称性が4次対称群で表されることをご存じだと思うのですが、そのときの「置換の型」の考え方が塗り分けにおける大きな役割を果たしています。これを生かして「サイクルインデックス」というものを導入し、定理をより使いやすい形に書き直すこともできるようです。（一緒に[3]を読みましょう！）また、この定理は表現論を使って証明することもできるようです。（自分は詳しく知りません）そして、競技プログラミングの問題に応用することもあるらしいです。

最後に

　今回は前提知識なしで読めるようになるべく群論のことばを使わずに書いてみました。ですが定理の証明やより深い理解のためには群論が必須です。おすすめは参考文献[1]の本です。

　「一人では厳しい……」というそこのあなた！！！Wathematicaでこれから群論ゼミが開催されるらしいですよ！！！！！

参考資料

[1] 雪江明彦. 群論入門 / 雪江明彦著. 東京, 日本評論社, 2010

[2] Godsil, C. D. (Christopher David), Royle, Gordon. Algebraic graph theory / Chris Godsil, Gordon Royle. New York, Springer, 2001

[3] Aigner, Martin. A Course in Enumeration [electronic resource] / by Martin Aigner. 1st ed. 2007., Berlin, Heidelberg, Springer Berlin Heidelberg, 2007

[4] Liu, Chung Laung, 伊理正夫, 伊理由美. 組合せ数学入門. 1 / C.L.リウ著 ; 伊理正夫,伊理由美共訳. 東京, 共立出版, 1972.

ちまきのブログ

理系大学生が日々の生活ログやその他もろもろをかいてみます

Burnside の補題を用いた数え上げ【Wathematicaアドベントカレンダー】

問題設定

Burnsideの補題

命題の主張と解釈

具体例：正方形の頂点塗り分け

ｎ色で塗る場合

問題を解く

1. 立方体の対称性をとらえる

それぞれの操作に対する対称軸

2. 各対称性で不変な塗り方

3. 2で数えたものから答えを求める

おまけ

最後に

参考資料