バーンサイドの補題（コーシー・フロベニウスの定理）の解説・使用例・証明

昨日の AtCoder Beginner Contest で，バーンサイドの補題を使う問題が出題されました．
AtCoder Beginner Contest 198: F - Cube

この記事では，上の問題を例題としてバーンサイドの補題の使い方を説明し，バーンサイドの補題を証明します．代数学の知識は仮定しません．代数の知識がある方には，冗長もしくは不正確に感じられるかもしれません．

バーンサイドの補題は，コーシー・フロベニウスの定理とも呼ばれます．また，プログラミングコンテストチャレンジブック（通称: 蟻本）では，同じ定理がポリアの数え上げ定理として紹介されていますが，ポリアの数え上げ定理は，バーンサイドの補題を一般化したより強い定理を指すことが多いようです．

バーンサイドの補題とは

バーンサイドの補題を，競技プログラミングで使う形で書くと以下のようになります:

上の式に登場する $| \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$ 要素に移動したものです¹．$g$ の逆置換 $g^{-1} = (g^{-1}_1, \dots, g^{-1}_n)$ を使うと，$gx = (x_{g^{-1}_1}, \dots, x_{g^{-1}_n})$ とも書けます．

このように定めると，$(hg)x = h(gx)$ という「結合則」が成り立つことが分かります²．このことは証明で使います．

$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

出典: 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 のアルゴリズムを用いて求めています．
  参考文献:
  • 線形漸化式を満たす数列の N 項目を計算するアルゴリズム（簡潔）
  • 線形漸化的数列のN項目の計算 - Qiita（詳細）

#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| = |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

1. このような演算は，代数学では積ではなく「作用」と呼ばれます．
2. $hg$ と $gx$ は異なる演算なので「結合則」というのは不正確かもしれません．