群
群的定义
给定集合 \(G\) 和二元运算 \(\cdot\) 满足如下性质：
- 封闭性：\(\forall a,b\in G\)，有 \((a\cdot b)\in G\)
- 结合律：\(\forall a,b,c\in G\)，有 \((a\cdot b)\cdot c=a\cdot (b\cdot c)\)
- 存在单位元：\(\exists e\in G\)，使得 \(\forall a\in G\)，有 \(a\cdot e=e\cdot a=a\)
- 存在逆元：\(\forall a\in G\)，\(\exists a'\in G\)，使得 \(a\cdot a'=a'\cdot a=e\)
则称代数结构 \((G,\cdot)\) 为群。
代数结构就是给集合加上若干运算。
notes:
1. 显然 \(G\) 非空。
2. \(\cdot\) 可省略。
3. \(|G|\) 称为群的阶。
一些性质:
- 单位元唯一：设有两个单位元 \(e_1,e_2\),则 \(e_1\cdot e_2=e_1\)，\(e_1\cdot e_2=e_2\)，故 \(e_1=e_2\)。
- 逆元唯一：假设 \(a\) 存在两个逆元 \(a'_1,a'_2\)，则 \(a'_1 a a'_2=a'_1\)，\(a'_1 a a'_2=a'_2\)，故 \(a'_1=a'_2\)。因此，我们也将 \(a\) 的逆元记作 \(a^{-1}\)。
- 消去律：\(a=b\iff a c=b c\iff ca=cb\)
必要性显然。考虑充分性：\(a c=b c\Rightarrow a c c'=b c c'\Rightarrow a=b\) - 对于任意的(有限)群 \(G=\{a_1,a_2...a_n\}\), \(\forall a\in G\)，都存在一个常数 \({\rm ord}(a)\),使得 \(a^{{\rm ord}(a)}=e\)。此时称 \({\rm ord}(a)\) 为 \(a\) 的阶。
构造集合 \(S=\{a,a^2,a^3,\cdots,a^{n+1}\}\)，则 \(S\) 中每一个元素都 \(\in G\)，故必有两个元素相同。假设 \(a^x=a^y (x<y)\)，则 \(a^{y-x}=e\)，此时 \(\mathrm{ord}(a)=y-x\)。
notes:
尽管群不一定有交换律，但我们总可以证明在任意结合律成立的代数结构中，若左右单位元都存在，必然相等；若左右逆元都存在，必然相等。
子群：
若对于 \(H\subseteq G\)，\((H,\cdot)\) 构成群，则称 \((H,\cdot)\) 为 \((G,\cdot)\) 的子群，简记为 为 \(H\leq G\)
性质：
- \(\forall a\in H\)，\(a^{-1}\in H\)
证明：由群的定义显然。 - \(e\in H\)
证明：由于 \(a,a^{-1}\in H\)，所以 \(e=aa^{-1}\in H\)
如果 \(G\) 为一个群，\(H\) 为其子群，且 \(g\in G\)，则：
\(gH=\{g\cdot h\mid h\in H\}\)，称其为 \(H\) 在 \(G\) 内的关于 \(g\) 的左陪集。
\(Hg=\{h\cdot g\mid h\in H\}\)，称其为 \(H\) 在 \(G\) 内的关于 \(g\) 的右陪集。
一些引理（左陪集同理）：
- \(\forall g\in G\)，\(|H|=|Hg|\)
证明：由于消去律，所以 \(\forall a\not=b,a g\not=b g\) - \(\forall g\in G\)，\(g\in Hg\)
因为 \(e\in H\)，所以 \(e g=g\in Hg\) - \(Hg=H\iff g\in H\)
先证 \(Hg=H \Leftarrow g\in H\)，由于封闭性，\(Hg\subseteq H\)，又由 \(|Hg|=|H|\) 得 \(Hg=H\)
再证 \(Hg=H \Rightarrow g\in H\)。由 2. 得 \(g\in Hg=H\)，故 \(g\in H\) - \(Ha=Hb\iff a b^{-1}\in H\)
证明：
\(Ha=Hb\iff (Ha)b^{-1}=(Hb)b^{-1} \iff H(a b^{-1})=H\iff a b^{-1}\in H\) - \(Ha\cap Hb\not=\varnothing \iff Ha=Hb\)
证明：从右到左显然。
考虑证明从左到右。
由于 \(Ha\cap Hb\not =\varnothing\)，所以 \(\exists h_1,h_2\in H\)，使得 \(h_1a=h_2b\)，所以 \(ab^{-1}=h_2h_1^{-1}\in H\)，所以 \(Ha=Hb\)。
可以推导出 \(H\) 的陪集要么交为空，要么相等。 - \(\bigcap\limits_{g\in G} Hg=G\)
显然由封闭性有 \(\bigcap\limits_{g\in G} Hg\subseteq G\)。
由于 \(e\in H\)，所以 \(G=\bigcap\limits_{g\in G} \{e\}g\subseteq \bigcap\limits_{g\in G} Hg\)
故 \(\bigcap\limits_{g\in G} Hg=G\)
定义：\(G/H=\{gH\mid g\in G\}\)，\([G:H]=|G/H|\)
拉格朗日定理： \(|G|=|H|\cdot[G:H]\)
证明：由 5. 6. 知 \(G/H\) 中任意两个集合无交且并为 \(G\)，则 \(|G|=\sum\limits_{S\in G/H} |S|\)，由于 \(G/H\) 中每个集合大小都为 \(|H|\)，所以 \(|G|=|H|\cdot [G:H]\)
置换与置换群
置换：
一个从 \(S\) 到自身的双射称为一个置换。
记作： \(\begin{pmatrix}a_1&a_2&a_3&...&a_n\\a_{p_1}&a_{p_2}&a_{p_3}&...&a_{p_n}\end{pmatrix}\)
有时我们会省略那个 \(a\)，只记录下标，表示为 \(\begin{pmatrix}1&2&3&...&n\\p_1&p_2&p_3&...&p_n\end{pmatrix}\)
置换乘法
相当于映射的叠加。
即 \(\begin{pmatrix}1&2&\cdots&n\\a_1&a_2&\cdots &a_n\end{pmatrix}\cdot \begin{pmatrix}a_1&a_2&\cdots &a_n\\b_1&b_2&\cdots &b_n\end{pmatrix}=\begin{pmatrix}1&2&\cdots &n\\b_1&b_2&\cdots &b_n\end{pmatrix}\)
感性理解：若将置换看作函数 \(f:\mathbb N\cap[1,n]\rightarrow \mathbb N\cap [1,n]\)，则置换乘法相当于构造函数 \(g(x)=f_2(f_1(x))\)
据此容易类比函数复合得知置换乘法满足结合律，不满足交换律。
易知单位元为 \(\begin{pmatrix}1&2&\cdots&n\\1&2&\cdots &n\end{pmatrix}\)
\(\begin{pmatrix}1&2&\cdots&n\\a_1&a_2&\cdots &a_n\end{pmatrix}\) 的逆元为 \(\begin{pmatrix}a_1&a_2&\cdots&a_n\\1&2&\cdots &n\end{pmatrix}\)
置换群
容易发现，由置换集合 \(G\) 和置换乘法 \(\cdot\) 构成的代数结构 \((G,\cdot)\) 是群。
对于置换群有如下事实 : 对于任意一个 \(n\) 阶有限群,存在一个 \(n\) 阶置换群与其同构。
同构：对两个同阶群 \(G_1,G_2\)，若有双射 \(\sigma:G_1\rightarrow G_2\)，使得 \(\forall a,b\in G_1,\sigma(a)\sigma(b)=\sigma(ab)\)，则称 \(G_1，G_2\) 同构。
所以我们只要构造双射 \(\sigma(a)\) 即可。相当于构造双射 \(f_a(x)\)，使得 \(f_b(f_a(x))=f_{ab}(x)\)。
考虑构造 \(f_a(x)=x\cdot a\)。对应置换
\(p_k=\begin{pmatrix}a_1&a_2&\cdots &a_n\\a_1a_k&a_2a_k&\cdots&a_na_k \end{pmatrix}\)
显然，\((\{p_k\},\cdot)\) 构成一个置换群。
循环置换
定义置换 \(\begin{pmatrix} a_1&a_2&\cdots&a_n \\a_2&a_3&\cdots &a_1\end{pmatrix}\) 为循环置换，可简记为 \((a_1,a_2,\cdots,a_n)\)
考虑置换 \(\begin{pmatrix}1&2&3&...&n\\p_1&p_2&p_3&...&p_n\end{pmatrix}\)，将 \(i\rightarrow p_i\) 连边，显然会形成很多个环，我们可以用若干个循环置换表示任意置换。
Burnside 引理和 Polya 定理
群作用
分为 左群作用 和 右群作用，这里定义左群作用。
对于一个集合 \(X\) 和群 \(G\)，则 \(G\) 在 \(X\) 上的左群作用为二元函数 \(\varphi:G\times X\rightarrow X\)，\((g,x)\mapsto g\times x\)，即以 \(g\times x\) 表示 \(\varphi(g,x)\)
\(e\times k=k\quad (e\textbf{ 是单位元})\)
\(g\times(h\times x)=(gh)\times x\)
此时称 \(X\) 为 \(G\)-集合, 并称 \(G\) 作用于 \(X\)。\(|X|\) 称为 \(G\)-集合 \(X\) 的度。
性质： \(g\times x=y\iff x=g^{-1}\times y\)
证明：只证左到右
\(x=e\times x=(g^{-1}g)\times x=g^{-1}y\)
notes：
1. 这里的 \(\times\) 是右结合的。
2.群作用和置换本质相同，唯一区别在于对于 \(G\) 中一个元素 \(g\)，不同 \(x\) 的 \(g\times x\) 可以相同，而置换显然不能（相当于普通映射和双射的区别）。因此本文不会区分这两者。
在证明轨道-稳定子定理时往往称为群作用（毕竟叫轨道和稳定子），但在 Burnside 引理和 Polya 定理中叫做置换，其实是一个东西。
3.注意区分 \(\cdot\) 和 \(\times\) 的不同含义。
轨道-稳定子定理
给出两套定义：
一：
-
轨道
考虑一个作用在 \(X\) 上的群 \(G\) 。 \(X\) 中的一个元素 \(x\) 的「轨道」是 \(x\) 通过 \(G\) 中的元素可以转移到的元素的集合。\(x\) 的轨道被记为 \(G(x)=\{g\times x\mid g\in G\}\)。 -
稳定子
定义稳定子为：\(G^x = \{g|g\in G,g\times x=x\}\)
二：
此处的群为置换群。
- 不动点
考虑置换 \(p\in G\)，若该置换存在循环置换 \((k)\)，则称 \(k\) 为 \(p\) 下不动点。\(p\) 不动点个数记为 \(c(p)\) - k 不动置换类（相当于稳定子）
若 \(p\) 中有不动点 \(k\)，则 \(p\) 属于 k 不动置换类，记作 \(p\in Z_k\)。 - 等价类（相当于轨道）
等价类 \(E_k\) 定义为对元素 \(k\) 施加任意的 \(G\) 中置换,能够获得的元素集合。
定理： 同一轨道内元素可以通过 \(G\) 相互到达。
证明：设 \(x,y\in G(t)\)，则 \(\exists g_1,g_2\in G\)，使得 \(g_1\times t=x\)，\(g_2\times t=y\)，那么 \(y=g_2 g_1^{-1} g_1 \times t=g_2g_1^{-1} \times x\)
记 \(g_2g_1^{-1}=g\)，则 \(y=g\times x,x=g^{-1}\times y\)
可以推出任意不同轨道不交。
定理：若 \(x,y\) 属于同一个轨道，那么 \(|G^x|=|G^y|\)
证明：由于 \(\exists g\in G,y=g\times x\)
因此我们可以构造双射 \(G^x\rightarrow G^y\)。
考虑 \(g_0\in G^x\)，\(g_0\times x=x\)
则 \(y=gg_0g^{-1}\times y\)，所以 \(g_0\rightarrow gg_0g^{-1}\)
这是一个双射。
故 \(|G^x|=|G^y|\)
在置换意义下的等价定理：若 \(x,y\) 属于同一个等价类，那么 \(|Z_ x|=|Z_ y|\)
轨道-稳定子定理
\(|G|=|E_ k|\cdot|Z_ k|\)（或者说 \(|G^x|\cdot |G(x)|=|G|\)）
引理 1：\(G^x\) 是 \(G\) 的子群。
证明：首先 \(e\in G^x\)，结合律显然。
封闭性：\(g\times x=x,h\times x=x,(gh)\times x=x\)
逆元：\(x=g\times x\iff x=g^{-1}\times x\)（见群作用的性质）
引理 2：\(G\) 中与 \(g\times x=h\times x\) 的解集是 \(gG^x\)
显然对于 \(gG^x\) 中的每一个元素都满足 \(h\times x=g\times x\)
假设还有 \(h\not\in gG^x\)。考虑到 \(h\times x=g\times x\iff x=h^{-1}g\times x\)，则 \(h^{-1}g\in G^x\)，故 \(h=hh^{-1}g\in hG^x\)，矛盾。
由引理 1 得拉格朗日定理 \(|G^x|[G:G^x]=|G|\)，只需证 \(|G(x)|=[G:G^x]\) 即可。
由引理 2 得 \(G^x\) 的任意陪集是一个极大的作用于 \(x\) 得到结果相同的集合，那么它对应于 \(G(x)\) 中的一个元素。而且陪集的并为 \(G\)，意味着 \(G/G^x\) 等价于将 \(G\) 中作用于 \(x\) 结果相同的元素分在一组，则作用效果的种类就是 \([G:G^x]\)，而 \(|G(x)|\) 显然等于效果种类数。
故 \(|G(x)|\cdot |G^x|=|G|\)，得证。
Burnside 引理
定义：设 \(A\) 和 \(B\) 为有限集合，\(X\) 为一些从 \(A\) 到 \(B\) 的映射组成的集合。
\(G\) 是 \(A\) 上的置换群，且 \(X\) 中的映射在 \(G\) 中的置换作用下封闭。
\(X/G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类的集合。
一个例子：
考虑一个长度为 \(n\) 的环，被染成黑白两色，所有旋转重合的方案视为一种。
那么
\(A\) 表示环上节点的集合。
\(B\) 表示颜色集合。
\(X\) 就是不考虑本质不同这一限制时染色方案的集合。
\(G\) 是各种翻转操作构成的置换群
其中 \(X^g=\{x\in X\mid g\times x=x\}\)
说人话：本质不同等价类个数=各个置换下不动点个数的和的平均数。
证明：由于轨道彼此不交且并为 \(X\)，所以我们将大小为 \(n\) 轨道内元素的贡献设为 \(\dfrac 1n\)，求贡献和即可。
\[\begin{aligned} |X/G|&=\sum_{x\in X} \frac{1}{|G(x)|} \\ &=\sum_{x\in X} \frac{|G^x|}{|G|} \quad \textbf{（轨道-稳定子定理）}\\ &=\frac{1}{|G|}\sum_{x\in X} |G^x| \\ &=\frac{1}{|G|}\sum_{g\in G} |X^g| \end{aligned}\]Polya 定理
其实用 Burnside 引理已经可以算答案了，但关键问题是不动点并不好算。
考虑让 \(X\) 为所有从 \(A\) 到 \(B\) 的映射（Burnside 引理允许只有部分映射）。
此时有：
其中 \(c(g)\) 表示置换 \(g\) 能拆分成的不相交的循环置换的数量。
可以发现 \(|X^g|\) 就是 \(|B|^{c(g)}\)。
原因：循环间彼此独立，循环内同色。
参考资料
command_block：群论小记
OI-Wiki
Soulist：题解 P4980 【【模板】Polya定理】