定期宣伝

弊社はエンジニアを熱烈募集しています．以下から気軽にカジュアル面談申し込んでください．就職・転職を考えている知人にも積極的に宣伝してください．

この勉強会の宣伝もお願いします．参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会で実況や感想，質問を呟くなども．

バーンサイドの補題

競プロでよく聞くのは「ポリアの数え上げ定理」なのでタイトルはそうしていますが、「バーンサイドの補題」との違いが分からなかったのでそっちで解説します。 https://atcoder.jp/contests/abc198/tasks/abc198_f のような重み付きの場合を「ポリアの数え上げ定理」と呼ぶらしい？

補題の主張

有限群 $G$ が有限集合 $X$ に作用するとき、以下が成立する。

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

ここで $X/G$ は $G$ の作用で行き来する $X$ の要素を同一視したもので、 $X^g$ は $X$ の元のうち $G$ の元 $g$ を作用しても値が変わらないもの。

群論の知識が必要なのでこれを理解することは一旦諦めて、巡回群の場合の具体例を考える。

巡回群の問題

問題

$n$ 個の石が並んでいる。各石を $m$ 色で塗る方法は何通りか。

答え

各石の塗り方が $m$ 通りで、石が $n$ 個なので $m^n$ 通り。

問題

$n$ 個の石が円状に並んでいる。各石を $m$ 色で塗る方法は何通りか。ただし回転して同じになる塗り方は同一視する。

$n=4, m=2$ の場合 6 通り