大学数学基礎解説

立方体の６面色塗りの総数を数学で解決！

コーシー・フロベニウスの定理,群論,場合の数

716

立方体の６面色塗りの総数をJulia で解決！
https://zenn.dev/dannchu/articles/c2d1b6181c1c1b

を読んで書いた記事です。

立方体の面の塗り分けを行い、回転して重なるものは同一視する、という問題ですが、
これは群論を用いることで手計算でも簡単に答えを得ることができます。

同値類

集合Xに対して、関係 $\sim$ ($x \sim y$の真偽が定まる) を定める時、以下の条件を満たしていれば同値関係といい、$x \sim y$を xとyが同値という。

反射律
$x \sim x$
対称律
$x \sim y \iff y \sim x$
推移律
$x \sim y \ かつ \ y \sim z \implies x \sim z $

元xと同値なものの集合をxの同値類という。
$ [x] = \{y | x \sim y \} $
また、Xを同値類に分割できる。この操作を同値類で割るという。
$ X / \sim \ = \{[x] | x \in X\} $

$X$のすべての元は最低でも自分自身を含む同値類に入るので、必ずどれかの同値類に入っている。
異なる同値類に入っているものが重複することはない。もしそうなるとその2つの同値類のどのペアを取ってきても、共通に入っている元による推移律によって最初から同値だったことになってしまうからである。

群

集合G、
Gの元e(単位元)、
単項演算$◌^{-1}$ ($a$の逆元) ($ a \in G $ に対し $ a^{-1} $のように使うと、$ x^{-1} \in G $になっている)
二項演算$\cdot$ (積) ($ x,y \in G $に対し $ x・y $のように使うと、$ x・y \in G $になっている)
の組$(G, e, ◌^{-1}, ・ )$で、以下の条件を満たすものを群という

1.単位元は掛けてもなにもしない
$$ e \cdot x = x \cdot e = x \\ $$

2.逆元とくっつくと消える(なにもしない単位元になる)
$$ x \cdot x^{-1} = x^{-1} \cdot x = e $$

3.結合法則
$$ (x \cdot y) \cdot z = x \cdot (y \cdot z) $$
これがあるので、$x \cdot y \cdot z$と書く場合があるが、どちらにしてもよいということがわかる。

作用

群Gと集合Xに対して、(左)作用という演算を定義する。
$ g \in G , x \in X $ のとき、 $ gx \in X $ は

単位元は作用でも何もしない
$ ex = x $
作用は$\cdot$でまとめて作用できる
$ (g_1 \cdot g_2) x = g_1 (g_2 x) $

群の定義と作用の定義より、
$ (g \cdot g^{-1}) x = (g^{-1} \cdot g) x = x $

作用は同値関係を定める

$ x \sim y \iff あるgによって、 y = gx $ とすると、

$ x = ex $
$ y = gx \implies x = g^{-1} y $
$ z = g_1 y \,かつ\, y = g_2 x \implies z = (g_1 \cdot g_2) x $
なので、同値関係になる。このとき、各同値類を軌道という。

コーシー・フロベニウスの定理

群$G$が集合$X$に作用しているとき、その軌道を$X/G$とする。
また、$G$の元$g$で動かない$X$の点の集合(固定点集合)を $X^g = \{ x | gx = x \}$ と書くとき、
$$ |G| \cdot |X/G| = \sum_{g \in G} |X^g| $$
($|X|$は$X$の濃度(元の数)を表します。)

\begin{eqnarray} |G| &:& 動かし方の数 \\ |X/G| &:& 同一視をした後のパターン数 \\ |X^g| &:& g \in G で動かしたとき、元のパターンと変わらないものの数 \\ \end{eqnarray}

左辺と右辺とを1対1で対応させる。
まず、同値類ごとに代表として元を1つ選んでおく。$[x]$の代表元を$c_{[x]}と書くことにする。$

右辺 $(g,y) \: (g \in G, y \in X^g)$ が与えられたとする。
$x = c_{[y]}$とすると、$ y \in [y] = [x] $で、$x \sim y$になるので、
ある$h_{y,x}$が存在して$y = h_{y,x} x$と書ける。
右辺から左辺に、$f: (g,y) \mapsto ( g \cdot h_{y,x} , [y])$ という写像で対応させる。

