2023-11-08

バーンサイドの補題について

はじめに

ABC198-F でバーンサイドの補題を知ったので、自分なりにまとめた記事です。

一応、群論の知識を仮定せずに読めるようにしてあるはずです。

はじめに
用いる記法など
群について
- 代表的な群
同値関係
- 同値関係の例
剰余類
- 剰余類による同値関係
  - 剰余類による同値関係の例
- 剰余集合
群の作用
群の軌道 / 安定化群と不動点集合
- 群作用による同値関係
バーンサイドの補題
参考文献

用いる記法など

$\mathbb{Z}$ : 整数全体の集合のこと。
$\mathbb{R}$ : 実数全体の集合のこと。
$|X|$ : 集合 $X$ の要素数のこと。
$A \cap B$ : 集合 $A$ と集合 $B$ の共通部分のこと。
$x \in X$ : $x$ が集合 $X$ の要素であるということ。
$G \times X$ : 基本的に $G$ と $X$ の積、 $G,X$ が集合である場合には集合 $\{(g,x) | g \in G,x \in X\}$ のこと。
$\emptyset$ : 空集合のこと。

群について

ある集合 $G$ があって、その集合の中の要素だけで行う二項演算 $\star$ を考えます。 (つまり、任意の $a, b\in G$ に対して $a \star b \in G$ を満たしています。)

この時、 $G$ が以下のすべての条件

任意の $a,b,c \in G$ に対し $(a \star b) \star c = a \star (b \star c)$ が成り立つ。 (結合法則)
ある $e \in G$ が存在して、すべての $a \in G$ に対して $e \star a = a \star e = a$ となる。(単位元の存在)
任意の $a \in G$ に対し、 $a \star a^{-1} = a^{-1} \star a = e$ となるような $a^{-1} \in G$ が存在する。 (逆元の存在)

を満たすとき、 $G$ を群と呼び、 $G$ は演算 $\star$ に関して群をなすと言います。

競プロer が知っていそうな代数的構造ナンバーワンのモノイド (セグ木に乗るやつです) に逆元の存在を付け加えた形になります。

代表的な群

★ 実数全体の集合 (加法について)

$\mathbb{R}$ は加法について群をなします。群の定義を満たすか確認してみると、

結合法則: 任意の実数 $a,b,c$ に対し $(a+b)+c = a+(b+c)$ より、結合法則が成り立っていると分かります。
単位元の存在: 任意の実数 $a$ に対し、 $e + a = a + e = a$ ですからこれを解いて $e = 0$ を得て、単位元が存在していることがわかります。
逆元の存在: 任意の実数 $a$ に対し、 $a + (-a) = (-a) + a = e$ で、単位元 $e$ が $0$ であることからこれを解いて $a^{-1} = -a$ を得て、逆元が存在していることがわかります。

以上より、 $\mathbb{R}$ は加法に対して群をなすことが分かりました。この群のことを $\mathbb{R}^{+}$ と書くこともあります。

加法に関して、実数全体の集合は上の三つ以外に大切な性質として交換法則 $a+b = b+a$ が成り立っています。

このように交換法則が成り立っている群のことを、アーベル群や可換群と呼びます。

★ 実数全体の集合から $0$ を除いたもの (乗法について)

$\mathbb{R}$ は加法について群をなしますが、乗法についてだとそうはいきません。 $0$ を含めた場合に定義を満たすか確認してみましょう。

結合法則: 任意の実数 $a,b,c$ に対し $(a \times b) \times c = a \times (b \times c)$ より、結合法則が成り立っていると分かります。
単位元の存在: 任意の実数 $a$ に対し $a \times e = e \times a = a$ であるから、これを解いて $e = 1$ を得て、単位元が存在していることがわかります。
逆元の存在: 任意の実数 $a$ に対し、 $aa^{-1} = a^{-1}a = 1$ となるような $a^{-1}$ を考えると、一見 $a^{-1} = \frac{1}{a}$ とすればよさそうに見えますが $a=0$ において $\frac{1}{a}$ は定義できません。

以上のことから、 $\mathbb{R}$ は乗法について群をなしませんが、 $\mathbb{R}$ から $0$ を除いた集合は乗法について群をなすことが分かりました。この群のことを $\mathbb{R}^{\times}$ と書くこともあります。

★ $n$ 次の置換の全体集合 (関数の合成について)

全単射 *1 であるような関数 $\sigma: \{1,2,3, \cdots, n\} \to \{1,2,3, \cdots, n\}$ *2　を考えます。

$1,2,3,\cdots,n$ を順に代入していくとそれぞれ $\sigma(1),\sigma(2),\sigma(3),\cdots,\sigma(n)$ となりますが、 $\sigma$ が全単射であったことを思い出すと、これは $1,2,3,\cdots, n$ をそれぞれ異なる数字(元の数字と行き先の数字は同じでもよい)に置換しています。

