昨日の AtCoder Beginner Contest で，バーンサイドの補題を使う問題が出題されました．
AtCoder Beginner Contest 198: F - Cube
この記事では，上の問題を例題としてバーンサイドの補題の使い方を説明し，バーンサイドの補題を証明します．代数学の知識は仮定しません．代数の知識がある方には，冗長もしくは不正確に感じられるかもしれません1．
バーンサイドの補題は，コーシー・フロベニウスの補題とも呼ばれます．また，プログラミングコンテストチャレンジブック（通称: 蟻本）では，同じ定理がポリアの数え上げ定理として紹介されていますが，ポリアの数え上げ定理は，バーンサイドの補題を一般化したより強い定理を指すことが多いようです．
バーンサイドの補題とは
バーンサイドの補題を，競技プログラミングで使う形で書くと以下のようになります:
以下が与えられる:
- $n$ 個の要素の組 $(x_1, x_2,\dots, x_n)$ からなる有限集合 $X$，
- $n$ 個の要素の置換の集合 $G$．
$X$ の要素のうち，$G$ による置換で一致するものを同一視して，$X$ の相異なる要素の個数を求めたい．そのためには，以下を計算すればよい: \[ \frac{1}{|G|} \sum_{g \in G} | \set{x \in X \mid gx = x} |. \]
上の式に登場する $| \set{x \in X \mid gx = x} |$ は，「要素の置換 $g \in G$ により不変であるような $x \in X$ の個数」という意味です．
用語・記法の説明
この記事において，置換とは $n$ 個の要素を並べ替える操作を指します．置換は $n$ 個の整数の組として表せます．置換 $(g_1, \dots, g_n)$ と書いたら，各 $i =1,\dots, N$ に対し，$i$ 番目の要素を $g_i$ 番目に移動させるような置換を指すこととします．
恒等置換とは，置換 $(1,2,\dots,n)$ を指します．つまり，要素の順序を一切変更しない置換です．
$2$ つの置換 $g = (g_1, \dots, g_n), $ $h = (h_1, \dots, h_n)$ に対し，その積 $hg$ は置換 $(h_{g_1}, \dots, h_{g_n})$ を表します．つまり置換 $hg$ は，要素を $g$ で並べ替えたあと，$h$ で並べ替えることを表します．$g, h$ の順番に注意してください．
置換 $g$ の逆置換を $g^{-1}$ と書きます．$g$ の逆置換とは，積 $hg$ が恒等置換 $(1,2,\dots,n)$ に等しくなるような置換 $h$ です．そのような $h$ はただ一つ存在します．
$n$ 要素の組 $x = (x_1, \dots, x_n)$ と置換 $g = (g_1, \dots, g_n)$ に対し，その積 $gx$ は $x$ の要素を $g$ により並べ替えたものを表します．つまり積 $gx$ は，$x$ の第 $i$ 要素を第 $g_i$ 要素に移動したものです2．$g$ の逆置換 $g^{-1} = (g^{-1}_1, \dots, g^{-1}_n)$ を使うと，$gx = (x_{g^{-1}_1}, \dots, x_{g^{-1}_n})$ とも書けます．
このように定めると，$(hg)x = h(gx)$ という「結合則」が成り立つことが分かります3．このことは証明で使います．
$X, G$ についての条件
バーンサイドの補題が成り立つためには，$X, G$ が次の条件を満たしている必要があります:
- 任意の $g, h \in G$ に対し $h g \in G$（積について閉じている）
- $(1,2,\dots,n) \in G$（恒等置換の存在）
- 任意の $g \in G$ に対し $g^{-1} \in G$（逆置換の存在）
- 任意の $x \in X$ と $g \in G$ に対し $gx \in X$．
これらは「満たしてないといかにもヤバそう」な，かなり弱い条件です．競技プログラミングで現れる「回転（や反転）で一致するものは同一視する」という状況では，これらの条件は満たされます．
使用例
例題: ABC198: F - Cube
立方体の各面に $1$ つずつ正の整数を書きます．書かれた $6$ つの数の和が $S$ になるような書き込み方は何通りありますか？ ただし，立方体を回転したときに一致するような書き込み方は区別しないものとします（数に向きはありません）．
出典: AtCoder Beginner Contest 198: F - Cube
解法概要
$n = 6$ です．立方体の各面に $1,\dots, 6$ と添字に対応する番号をふり，集合 $X$ を \[ X := \set{ (x_1,\dots, x_6) \in \Z_{>0}^6 \mid x_1 +\dots + x_6 = S } \] と定めます．立方体の回転を考慮しない場合は，$X$ の要素数 $|X|$ が答えです．
立方体の回転を考慮するためにバーンサイドの補題を使います．
回転を表す添字（＝立方体の面）の置換の集合を $G$ とします．$G$ の要素数は $|G| = 24$ です．この $24$ 個の各置換について，置換により不変な $x \in X$ の個数を求めます．
例えば，
- $(1, 2, 3, 4, 5, 6) \in G$ という置換により不変な $x \in X$ は，$X$ の要素全てなので，その個数は $|X|$ です．
- $(1, 3, 5, 2, 4, 6) \in G$ という置換により不変な $x = (x_1,\dots, x_6) \in X$ は，$x_2 = x_3 = x_4 = x_5$ なるものです．そのような $x$ の個数は $x_1 + 4x_2 + x_6 = S$ という方程式の解の個数に等しいです．
このように全て計算し，それらの総和を求め，$|G| = 24$ で割ると答えが得られます．
$24$ 通りもあるので大変そうに見えますが，実は対称性から本質的には $5$ 通りのみ考えればよいです（詳細省略）．もしくは，$24$ 通りの置換を幅優先探索などで生成することもできます．
実装例
- 回転を表す置換を幅優先探索で生成しています．
- 各置換について，方程式の係数を Union-Find を用いて求めています．
- 方程式の解の個数は形式的冪級数，特に Bostan–Mori のアルゴリズムを用いて求めています．
参考文献:
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep_(i, a_, b_, a, b, ...) for (int i = (a), lim##i = (b); i < lim##i; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
using ll = long long;
using Rot = array<int, 6>;
using mint = modint998244353;
// 24 個の置換を BFS で生成
set<Rot> gen_perm() {
const Rot e = {0, 1, 2, 3, 4, 5};
const vector<Rot> ps = {
{0, 2, 3, 4, 1, 5}, // 1234
{1, 5, 2, 0, 4, 3}, // 0153
};
queue<Rot> que;
set<Rot> S;
que.push(e); S.insert(e);
while (!que.empty()) {
auto p = que.front(); que.pop();
for (auto q : ps) {
rep(i, 6) q[i] = p[q[i]];
if (S.count(q)) continue;
que.push(q); S.insert(q);
}
}
return S;
}
// 有理式 p(x) / q(x) で表される形式的冪級数の x^n の係数を計算
template<class T>
struct bostan_mori {
vector<T> p, q;
bostan_mori(vector<T> &_p, vector<T> &_q) : p(_p), q(_q) {}
void rev(vector<T> &f) const {
int d = f.size();
rep(i, d) if (i&1) f[i] = -f[i];
}
void even(vector<T> &f) const {
int d = (f.size() + 1) >> 1;
rep(i, d) f[i] = f[i<<1];
f.resize(d);
}
void odd(vector<T> &f) const {
int d = f.size() >> 1;
rep(i, d) f[i] = f[i<<1|1];
f.resize(d);
}
T operator[] (ll n) const {
vector<T> _p(p), _q(q), _q_rev(q);
rev(_q_rev);
for (; n; n >>= 1) {
_p = convolution(move(_p), _q_rev);
if (n&1) odd(_p);
else even(_p);
_q = convolution(move(_q), move(_q_rev));
even(_q);
_q_rev = _q; rev(_q_rev);
}
return _p[0] / _q[0];
}
};
// 方程式
// cs[0] x_0 + cs[1] x_1 + ... + cs[k-1] x_{k-1} = s
// の非負整数解 (x_0, ..., x_{k-1}) の個数を計算
mint subcount(vector<int> cs, ll s) {
vector<mint> p{1}, q{1};
for (auto &c : cs) {
vector<mint> f(c+1);
f[0] = 1, f[c] = -1;
q = convolution(q, f);
}
bostan_mori<mint> bm(p, q);
return bm[s];
}
int main() {
ll s; cin >> s;
mint ans = 0;
auto S = gen_perm();
for (auto &p : S) {
dsu uf(6);
rep(i, 6) uf.merge(i, p[i]);
vector<int> c;
for (auto &v : uf.groups()) c.push_back(v.size());
ans += subcount(c, s-6);
}
ans /= S.size();
cout << ans.val() << '\n';
}証明
バーンサイドの補題を，$3$ ステップに分けて証明します．
Step 1
$x \in X$ を一つ固定します．$x$ を $G$ の要素で置換して得られるもの全体の集合を $Y_x \subseteq X$ とおきます．つまり，\[ Y_x := \set{gx \mid g \in G} \] です．
$X$ の要素のうち $G$ による置換で一致するものを同一視しない場合，同一視する場合に比べて，$x$ は $|Y_x|$ 倍多く数えられます．よって，求めたい値は \[ \sum_{x \in X} \frac{1}{|Y_x|} \] と書けます．
各要素 $y \in Y_x$ に対し，$x$ から $y$ を得る置換，すなわち $y = gx$ となる $g \in G$ は複数ありえますが，そのうち一つを任意に選びます．これをすべての $y \in Y_x$ について集めたものを $R_x \subseteq G$ とおきます．
もちろん，$Y_x$ と $R_x$ の要素数は等しいです．そのため，求めたい値は \begin{equation} \label{sum-r} \sum_{x \in X} \frac{1}{|R_x|} \end{equation} とも書けます．
Step 2
再度 $x \in X$ を固定します．$x$ を変化させないような置換の集合を $H_x \subseteq G$ とおきます．つまり，\begin{equation} \label{def-h} H_x := \set{g \in G \mid gx = x} \end{equation} です．
実は，任意の置換 $g \in G$ は，$2$ つの置換 $h \in H_x, $ $r \in R_x$ を用いて \[ g = rh \] とただ一通りに表すことができます．証明は難しくないです．
まず，$g = rh$ となる $(h, r) \in H_x \times R_x$ が $1$ 通り以上存在することを示します．
$gx = rx$ を満たすように $r \in R_x$ を定めます（$R_x$ の定義よりそのような $r$ は存在します）．さらに，$g = rh$ を満たすように $h = r^{-1} g$ と定めます．このとき $hx = r^{-1} g x = r^{-1} rx = x$ より $h \in H_x$ です．これで $1$ 通り以上存在することが示せました．
次に，$(h, r)$ が $2$ 通り以上存在しないことを示します．$(h_1, r_1), (h_2, r_2) \in H_x \times R_x$ に対し「$r_1 h_1 = r_2 h_2$ ならば $(h_1, r_1) = (h_2, r_2)$」を示します．
$r_1 h_1 = r_2 h_2$ より，$r_1 h_1 x = r_2 h_2 x$ つまり $r_1 x = r_2 x$ が成り立ちます．これと $R_x$ の定義より，$r_1 = r_2$ となります．$r_1 h_1 = r_2 h_2$ の両辺に左から $r_1^{-1} = r_2^{-1}$ をかけると，$h_1 = h_2$ となります．よって $(h_1, r_1) = (h_2, r_2)$ です．
このことから，\[ |G| = |R_x| |H_x| \]という重要な式が得られます．これを式 \eqref{sum-r} と組み合わせると，求めたい値は \begin{equation} \label{sum-h} \frac{1}{|G|} \sum_{x \in X} |H_x| \end{equation} に等しいことが分かります．
Step 3
式 \eqref{sum-h} を計算します．$H_x$ の定義 \eqref{def-h} を思い出しながら和の順序交換をすると，\begin{align*} \frac{1}{|G|} \sum_{x \in X} |H_x| &= \frac{1}{|G|} \sum_{x \in X} \sum_{g \in G} {\1}[gx = x] \\ &= \frac{1}{|G|} \sum_{g \in G} \sum_{x \in X} {\1}[gx = x] \\ &= \red{\frac{1}{|G|} \sum_{g \in G} | \set{x \in X \mid gx = x} | } \end{align*} となります．これで証明が完了しました！
Project Euler の例題
記事公開後，maspy さんに Project Euler の例題を教えていただきました．ありがとうございます．
- https://projecteuler.net/problem=599
- https://projecteuler.net/problem=626
- https://projecteuler.net/problem=651
