読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Burnside の定理

アルゴリズム解説 群論 バーンサイドの補題

Polya の定理の簡単バージョンである Burnside の定理の説明と証明をする。

群を使ってるので、最低限の群の知識はあった方がいいかも。

導入

次の問題を解くことを考えてみる。

$ n $ 個の石が円形状に並んでいる。$ m $ 色使って石に色を塗る方法は何通りあるか。ただし回転して同じものは重複して数えない。

$ n=4 $, $ m=2 $ のとき $ 2^4 $ 通り書きだしてみよう。

f:id:pekempey:20160607135959p:plain

左肩にのっている数字は、回転して同一視できる塗り方がいくつあるか。うまく付け加えると同一視できる塗り方が全部 4 つずつになる。

f:id:pekempey:20160607140329p:plain

追加したのは

  • 90 度回転しても変わらない塗り方
  • 180 度回転しても変わらない塗り方
  • 270 度回転しても変わらない塗り方

さらに、ここに書いてあるパターン数を 4 で割れば答えが得られる。

Burnside の定理

さきほどの例をもとに式を立ててみよう。石、色、色の塗り分け、回転をそれぞれ文字に置き換える。

  • 石:$ A=\{1, 2, 3, \ldots, n\} $
  • 色:$ B=\{ 1, 2, 3, \ldots, m\} $
  • 色の塗り分け:写像の集合 $X=\{x \mid x:A \to B\}$
  • 回転:群 $G=\{g_1,g_2,\ldots,g_k\}$

さきほどの例であれば、$G=\{\text{0度回転},\text{90度回転},\text{180度回転},\text{270度回転}\}$である。

これで問題と文字の結びつけは終わり。しかしこれだけだと不便なので 2 つ表記を加える。

ある操作 $g \in G$ を作用させても変化しない $x \in X$ を集めた集合を$X^g$ とする。$X^g=\{ x \in X \mid x=gx \}$。
$x, y\in X$ に対し、ある $g \in G$ が存在し $y = gx $ が成り立つという関係は同値関係$\sim_G$になる。この同値関係の商集合を $X/\sim_G=X/G$ と書く。$\sim_G=\{(x,y) \mid x, y\in X, g \in G, y=gx \}$。

$|X/G|$ が求めたい解になっている。先ほどの石の例を式にすれば次のようになる。

$$ |X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g| $$

そしてこの式こそ Burnside の定理である。ちょっと文字が多いので日本語で書いてみると次のような感じ。

$$ |X/G| = \frac{1}{|G|} \sum_{g \in G} \text{変換} g \text{を掛けても変化しない塗り分け方の個数} $$

残りは証明なので、実質この記事はここで終わり。

証明

証明する前に、軌道固定部分群という概念を導入する。

軌道: $G(x)=\{ g(x) \mid g \in G \}$
固定部分群: $G_x=\{ g \in G \mid gx=x \}$

この 2 つには次のような関係がある。

$$ |G|=|G_x||G(x)| $$

これは $|G/G_x|=|G(x)|$ を示してから Lagrange の定理を適用すれば示せる。あと使うのは次の性質。

$x, y \in X$ が同じ軌道なら $|G_x|=|G_y|$である。

証明は簡単なので省略。これらを使って式変形を行えばいい。$X/G$ の代表元の集合を $R$ とすると、次のように計算できる。

$$ \begin{align} \sum_{g \in G} |X^g| &= \sum_{x \in X} |G_x| \\ &=\sum_{x \in R} \sum_{y \in G(x)} |G_y| \\ &=\sum_{x \in R} |G(x)||G_x| \\ &=\sum_{x \in R} |G| \\ &=|X/G||G| \end{align} $$

これで証明は終わりなのだが、実際にこの式変形が何をしているのかを先ほどの石の問題を例に図示してみる。

操作によって変わらないところに○をつけた。

f:id:pekempey:20160607133844p:plain

step 1:$\sum_{g \in G} |X^g|$:$g$によって変わらない塗り分け方を数える。

f:id:pekempey:20160607133922p:plain

step 2:$\sum_{x \in X} |G_x|$:塗り分け方が変わらないような $g$ の数を数える。

f:id:pekempey:20160607133952p:plain

step 3:$\sum_{x \in R} \sum_{y \in G(x)} |G_y|$:軌道ごとに分解して考えてみる。

f:id:pekempey:20160607152828p:plain

step 4:$\sum_{x \in R} |G(x)||G_x|$:軌道ごとの$|G_x|$は等しいので代表元だけ残す。

f:id:pekempey:20160607152835p:plain

step 5:$\sum_{x \in R} |G|$:ぎゅっと縮める。

f:id:pekempey:20160607134103p:plain:w400

例題

yukicoder の No.377 背景パターン - yukicoder を Burnside の定理で解いてみよう。

Burnside の定理は$G$ が何であるかを考えるのが重要。$X$ はサイズしか変わる余地が無いので、さほど気にする必要はない。

Gx 軸方向の1回転 \alphay 軸方向の1回転 \beta を使うことで、

$$ G=\{(\alpha^i, \beta^j) \mid 0\le i \lt H, 0 \le j \lt W \} $$

と表せる。

$g=(\alpha^i, \beta^j)$ としたとき、$g$ を作用させても変化しない塗り分け方を考えてみる。

$$(0,0) \to (i,j) \to (2i, 2j) \to (3i, 3j) \to \cdots \to (0,0) $$

というサイクルに含まれている地点はすべて同じ色である必要がある。このサイクル長は $(\alpha^i,\beta^j)$ の位数と一致する。

一般に直積分解された群 $G=A \times B$ の元 $(a,b)$ の位数は $\mathrm{lcm}(\mathrm{ord}(a), \mathrm{ord}(b))$ になる。 このことを踏まえると、$(\alpha^i,\beta^j)$の位数は

$$\mathrm{lcm}(H/\mathrm{gcd}(i,H), W/\mathrm{gcd}(j,W))$$

となる。これは gcd(i,H) と gcd(j,W) にしか依らないので、(gcd(i,H),gcd(j,W)) が等しい(i,j)をまとめて計算すれば結構速い。

これは完全に余談だけど、Z/mZ を中国剰余定理で直積分解してから lcm すると Carmichael の定理が示せる。
yukicoder で突然 Burnside の定理がでてきて良くわからなかったので真面目に証明した。 群論に慣れてしまったせいで初等整数論を忘れかけている。