このことから、上の条件を満たすような写像 $\sigma$ のことを $n$ 次の置換と呼びます。

また、このような置換を

$\displaystyle \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(n) \\ \end{pmatrix} \\$

と書くこともあります。

例えば、 $3$ 次の置換 $\sigma$ を $\sigma(1) = 2, \sigma(2) = 1, \sigma(3) = 3$ とすると、この置換は

$\displaystyle \begin{pmatrix} 1 & 2 & 3\\ 2 & 1 & 3\\ \end{pmatrix} \\$

と書くことができます。

ここで、 $n$ 次の置換全体の集合を関数の合成に対して考えます。置換に対する関数の合成は例えば、

$\sigma _1 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \sigma _2 = \begin{pmatrix} 1 & 2 & 3\\ 3 & 2 & 1\\ \end{pmatrix}$

と定めたとき、

$\sigma_1 \circ \sigma_2 = \begin{pmatrix} 1 & 2 & 3\\ \sigma_2(\sigma_1(1)) & \sigma_2(\sigma_1(2)) & \sigma_2(\sigma_1(3)) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \\$

$\sigma_2 \circ \sigma_1 = \begin{pmatrix} 1 & 2 & 3\\ \sigma_1(\sigma_2(1)) & \sigma_1(\sigma_2(2)) & \sigma_1(\sigma_2(3)) \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3\\ 3 & 1 & 2 \end{pmatrix} \\$

のように計算できます。上の二つの例と異なり、交換法則が成り立たない点に注意しましょう。

ここで、

結合法則: $n$ 次の置換 $\sigma_1, \sigma_2, \sigma_3$ に対して、 $(\sigma_1 \circ \sigma_2)(\sigma_3) = \sigma_1(\sigma_2(\sigma_3)) = \sigma_1 \circ (\sigma_2 \circ \sigma_3)$ であることより、結合法則が成り立つと分かります。
単位元の存在: $n$ 次の置換 $e: \{1,2,3, \cdots, n \} \to \{1,2,3,\cdots, n\}$ を、 $e(1) = 1, e(2) = 2, \cdots, e(n) = n$ とすれば、任意の $n$ 次の置換 $\sigma$ に対し、 $e \circ \sigma = \sigma \circ e = \sigma$ が成り立つため、単位元が存在しているとがわかります。
逆元の存在: 任意の $n$ 次の置換 $\sigma$ について、 $\sigma ^{-1}$ を $1 \leq i \leq n$ を満たすすべての $i$ に対し、 $\sigma^{-1}(\sigma(i)) = i$ となるように定めると、 $\sigma$ が全単射であることから $\sigma^{-1}$ も全単射であり、 $n$ 次の置換です。これより、逆元が存在していると分かります。

より、 $n$ 次の置換全体の集合は関数の合成について群をなすことが分かりました。

このような群のことを $\mathfrak{S}_n$ と書き、 $n$ 次対称群と呼びます。

同値関係

突然ですが、バーンサイドの補題への準備として、同値関係を扱います。

ある集合 $X$ 上において、任意の $X$ の二つの要素同士についてある関係 $\sim$ が定義されているとき、

任意の $x \in X$ に対して、 $x \sim x$ (反射律)
任意の $x,y,z \in X$ に対して、 $x \sim y$ かつ $y \sim z$ ならば $x \sim z$ (推移律)
任意の $x,y \in X$ に対して、 $x \sim y$ ならば $y \sim x$ (対称律)

がすべて成り立つのならば、このような関係を同値関係と呼びます。

同値関係という名前の通り、ある視点から見た際にその要素を同一視してもよいようなもの同士の関係であることが主です。

今後、群上で同値関係を定めたりします。

同値関係の例

★ 余りによる同値関係

$m$ を $1$ より大きい整数としたとき、整数全体の集合の要素に対して $m$ で割った余りが等しいような関係は同値関係です。このような同値関係を $\equiv (\mathrm{mod} \ m)$ などと書きます。

皆さん $m = 998244353$ などでお馴染みなのではないのでしょうか？実際に同値関係か確認してみましょう。

反射律: 任意の整数 $x$ に対して、 $x \equiv x \ (\mathrm{mod} \ m)$ ですから、反射律は成り立っています。
推移律: 任意の整数 $x,y,z$ に対して、 $x \equiv y \ (\mathrm{mod} \ m)$ かつ $y \equiv z \ (\mathrm{mod} \ m)$ であるとき、 $x \equiv z \ (\mathrm{mod} \ m)$ ですから、推移律は成り立っています。
対称律: 任意の整数 $x,y$ に対して、 $x \equiv y \ (\mathrm{mod} \ m)$ ならば $y \equiv x \ (\mathrm{mod} \ m)$ ですから、対称律は成り立っています。

よって $\equiv (\mathrm{mod} \ m)$ が同値関係であると分かりました。

