为了防止明天就把好不容易听完的东西都还给 rabbit_lb 了，还是记一点吧。

1. 群论基础

1.1 群(group) 的定义

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

封闭性：若 $a,b\in G$，则 $a\cdot b\in G$。
结合律：对于任意 $a,b,c\in G$，有 $(a\cdot b)\cdot c=a\cdot (b\cdot c)$。
单位元：存在单位元 $e\in G$，$\forall a\in G,\, a\cdot e=e\cdot a=a$。
逆元：对于任意 $a\in G$，存在 $b\in G$，使得 $a\cdot b=b\cdot a=e$。记为 $b=a^{-1}$。

1.2 一些概念

群元素个数有限则称为有限群，无限则称为无限群。
有限群 $G$ 的元素个数叫做群的阶，记做 $|G|$。
设 $G$ 和 $G$上的二元运算 $\cdot$ 构成一个群，$H$ 是 $G$ 的子集，且 $H$ 在原有运算下也是一个群，则 $H$ 为 $G$ 的一个子群。
若群 $G$ 的任意两元素均满足交换律，则称 $G$ 为交换群（Abel 群）。

1.3 群的性质

单位元唯一：$e_1e_2=e_1=e_2$
消去律：$ab=ac\Rightarrow b=c$
每个元的逆元唯一：反证，若 $aa^{-1}=a^{-1}a=e,\, ab^{-1}=a^{-1}b=e$，则 $aa^{-1}=ab^{-1}$，即 $a^{-1}=b$。
若 $G$ 有限，且 $a\in G$，则存在最小正整数 $r$，使得 $a^r=e$，且 $a^{-1}=a^{r-1}$。$r$ 称为 $a$ 的阶。

2. 置换群

2.1 置换

$[1,n]$ 到自身的一个映射称为 $n$ 阶置换，表示为 $\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix}$，其中 $a_1,a_2,\dots,a_n$ 是 $[1,n]$ 的一个排列。

$n$ 阶置换共有 $n!$ 个，同一个置换有 $n!$ 中表示方法，如 $p_1=\begin{pmatrix}1&2&3&4\\3&1&2&4\end{pmatrix}=\begin{pmatrix}3&1&4&2\\2&3&4&1\end{pmatrix}$。$n$ 阶置换也可以看作 $[1,n]$ 上的一元运算。

设 $P_1=\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix},\, P_2=\begin{pmatrix}1&2&\dots & n\\b_1&b_2&\dots&b_n\end{pmatrix}$，则定义置换乘法 $P_1P_2=\begin{pmatrix}1&2&\dots & n\\b_{a_1}&b_{a_2}&\dots&b_{a_n}\end{pmatrix}$。

置换乘法不满足交换律，但满足结合律。

2.2 置换群

$[1,n]$ 上由多个置换组成的集合，在 2.1 的乘法定义下构成的群，称为置换群。

封闭性：$\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix} \begin{pmatrix}a_1&a_2&\dots & a_n\\b_1&b_2&\dots&b_n\end{pmatrix}=\begin{pmatrix}1&2&\dots & n\\b_1&b_2&\dots&b_n\end{pmatrix}$
结合律：由 2.1 知置换乘法满足结合律。
单位元：$e=\begin{pmatrix}1&2&\dots & n\\1&2&\dots&n\end{pmatrix}$
逆元：$\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix}^{-1}=\begin{pmatrix}a_1&a_2&\dots & a_n\\1&2&\dots&n\end{pmatrix}$

$[1,n]$ 上的所有（$n!$ 个）置换构成的群，称为 $n$ 阶对称群，记作 $S_n$。平时所说的 $[1,n]$ 上的一个置换群，一定是 $S_n$的子群。

2.3 循环

2.3.1 置换的循环表示

置换 $\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix}$ 可以写作 $(1,a_1,a_{a_1},\dots)(\dots)$ 的形式，称为置换的循环表示。E.g. $\begin{pmatrix}1&2&3 & 4&5\\3&1&2&5&4\end{pmatrix}=(132)(45)$，$\begin{pmatrix}1&2&3 & 4&5\\5&2&3&1&4\end{pmatrix}=(154)(2)(3)$。

$(a_1a_2\dots a_m)$ 称为 $m$ 阶循环，有 $m$ 种表示方法。

通常情况下，我们可以忽略所有阶为 $1$ 的循环。两个不相交的循环之间满足交换律。

定理：任意置换可表示成若干不相交循环的积。

证明：考虑令置换 $i$ 向 $a_i$ 连边，图由若干个环构成。显然每个环都可以表示成一个循环。

2.3.2 共轭类

我们设置换 $p$ 的循环表示为 $p=(a_1a_2\dots a_{k_1})(b_1,b_2\dots b_{k_2})\dots (h_1h_2\dots h_{k_n})，其中 $$\sum\limits_{i=1}^n k_i=n$。设 $k$ 阶循环出现的次数为 $c_k$。
那么置换 $p$ 的格式为 $(1)^{c_1}(2)^{c_2}\dots(n)^{c_n}$。E.g. $(1)(23)(4567)$ 的格式为 $(1)^1(2)^1(4)^1$。

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

定理：$S_n$ 中 $(1)^{c_1}(2)^{c_2}\dots(n)^{c_n}$ 所在的共轭类元素个数为 $\dfrac{n!}{(c_1!c_2!\dotsc_n!)(1^{c_1}2^{c_2}\dots n^{c_n})}$。

可以这样理解这个式子：

一个长度为 $i$ 的循环共有 $i$ 种表示，$c_i$ 个长度为 $i$ 的循环有 $i^{c_i}$ 种表示；
对互不相交的 $c_i$ 个循环枚举全排列，共有 $c_i!$ 种表示。

2.3.3 对换与奇偶置换

$2$ 阶循环叫做对换。

定理：任意循环都可以表示为若干对换的积。

推柿子：

\[\begin{aligned} &(1\, 2\, 3\dots n-1)(1\, n)\\ =&\begin{pmatrix}1&2&\dots & n-1\\2&3&\dots&1\end{pmatrix}\begin{pmatrix}1&2&\dots & n-1&n\\n&2&\dots&n-1&1\end{pmatrix}\\ =&\begin{pmatrix}1&2&\dots & n-1&n\\2&3&\dots&n&1\end{pmatrix}\\ =&(1\,2\,\dots\,n) \end{aligned} \]

那么进一步地，有分解 $(1 2\dots n)=(12)(13)\dots(1n)$。注意每个置换的分解不唯一。

若一个置换能分解为奇数个对换之积，则为奇置换；否则为偶置换。

Warning. 置换相乘的奇偶性类似于自然数加法，而非自然数乘法：奇 x 奇 = 偶，奇 x 偶 = 奇。