逆に左辺$(g, [x]) (g \in G, [x] \in X/G)$が与えられたら、
$ x_0 = c_{[x]} $として、
$f': (g, [x]) \mapsto ( g \cdot h_{gx_0,x_0}^{-1} , g x_0 ) $
とすると、
\begin{eqnarray} f' (f(g,y) ) &=& f'( g \cdot h_{y,c_{[y]}} , [y]) \\ &&(x = c_{[y]}とすると) \\ &=& f'( g \cdot h_{y,x} , [x]) \\ &=& ( g \cdot h_{y,x} \cdot h_{\textcolor{violet}{(g \cdot h_{y,x}) x},x}^{-1} ,\textcolor{violet}{(g \cdot h_{y,x}) x}) \\ &=& ( g \cdot h_{y,x} \cdot h_{\textcolor{violet}{y},x}^{-1} ,\textcolor{violet}{y}) \\ &=& (g,y) \end{eqnarray}

\begin{eqnarray} f (f'(g,[x]) ) &=& f( g \cdot h_{gx,x}^{-1} , g x ) \: (xはc_{[x]}を使って代表元のものを選んでおく)\\ &=& ( g \cdot h_{gx,x}^{-1}\cdot h_{gx,x} , [g x] ) \\ &=& (g, [x]) \end{eqnarray}
よって、一対一で対応していることがわかる。

$[x]$から$x$を出すときなどに$c_{[x]}$などを使って、細心の注意を払っているのは、well-defined性といって、
$X/ \sim$などの集合からの関数を作るときは、$x \sim y \implies f([x]) = f([y])$になるようにする必要があり、
そうしないと同じはずの元から違う結果が返ってくるようなことになり、関数にならないという問題があるからです。

重複円順列

赤球、白球がたくさんあるとき、これらのうち6つを円状に並べる方法はいくつあるか。
回転で重なるものは同じとする。

群Gを巡回群$C_6$とする。これは
\begin{eqnarray} |C_6| &=& \{0,1,2,3,4,5\} \\ e &=& 0 \\ a^{-1} &=& \begin{aligned} \left\{ \begin{array}{l} 6 - a &\:& ( a > 0) \\ 0 &\:& (a = 0) \end{array} \right. \end{aligned}\\ a \cdot b &\equiv& a + b \mod 6\\ \end{eqnarray}
なる群である。

Xを${(0,0,0,0,0,0) \sim (1,1,1,1,1,1) }$の$2^6$要素の集合とし、
作用を$ (gx)_i = x_{(i + g) \bmod 6} $で定義する。
例： $g=3, x = (\textcolor{red}1,\textcolor{blue}0,\textcolor{green}1,\textcolor{purple}0,\textcolor{orange}0,\textcolor{brown}1) $なら、$gx = (\textcolor{purple}0,\textcolor{orange}0,\textcolor{brown}1,\textcolor{red}1,\textcolor{blue}0,\textcolor{green}1)$

そうすると、

g=0のとき、xのすべての元は動かないので $|X^g| = 64$
g=1,5のとき、すべてのiについて$x_i = x_{i+1} $でないといけないので、
結局すべての$x_i$が同じ場合のみ重なる $|X^g| = 2$
g=2,4のとき、$x_0 = x_2 = x_4, x_1 = x_3 = x_5 $ $|X^g| = 4$
g=3のとき、$x_0 = x_3, x_1 = x_4, x_2 = x_5$ のとき重なるので $|X^g| = 8$

$ | X / G | = \frac{64 + 2 \times 2 + 2 \times 4 + 8}{6} = \frac{84}{6} = 14 $

立方体の彩色1 (元記事にあった問題)

立方体の6面を赤色、青色、黄色の3色で2面づつ塗り分ける方法は何通りか。
回転で重なるものは同じとする。

群Gを立方体を回転(鏡写しはふくまない)して重ねる方法の全体、
$e$を動かさない操作、
$a^{-1}$をaの逆の回転、
$b \cdot a$をaのあとにbを行う操作とする。
サイコロで考えると、1の行き先が6種類、2はその隣の面4つのどれかなので、24通りの回転があるが、後々のために別の方法で分類する。