剰余類

$G$ を演算 $\star$ に関して群をなし、 $H$ を $G$ の部分集合であって $\star$ に関して群をなすとします。*3このとき任意の $g \in G$ に対して、

$gH = \{g\star h \ | \ h \in H \}$

を $g$ による $H$ の左剰余類と呼び、

$Hg = \{h \star g \ | \ h \in H \}$

を $g$ による $H$ の右剰余類と呼びます。

剰余類による同値関係

$G,H$ には上の仮定が成り立っているとします。このとき以下が成り立つことが知られています。(証明略)

任意の $a, b \in G$ に対し、 $aH = bH$ もしくは $aH \cap bH = \emptyset$
任意の $a, b \in G$ に対し、 $Ha = Hb$ もしくは $Ha \cap Hb = \emptyset$
任意の $a, b \in G$ に対し、 $aH = bH \Leftrightarrow a^{-1} \star b \in H$
任意の $a, b \in G$ に対し、 $Ha = Hb \Leftrightarrow a \star b^{-1} \in H$

ここで、任意の $a, b \in G$ に対し関係 $a \sim b$ を $aH = bH$ であることと定めると、これは同値関係です。 $a \sim b$ を $Ha = Hb$ であることとしても、同様に同値関係になります。

このことから、剰余類による同値関係は $G$ の要素に対してある種の分類を与えているとわかります。

剰余類による同値関係の例

★ 整数全体の集合と $3$ の倍数全体の集合からなる部分群による同値関係 (加法について)

$\mathbb{Z}$ は加法について群をなします。(実数の場合と同様です)

ここで、 $H$ を $H = \{0, \pm 3, \pm 6, \cdots \}$ と定めると、これは $\mathbb{Z}$ の部分群になっています。

$H$ に対して上のような同値関係を考えましょう。加法は交換法則が成り立つので、左剰余類と右剰余類のどちらを考えてもよいです。ここでは左剰余類を考えます。

少し考えると、 $x,y \in \mathbb{Z}$ に対して $x \sim y$ であることと $x \equiv y \ (\mathrm{mod} \ 3)$ であることは同値です。 $x \equiv y \ (\mathrm{mod} \ 3) \Rightarrow x \sim y$ を示します。

適当に選んできた $x \in \mathbb{Z}$ が $x \equiv n \ (\mathrm{mod} \ 3) \ (0 \leq n \leq 2)$ であったとき、任意の $a \in H$ について $a+x \equiv n \ (\mathrm{mod} \ 3)$ であるため、 $aH = \{3m + n \ | \ m \in \mathbb{Z}\}$ と分かります。

したがって $x \equiv y \ (\mathrm{mod} \ 3) \Rightarrow x \sim y$ です。逆も仮定を $aH = \{3m + n \ | \ m \in \mathbb{Z}\}$ から始めることで容易に示せます。

これより、 $\mathbb{Z}$ の $H$ による同値関係は上で考えた $a \equiv b \ (\mathrm{mod} \ 3)$ と同値と分かります。

また、この同値関係によって $\mathbb{Z}$ は三種類の集合に分けることができます*4。

このような剰余類による同値関係での分類の個数を $|G : H|$ と書き、部分群 $H$ の指数と呼びます。左剰余類と右剰余類による分類の個数は等しいことが知られており(後に証明します)、どちらか区別できなくてもよい記法になっています。

剰余集合

$G$ を群、 $H$ を $G$ の部分群とします。この時、

$G/H = \{gH \ | \ g \in G \}\\$

を左剰余集合、

$H \backslash G = \{Hg \ | \ g \in G \}\\$

を右剰余集合と呼びます。これは先ほど $\mathbb{Z}$ を $H = \{0, \pm 3, \pm 6, \cdots \}$ で分類していたのと同じことをしています。

実際、この定義において $G = \mathbb{Z}, H = \{0, \pm 3, \pm 6, \cdots \}$ と置けば、 $G/H = H \backslash G = \{\{3m+n \ | \ m \in \mathbb{Z}\} \ | \ n \in \mathbb{Z} \} = \{\{3m+n \ | \ m \in \mathbb{Z}\} \ | \ 0 \leq n \leq 2 \}$ となって先ほどの分類と一致します。

ここで証明を保留した「左剰余類と右剰余類による分類の個数は等しい」、つまり $|G/H| = |H \backslash G|$ を示しましょう。

▼ 証明 (長めなので折り畳み) / クリックで展開

これと同じような方法によって示せるものとして、 $|gH| = |Hg| = |H|$ があります。概略としては、 $f: H \to gH$ を任意の $h \in H$ に対して $f(h) = gh$ と定めて、これが全単射であることを示せばよいです。

