群论

群的定义

定义：给定集合 $G$ 和集合 $G$ 上的二元运算 $\cdot$，满足以下条件称为群：

1、封闭性（Closure）：若 $a,b\in G$，则 $\exists c\in G$，使得 $a\cdot b=c$。

2、结合律（Associativity）：对 $\forall a,b,c\in G$，有 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$。由于结合律成立，可记作 $a\cdot b\cdot c$。

3、有单位元（Identity）：$\exists e\in G$，满足对 $\forall a\in G$，有 $a\cdot e=e\cdot a=a$。

4、有逆元（Inverse）：$\forall a\in G$，满足 $\exists b\in G$，使得 $a\cdot b=b\cdot a=e$，记作 $b=a^{-1}$。

一些概念

群元素的个数是有限的，是有限群；群元素的个数是无限的，是无限群。

有限群 $G$ 的元素个数叫做群的阶，记做 $|G|$。

设 $G$ 是群，$G'$ 是 $G$ 的子集，若在 $G'$ 原有的运算之下也是一个群，则称为 $G$ 的一个子群。

若群 $G$ 的任意两元素 $a,b$ 恒满足 $a\cdot b=b\cdot a$。则称 $G$ 为交换群，又称 Abel 群。

一些性质

单位元唯一：$e_1e_2=e_2=e_1$

左右逆元相等：$ab=e,ca=e\rightarrow b=c$
证明：$cab=(ca)b=eb=b, cab=c(ab)=ce=c \Rightarrow b=c$

消去律成立：$ab=ac\rightarrow b=c$
证明：$ab=ac \Rightarrow a^{-1}ab=a^{-1}ac\Rightarrow b=c$

每个元的逆元唯一：$ab=ba=e,ac=ca=e \rightarrow b=c$
证明：$e=ab=ac\Rightarrow b=c$

多个数乘积的逆元：$(ab\cdots c)^{-1}=c^{-1}\cdots b^{-1}a^{-1}$
证明：$(c^{-1}\cdots b^{-1}a^{-1})(ab\cdots c)=c^{-1}\cdots b^{-1}(a^{-1}a)b\cdots c=\cdots=e$

对于有限群，逆元存在于消去律存在等价。
证明：上面已经证明逆元存在则消去律存在，接下来证明消去律存在则逆元存在。
$ab=ac\rightarrow b=c$，则令 $G'={ax|x\in G}$，根据消去律 $ax$ 两两不同，则 $|G|=|G'|$，而根据封闭性，$G'\subseteq G$，（对有限群）故 $G=G'$，则必然存在 $e\in G'$，即 $\exists x\in G,ax=e$。

对于有限群，若 $a\in G$，则存在最小正整数 $r$，使得 $a^r=e$，且 $a^{-1}=a^{r-1}$。
证明：设 $g=|G|$，则 $a,a^2,\cdots,a^g,a^{g+1}\in G$ 中必有相同项（鸽巢原理）。
设 $a^j=a^k(1\leq j\lt k\leq g+1)$，则 $e=a^{k-j}$（消去律）。令 $r=k-j$，则 $a^r=a^{r-1}a=e$，即 $a^{-1}=a^{r-1}$。
既然存在正整数 $r$ 使得 $a^r=e$，其中必有最小者，不妨仍设为 $r$。
$r$ 称为 $a$ 的阶（和群的阶不同，这是一个元的阶），容易证明 $H={a,a^2,\cdots,a^r=e}$ 在原有运算意义下也是一个群。

置换群

置换

置换：$[1,n]$ 到自身的一一映射称为 $n$ 阶置换，共有 $n!$ 个。$S_n$ 为所有 $n$ 阶置换组成的置换群。

置换群的运算：双射的复合（不满足交换律）。

循环

循环：$p=(a_1,a_2,\cdots,a_n)$ 称为 $n$ 阶循环，$a_1\rightarrow a_2\rightarrow a_3,\cdots\rightarrow a_n\rightarrow a_1$。$p^n=(1)(2)\cdots (n)=e$。

若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。任一置换可表示成若干不相交循环的乘积。

共轭类

$P=(a_1a_2\cdots a_{k_1})(b_1b_2\cdots b_{k_2})\cdots(h_1h_2\cdots h_{k_l})$，其中 $a,b,\cdots,h$ 都是不相交循环，$k_1+k_2\cdots k_l=n$。设 $k_i=j$ 的出现次数为 $c_j$，用 $(j)^{c_j}$ 表示，$\sum_{j=1}^n j c_j=n$ 则它的格式为 $(1)^{c_1}(2)^{c_2}\cdots (n)^{c_n}$。

共轭类：$S_n$ 中所有相同格式的置换全体构成一个共轭类。

对换

任意循环都可以表示为对换的积：$(1\ 2\cdots n)=(1\ 2)(1\ 3)\cdots (1\ n)$。

每个置换的分解方式不是唯一的，但是表示成对换的个数的奇偶性是唯一的。

陪集