ここで、 $f(h_1) = f(h_2) \Leftrightarrow gh_1 = gh_2 \Leftrightarrow h_1 = h_2$ より、 $f$ は単射です。全射性は定義より明らかなので、 $f$ の全単射性が示せました。

また、剰余集合における基本的な定理として、以下があります。

ラグランジュの定理

上の状況で

$|G| = |G:H| |H| \\$

が成り立つ。特に $G$ の要素数が有限であるとき、部分群の要素数は $|G|$ の約数だとだとわかる。

証明

$|G| = \infty$ のとき主張は明らかであるため、そうでないときのみを示せばよいです。

$G/H = \{g_1H, g_2H, \cdots, g_{|G:H|} H\}$ となるように $g_1, g_2, \cdots, g_{|G:H|} \in G$ を取ると、 $\displaystyle |G| = \sum_{i=1}^{|G:H|} |g_i H|$ です。

ここで $|gH| = |H|$ より、 $\displaystyle \sum_{i=1}^{|G:H|} |g_i H| = \sum_{i=1}^{|G:H|} |H| = |G:H| |H|$ ですから、 $|G| = |G:H| |H|$ と分かりました。

群の作用

ここから対称性を考える数え上げっぽい話になってきます。

突然ですが、以下のような問題を考えましょう。

問題 (ABC198-F Cube の弱体化 ver.) 正整数 $S$ が与えられます。
正三角形の三つの頂点上に正整数を書き込む方法のうち、その三つの頂点に書かれた数の和がちょうど $S$ となるような書き込み方はいくつあるでしょうか？
ただし回転/反転によって一致するようなものは区別しないとします。

もちろんこれは対称性を考えずに一度全列挙してから、重複を除く処理をして数え上げることもできます。

しかし、もっと効率的な解法が欲しいとなった場合どうすればよいでしょうか。

ここで回転と反転という操作に着目してみると

上の六つの操作が回転や反転を行う方法すべてであると分かります。

これらの操作は、実は $3$ 次の置換全体の集合 (つまり三次対称群) と同一視することができます。

なぜならば、これらの操作は ある点をほかの点へ置換する 操作と言い換えることができ、これはまさに置換の定義と同様だからです。

したがって、三角形の回転と反転による操作は、ある $3$ 次の置換 $\sigma \in \mathfrak{S}_3$ があって、 $\{1,2,3\}$ の順列 $A$ を $\{\sigma(A_1),\sigma(A_2),\sigma(A_3)\}$ へと置き換えるような操作へ言い換えることができます。このようにある群の要素によって集合に行う操作を、 群作用と呼びます。

より形式的な定義をします。

$G$ を $\star$ に対して群、 $e$ を $G$ の単位元、 $X$ を集合とすると、関数 $f_1: G \times X \to X$ が以下の条件

全ての $x \in X$ に対して、 $f_1(e,x) = x$
全ての $g_1 , g_2 \in G , x \in X$ に対して、 $f_1(g_1, f_1(g_2,x)) = f_1(g_1 \star g_2,x)$

を満たすとき、 $f_1$ を $G$ の $X$ への左作用と呼び、

また、関数 $f_2: X \times G \to X$ が以下の条件

全ての $x \in X$ に対して、 $f_2(x,e) = x$
全ての $g_1, g_2 \in G, x \in X$ に対して、 $f_2(f_2(x,g_1),g_2) = f_2(x,g_1 \star g_2)$

を満たすとき、 $f_2$ を $G$ の $X$ への右作用と呼びます。

$G$ から $X$ への右作用もしくは左作用が存在するならば、 $G$ は $X$ に作用するといいます。

この記事ではこれ以降、断りのない限り左作用であるとし $f(x,g)$ を単に $xg$ と書きます。

先ほどの例では、 $G = \mathfrak{S}_3,X =(\{1,2,3\}$ の順列の全体集合 $)$ とすると、

$f: G \times X \to X$ を任意の $g \in G, x \in X$ に対して $f(x,g) = \{g(x_1),g(x_2),g(x_3)\}$ と定めればよいです。

群の軌道 / 安定化群と不動点集合

群 $G$ が集合 $X$ に対して作用しているとします。このとき、 $x \in X$ に対して

$Gx = \{gx \ | \ g \in G\}$

を $x$ の $G$ による軌道と呼び、

$G_x = \{g \in G \ | \ gx = x\}$

を $x$ の安定化群と呼びます。

また、 $g \in G$ に対して

$X^g = \{x \in X \ | \ gx = x\}$

を $g$ の不動点集合と呼びます。

それぞれのお気持ちとしては、

軌道: $x$ に対して操作を繰り返したときにできるパターンの集合
安定化群: $x$ を変化させないような操作の集合
不動点集合: 操作 $g$ に対して不変であるようなパターンの集合

のような感じです。

安定化群に対して、以下の定理は基本的です。

軌道安定化群定理

任意の $x \in X$ について、上の状況で

$|G/G_x| = |Gx|$

が成り立つ。

証明

関数 $f: G/G_x$ を任意の $gG_x \in G/G_x$ に対して $f(gG_x) = gx$ と定めます。この関数が well-defined であることを確認しましょう。

$g_1, g_2 \in G$ が $g_1 G_x = g_2 G_x$ を満たすとします。この時

$g_1 G_x = g_2 G_x \Leftrightarrow g_2 ^{-1} g_1 G_x = G_x \Leftrightarrow g_2^{-1} g_1 \in G_x \Leftrightarrow g_2^{-1} g_1x = x \Leftrightarrow g_1x = g_2x$

であるため、 $f$ は well-defined です。さらにこれらはすべて同値であることから、 $f$ が全単射であることも従います。

したがって $G/G_x$ の要素と $Gx$ の要素は一対一対応し、 $|G/G_x| = |Gx|$ が示せました。

群作用による同値関係

剰余類を考えたときと同じような関係を定義します。

群 $G$ が集合 $X$ に対して作用しているとしたとき、 $x, y \in X$ に対して、関係 $x \sim y$ を $Gx = Gy$ であることと定めます。このとき関係 $\sim$ は同値関係です。

ここで $Gx = Gy$ であることの意味を考えてみると、これは対称性を考慮したとき $x$ と $y$ を同一視してもよいととらえることができます。ここで、

$X/G = \{Gx \ | \ x \in X\}$

と定めれば、本質的には $|X/G|$ を求めることによって対称性を考慮した数え上げができると分かります。

バーンサイドの補題

いよいよ本題(補題ですが)です。まずは主張を確認してみましょう。

バーンサイドの補題

有限群 $G$ が有限集合 $X$ に作用しているとする。このとき

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

が成り立つ。

砕けた言葉で言いかえれば「対称性を考えたときの数え上げの答えは各操作に対して不変なものに対する答えの総和を操作の種類数で割ったものに等しい」となります。

これを用いて先ほどの問題を解いてみましょう。

問題正整数 $S$ が与えられます。
正三角形の三つの頂点上に正整数を書き込む方法のうち、その三つの頂点に書かれた数の和がちょうど $S$ となるような書き込み方はいくつあるでしょうか？
ただし回転/反転によって一致するようなものは区別しないとします。

解法

先ほど行った議論から、回転に関しては $G = \mathfrak{S}_3$ とすればよいです。

また、 $X = (三つの正整数からなる総和が \ S \ である順序集合全体の集合)$ とし、 $f: G \times X \to X$ を任意の $g \in G, x \in X$ に対して $f(g,x) = (x_{g(1)},x_{g(2)},x_{g(3)})$ とすると、 $f$ は左作用です。

あとは地道に $g \in G$ によって場合分けを行っていきましょう。

(i) $g(1) = 1, g(2) = 2, g(3) = 3$ のとき

　　このとき $|X^{g}|$ は $s + t + u = S$ なる $(s,t,u)$ の組の数に等しいです。

(ii) $g(1) = 3, g(2) = 1, g(3) = 2$ のとき

　　このとき任意の $x \in X^{g}$ は $x_1 = x_2, x_2 = x_3, x_3 = x_1$ であるため、 $|X^{g}|$ は $S \equiv 0 \ (\mathrm{mod} \ 3)$ であるとき $1$ 、そうでないとき $0$ です。

(iii) $g(1) = 2, g(2) = 3, g(3) = 1$ のとき

　　(ii) と同様に $S \equiv 0 \ (\mathrm{mod} \ 3)$ であるとき $1$ 、そうでないとき $0$ です。

(iv) $g(1) = 3, g(2) = 2, g(3) = 1$ のとき

　　このとき任意の $x \in X^{g}$ は $x_2 = x_3$ を満たします。したがって $|X^{g}|$ は $s + 2t = S$ なる $(s,t)$ の組の数に等しいです。

(v) $g(1) = 3, g(2) = 2, g(1) = 1$ のとき

　　(iv) と同様に $s + 2t = S$ なる $(s,t)$ の組の数に等しいです。

(vi) $g(1) = 2, g(2) = 1, g(3) = 3$ のとき

　　(iv) と同様に $s + 2t = S$ なる $(s,t)$ の組の数に等しいです。

したがってこれらの和を取って $|G| = 6$ で割ればよいです。

上のような組の数を求めるのは例えば Bostan-Mori 法で $O(\log{S})$ 時間になります。

よって、この問題を $O(\log{S})$ 時間で解けました。

使い方もわかったところでバーンサイドの補題を証明していきましょう。

まず以下のような補題の補題を示します。

補題の補題軌道がただ一つ、つまり $|X/G| = 1$ であるとき、以下が成り立つ

$\displaystyle |G| = \sum_{g \in G} |X^g|$

証明