陪集：对于 $G$ 的一个子群 $G'$，它关于 $a\in G$ 的右陪集为 $G'_a={x\cdot a|x\in G'}$，左陪集为 $_aG'={a\cdot x|x\in G'}$。
根据消去律，陪集的元素两两不同，故 $G'$ 每一个陪集的大小都和 $G$ 相等。

方便起见，以下均以右陪集为例，左陪集同理。
一个性质：对于 $a,b\in G$，若 $G'_a \cap G'_b\neq \varnothing$，则 $G'_a=G'_b$。
证明：因为 $G'_a \cap G'_b\neq \varnothing$，所以 $\exists x,y\in G',x\cdot a=y\cdot b$，$y^{-1}\cdot x\cdot a=b$。
对 $\forall z\in G'_b$，设 $z=tb(t\in G')$，则 $z=tb=t\cdot y^{-1}\cdot x\cdot a=(t\cdot y^{-1}\cdot x)\cdot a$，而 $t\cdot y^{-1}\cdot x\in G'$，故 $z\in G'_a$，即 $G'_b\subseteq G'_a$。同理可以证明 $G'_a\subseteq G'_b$，故 $G'_a=G'_b$。

拉格朗日定理

拉格朗日定理（Lagrange's theorem）：对任意 $G$ 的一个子群 $G'$，$|G'||G':G|=|G|$（$|G':G|$ 表示 $G'$ 在 $G$ 中的陪集个数）。
证明：上面说明了 $G'$ 的陪集的大小都是 $|G'|$，而且任意两个相等或不交。
又因为 $e\in G'\Rightarrow x\in G'_x \Rightarrow \bigcup _{x\in G} G'_x=G$，所以共有 $|G':G|=\frac{|G|}{|G'|}$ 个不同的陪集。
这个定理说明了一个群的子群大小是整除该群大小的。

不动点、轨道和稳定化子

很多概念在中文翻译的描述上有差异，我们主要用不动点/轨道/稳定化子来描述。

设群 $G$ 作用在集合 $X$ 上。对于 $X$ 中的一个元素 $x$，每个 $G$ 中元素 $g$ 都把 $x$ 映射到某个 $g(x)\in X$ 上。

注意，$g(x)$ 表示将 $g$ 作用在 $x$ 上得到的结果。

不动点（fixed point）：对于 $X$ 中的一个元素 $x$，如果 $x\in X$ 在任意 $g\in G$ 的作用下都不变，即 $g(x)=x$，那么称 $x$ 为该群作用的一个不动点。不动点集 $X^g={x\in X\mid g(x)=x, \forall g\in G}$。

轨道（orbit）：对于 $X$ 中的一个元素 $x$，所有能被映射到的元素 $g(x)$ 构成了 $X$ 的一个子集，称为元素 $x$ 的轨道。$\mathrm{orbit}(x)={g(x)\mid g\in G}$。轨道集合 $X/G$ 为所有不同轨道的集合。
（另外的一种描述，等价类。）

稳定化子（stablizer）：对于 $X$ 中的一个元素 $x$，所有满足 $g(x)=x$ 的 $g$ 构成了 $G$ 的一个子群，称为元素 $x$ 的稳定化子。$\mathrm{stab}(x)={g\in G\mid g(x)=x}$。
（另外的一种描述，$k$ 不动置换类：设 $G$ 是 $S_n$ 的一个子群。对于 $k\in [1,n]$，$G$ 中使得 $k$ 元素保持不变的置换全体，称为 $k$ 不动置换类，记作 $Z_k$。）

轨道-稳定化子定理

轨道-稳定化子定理（Orbit-stabilizer theorem）：对 $\forall x\in X$，有 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。
证明：首先我们有对于 $\forall x\in X$，满足 $\forall g,h\in G,g(x)=h(x) \Longleftrightarrow g$ 和 $h$ 在稳定化子的同一个左陪集上，证明如下 $g(x)=h(x)\Leftrightarrow (g^{-1}\cdot h)(x)=x\Leftrightarrow g^{-1}\cdot h\in \mathrm{orbit}(x)\Leftrightarrow h\in \ _g\mathrm{orbit}(x)$。
故轨道数量 $|\mathrm{orbit}(x)|$ 就是稳定化子的陪集数量 $|\mathrm{stab(x)}:G|$，根据拉格朗日定理，可以得到 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。

Burnside 引理

伯恩赛德引理（Burnside's lemma）：$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$。轨道数（等价类）数量为所有置换下不动点数量的平均值。
证明：$|X/G|=\sum_{x\in X}\frac{1}{|\mathrm{orbit}(x)|}=\frac{\sum_{x\in X} |\mathrm{stab}(x)|}{|G|}=\frac{\sum_{g\in G} |X^g|}{|G|}$。
解释：第一个等号是，每个 $x$ 出现在大小为 $|\mathrm{orbit}(x)|$ 的轨道，而每个轨道应该被计算恰好一次，相当于其中每个元素贡献 $\frac{1}{|\mathrm{orbit}(x)|}$；第二个等号是轨道-稳定化子定理；第三个等号是两个分子都等于 $x\in X,g\in G,g(x)=x$ 的数量。

Pólya 定理

波利亚计数定理（Pólya enumeration theorem）：对于 $n$ 阶置换群 $G$，用 $t$ 种颜色给 $n$ 个位置着色的不同方案数为 $|X/G|=\frac{1}{|G|}\sum_{g\in G}t^{c(g)}$，其中 $c(g)$ 表示置换 $g$ 拆出的不相交循环个数。
证明：只需证明 $|X^g|=t^{c(g)}$。$X^g$ 中的元素在 $g$ 作用下不变，等价于同一个循环上的颜色都相同，而不同循环间独立，故 $|X^g|=t^{c(g)}$。