$\displaystyle \sum_{g \in G} |X^{g}|$ の式の形を見ると、 $g \in G$ ごとに $|X^{g}|$ を計算するのは大変ですから、 $x \in X$ ごとに計算したいです。

ここで $G_x$ は $gx = x$ なる $g \in G$ の集合でしたから、結局これを数えればよく

$\displaystyle \sum_{g \in G} |X^{g}| = \sum_{x \in X} |G_x|$

と変形したのち、軌道安定化群定理とラグランジュの定理より

$\displaystyle \sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|Gx|}$

であり、ここで軌道がただ一つであったことより $|Gx| = |X|$ と分かります。したがって

$\displaystyle \sum_{x \in X} \frac{|G|}{|Gx|} = \sum_{x \in X} \frac{|G|}{|X|} = |G|$

より、示すことができました。

これを使ってバーンサイドの補題を示します。

証明

同値な言いかえとして $\displaystyle |X/G||G| = \sum_{g \in G} |X^{g}|$ を示します。

今、補題の補題をうまく使うために軌道ごとに足し合わせていくことにします。このとき

$\displaystyle \sum_{g \in G} |X^g| =\sum_{Y \in X/G} \sum_{g \in G} |Y^{g}|$

と変形すれば、補題より

$\displaystyle \sum_{Y \in X/G} \sum_{g \in G} |Y^{g}| = \sum_{Y \in X/G} |G| = |X/G| |G|$

がわかり、これよりバーンサイドの補題が示せました。

参考文献

[1] 岡本吉央 "離散数理工学第 7 回離散代数：対称性を考慮した数え上げ" (閲覧日: 2023-11-07) http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/dme/lect07.pdf

[2] soratobipenguin "バーンサイドの補題" (閲覧日:2023-11-07) https://soratobipenguin.hatenablog.com/entry/2018/05/05/160718

[3] 雪江明彦 "代数学1 群論入門" 日本評論社 2010

*1:砕けた言葉で言うと、関数の中身に入るようなものの集合と関数によって移されたものの集合の要素がそれぞれ一対一対応していることです。

*2: $\sigma$ に $1$ から $n$ までのどれかの整数を代入すると $1$ から $n$ までのどれかの整数一つが返ってくることを言っています。

*3:このような $H$ を部分群と呼びます。

*4: $\mathrm{mod} \ 3$ で分類しているのと同じです。

2023-10-14

Wolfram Alpha / Wolfram Script を競プロで使おう！

注意

本記事には ABC154-F およびエイシングプログラミングコンテスト2020-F のネタバレが含まれます。

本題

皆さん、 Woflram Alpha を使ったことはありますか？　私はあります。

さて、Wolfram Alpha だと入力長制限や実行時間制限で計算できないことがあって若干煩わしいですよね。

そこで手元実行でそのようなことを気にせず使える Wolfram Script を導入しましょう！

そこまで難しい手順でもないので導入は公式に譲ります。 reference.wolfram.com

実際に使ってみる

ABC154-F Many Many Paths

問題概要

正整数 $L_1, L_2 \ (1 \leq L_1 \leq L_2 \leq 10^{6})$ および $R_1, R_2 \ (1 \leq R_1, R_2 \leq 10^{6})$ が与えられるので、 $\sum_{l=L_1}^{L_2} \sum_{r=R_1}^{R_2} \binom{l+r}{r}$ を $\mathrm{mod} \ (10^{9}+7)$ で求めてください。

解法

とりあえずそのまま式を入力してみます、すると

事前計算のもと $O(1)$ で解ける式を教えてくれます！

これを愚直に実装して AC を得られます。

エイシングプログラミングコンテスト2020-F Two Snuke

問題概要

次の問題を $T \ (1 \leq T \leq 100)$ 個の与えられるケースについて解いてください。

正整数 $N \ (1 \leq N \leq 10^{9})$ が与えられるので、 $0 \leq A_{2i} \lt A_{2i+1} \ (0 \leq i \leq 4)$ かつ $\sum_{i=0}^{9} A_i \leq N$ を満たすようなすべての長さ $10$ の数列 $A$ について、それぞれ $\prod_{i=0}^{4} (A_{2i+1} - A_{2i})$ を計算し、その総和を $\mathrm{mod} \ (10^{9}+7)$ で求めてください。

解法

FPS による考察を用います。

まず立式することを考えると、これは積の和典型のような形をしていますから

$\displaystyle f = \sum_{i=0}^{\infty} \sum_{j=0}^{i-1} (i-j)x^{i+j}$

と定めれば、

$\displaystyle \sum_{i=0}^{N} [x^{i}] f^{5} = [x^N]\frac{f^{5}}{1-x}$

が求めるべき答えであることは明らかです、ここで $f$ を具体的に計算すればあとは Bostan-Mori で殴って終わりそうですので、これを Wolfram に投げつけます。

と求めてくれたので、

$\displaystyle [x^N]\frac{f^{5}}{1-x} = [x^N] \frac{x^{5}}{(1-x)^{16}(1+x)^{5}}$

と分かりました、よって答えは $O(T\log{N})$ で計算できて十分高速に動作し、 AC を得られます。

おまけ

先ほど解いた Two Snuke は $O(T)$ 解法もあるのですが、それも Wolfram で導出できます。

今、求めたい値は $[x^{N}] \frac{x^{5}}{(1-x)^{16}(1+x)^{5}}$ であることがわかっていて、これは $[x^{N-5}] \frac{1}{(1-x)^{16}(1+x)^{5}}$ に等しいですから、これを考えます。

Wolfram 言語で SeriesCoefficient[1/(1-x)^16 1/(1+x)^5,{x,0,n}] と書くと $[x^{N}] \frac{1}{(1-x)^{16}(1+x)^{5}}$ を表せるので、これをターミナルに入力すると超長い式が返ってきます。

一旦 FullSimplify[%] と入力することでこの式を簡約化して

Piecewise (条件分岐用の関数) が邪魔なので InputForm[%] を入力してキーボードで打てる一般的な形にしてから中身をコピーして

その中身も長くて扱いにくいので一度入力して % として扱えるようにしてから、PolynomialMod[%,10^9+7] を入力して剰余をとって

さらにもう一度 InputForm[%] で整えて

いい感じの式を得られました。

あとは Vscode などの置換機能で (スペースと+) を %mod などに置き換えるとコピペで使えるようになります。

実際にほぼコピペで AC したコード: atcoder.jp

2023-09-24

ABC321 F - #(subset sum = K) with Add and Erase があの遷移でいい理由を理解する

わかっていてほしいもの

数 IA の多項式の四則演算

はじめに

ここでは多項式の実装等は扱わず、どうして遷移があのようになるかを取り扱います。また、わかりやすさのために厳密性を欠く記述があります。

本題

dp 配列と多項式を関連付けると嬉しい場合があります、これもそのうちの一つです。

最初からこの問題を考えると難しいので、箱から取り出すことがない場合を考えましょう。

すると、これは以下のように dp 配列を更新することで解けるはずです。

$\displaystyle dp[i] \leftarrow dp[i-x]+dp[i]$

ここで、これを多項式によって書くことを考えます。

仮に、多項式の次数を $i$ に相当するもの、 $y^i$ の係数を $dp[i]$ の中身に相当するものとし、これをどう遷移させるかを考えます。

(具体的には $dp[0]+dp[1]y+dp[2]y^2+\cdots +dp[K]y^k$ という多項式です)

ここで考えていた dp は

$\displaystyle (今の状態) \leftarrow (一つ前の状態) + (一つ前の状態の和に x だけ下駄をはかせたもの)$

と書き直すことができます。

一つ前の状態の和に $x$ だけ下駄をはかせたものというのは、一つ前の状態に $y^x$ を掛けたものに等しいです。

よって、次のように書けることがわかります。

$\displaystyle (今の状態) \leftarrow (一つ前の状態) \times (1+y^x)$

この形のまま、箱から取り出すことがある場合を考えましょう。

問題文から、取り出される際に $(今の状態)$ が $(1+y^x)$ を因数に持つことがわかります。

ここで多項式は乗法について可換ですから、 $(今の状態)$ の一番右に $(1+y^x)$ をもってきて、 $(1+y^x)$ で割って打ち消してしまいましょう。

直感的に乗算と除算は逆の演算ですから、dp として扱う際も逆の操作をすればよさそうです。

したがって、取り出すときの更新は以下のように書けます

$\displaystyle dp[i] \leftarrow dp[i] - dp[i-x]$

よって、この遷移を実装して、 $O(QK)$ 時間でこの問題を解くことが出来ました。

(FPS を用いた提出:提出 #45905788 - サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）)

(dp での提出:https://atcoder.jp/contests/abc321/submissions/45925519)

2023-09-24

入緑記事

始めに

中三の Python 勢です 23/09/23 の ABC321 で入緑したのでやったことなどを書いておこうかと

やったこと

とりあえず精進！精進をしましょう

ちゃんと理解していて、且つ書けるアルゴリズム/データ構造はこんな感じです

二分探索
基本的な dp
bit 全探索
bit dp
BFS/DFS
UnionFind
heapq
Dijkstra 法
Warshall-Floyd 法
Rolling Hash
Segment Tree
BIT
中国式剰余定理
FFT/NTT

上の方が実践で出くわす頻度が高いと思います

とりあえず出逢ったアルゴリズム/データ構造はバンバン記事を読むなどして理解できると良いです！

2023-07-31

ABC276 F - Double Chance を解くときに考えたこと

はじめに

自分の思考を殴り書いているような面があるので、文章の体裁はあまり保たれていませんし、解説もそこまでわかりやすくないです。
また、厳密性を欠くような部分もあると思いますが、ご容赦ください。

問題概要

整数列 $\lbrace A_i \rbrace _{(1 \leq i \leq N)},(1 \leq N \leq 2 \times 10^{5},1 \leq A_i \leq 2 \times 10^{5})$ が与えられます。
$1 \leq K \leq N$ について、以下のクエリに答えてください。

$A$ の部分列 $\lbrace A_i \rbrace _{1\leq i \leq K}$ から無作為に $1$ つの要素を選ぶことを二回繰り返します。(このとき、要素が重複してもよいです)
選ばれた要素のうち最大のものの期待値を有理数 $\mod 998244353$ で出力してください。

とっかかり

とりあえずある $K$ に対する期待値がいくらか考えてみます。
$\lbrace A_i \rbrace _ {(1 \leq i \leq K)}$ がソートされていると嬉しいので、例えば std::multiset などに入れ、ソートされた $\lbrace A_i \rbrace _ {(1 \leq i \leq K)}$ を考えたいです。
混同を防ぐためにソートされた $\lbrace A_i \rbrace _ {(1 \leq i \leq K)}$ を $\lbrace B _ {K _ i} \rbrace _ {(1 \leq i \leq K)}$ と書くことにします。
最初に $B _ {K _ i}$ が選ばれたとき、それが最後まで最大である場合の数を考えてみましょう。
これは二回目で $B _ {K _ i}$ 以下の値を引けばいいですから、 $B _ {K _ i}$ を超えない最大のインデックスを $j _ {K _ i}$ として $j _ {K _ i}$ です。
逆に、二回目で $B _ {K _ i}$ が選ばれたとき、それが最大である場合の数も、 $j _ {K _ i}$ です。
よって、 $B _ {K _ i}$ が最大である場合の数は $2j _ {K _ i}$ であるように思えますが、罠があります。
それは $B _ {K _ i}$ を二回選ぶような方法を重複してカウントしていることです。
よってその分を引いて場合の数は $2j _ {K _ i}-1$ であると分かりました。
したがって求めるべき期待値は $\displaystyle \frac{1}{K^{2}} \sum _ {i=1}^{K} (2j _ {K _ i} -1)B _ {K _ i}$ です。
これを便宜上、 $C _ {K}$ と書くことにします。

計算量改善

さて、これを愚直に計算すると、全体計算量 $O(N^{2})$ になってしまい間に合いません。(ユーザー解説にある通りコンパイル設定をいじれば通せはします)
そこで計算結果を使いまわすことを考えます。
$A _ {K+1}$ が、ソートした結果 $B _ {K+1 _ x}$ に入ったとして、期待値を計算しましょう。
$B _ {K+1 _ x}$ の期待値に対する寄与を考えると、これは $j _ {K+1 _ x}$ が求められれば良いです。
例えば std::multiset::upper_bound 等で $O(\log{K})$ 時間でできます。
次に、 $B _ {K+1 _ x}$ 以外の寄与を考えます。 $1 \leq i \lt x$ であるとき、 $j _ {K +1 _ i} = j _ {K _ i}$ であり、 $x \lt i \leq K+1$ のとき、 $j _ {K+1 _ i} = j _ {K _ {i-1}} +1$ です。
したがって $B _ {K+1 _ x}$ 以外の寄与は

$\displaystyle \dfrac{1}{(K+1)^2} \left(\sum _ {i = 1}^{x-1} (2j _ {K _ i}-1)B _ {K _ i} + \sum _ {i = x+1} ^ {K+1}(2j _ {K _ {i - 1}} + 1) B _ {K _ {i-1}}\right)$ $\displaystyle = \dfrac{1}{(K+1)^2} \left(\sum _ {i = 1}^{K} (2j _ {K _ i}-1)B _ {K _ i} + \sum _ {i = x} ^ {K} 2B _ {K _ i}\right)$ $\displaystyle = \dfrac{1}{(K+1)^2} \left(C _ K + \sum _ {i = x} ^ {K} 2B _ {K _ i}\right)$

と計算できます。
$C _ K$ は使いまわせますから、 $\displaystyle \sum _ {i = x} ^ {K} 2B _ {K _ i}$ を素早く計算することを考えます。区間和なのでセグ木を使いたいな～という気持ちになります。
そこで、重複している場合にインデックスを増やす座圧を行ったうえで、全要素 $0$ で初期化した長さ $N$ のセグ木を作りそこに要素を入れていけばよいです。
こうすると $\displaystyle \sum _ {i = x} ^ {K} 2B _ {K _ i}$ が $O(\log {K})$ で求められました。したがって一クエリあたりの計算量は $O(\log {K})$ であり、総計算量 $O(N \log{N})$ でこの問題に答えることができました。これは十分高速に動作し、 AC を得ることができます。