OI数学总结-群论

施工中，咕咕咕….

群的基本概念

群的定义

群公理包含下述四个性质（有时略去封闭性，只有三个性质）。若集合 $G\neq\varnothing$ 和 $G$ 上的运算 $\cdot$ 构成的代数结构 $(G,\cdot)$ 满足以下性质：

1. 封闭性：对于所有 $G$ 中 $a, b$ ，运算 $a·b$ 的结果也在 $G$ 中。
2. 结合律：对于 $G$ 中所有的 $a, b, c$ ，等式 $(a \cdot b)\cdot c = a \cdot (b \cdot c)$ 成立。
3. 标识元（单位元）： $G$ 中存在一个元素 $e$ ，使得对于 $G$ 中的每一个 $a$ ，都有一个 $e \cdot a=a\cdot e=a$ 成立。这样的元素是独一无二的。它被称为群的标识元素。
4. 逆元：对于每个 $G$ 中的 $a$ ，总存在 $G$ 中的一个元素 $b$ 使 $a \cdot b = b \cdot a = e$ ，此处 $e$ 为单位元，称 $b$ 为 $a$ 的逆元，记为 $a^{-1}$ 。

则称 $(G,\cdot)$ 为一个 群。

例如，整数集和整数间的加法 $(\mathbb{Z},+)$ 构成一个群，单位元是 $0$，一个整数的逆元是它的相反数。

阶的定义

• 一个群的阶是指其势，即其元素的个数；

• 一个群内的一个元素 $a$ 的阶（有时称为周期）

  是指会使得 $a^m = e$ 的最小正整数 $m$ （其中的e为这个群的单位元素，且$a^m$为 $a$ 的 $m$ 次幂）

  若没有此数存在，则称 $a$ 有无限阶。有限群的所有元素都有有限阶。

群的主要类别

置换群

对于给定的集合 $X$ ，$X$ 到自身的一些置换集合 $G$ 如果在复合运算和求逆运算下封闭，那么称 $G$ 是一个作用于 $X$ 上的群。

易证，集合 $S$ 上的所有置换关于置换的乘法满足封闭性、结合律、有单位元（恒等置换，即每个元素映射成它自己）、有逆元（交换置换表示中的上下两行），因此构成一个群。这个群的任意一个 子群 即称为 置换群。

置换的定义

有限集合到自身的双射成为置换。集合 $S = \{a_1,a_2,\cdots ,a_n\}$ 上的置换可以表示为

$$f = \begin{pmatrix} a_1,a_2,\cdots,a_n\\ a_{p_1},a_{p_2},\cdots,a_{p_n} \end{pmatrix}$$

意为将 $a_i$ 映射为 $a_{p_i}$ ，其中 $p_1,p_2,\cdots,p_n$ 是 $1,2,\cdots,n$ 的一个排列

显然 $S$ 上所有置换的数量为 $n!$

置换的乘法

对于两个置换 $f= \begin{pmatrix}a_1,a_2,\cdots,a_n\\a_{p_1},a_{p_2},\cdots,a_{p_n}\end{pmatrix}$和 $g= \begin{pmatrix}a_{p_1},a_{p_2},\cdots,a_{p_n}\\a_{q_1},a_{q_2},\cdots,a_{q_n}\end{pmatrix}$ ，$f$ 和 $g$ 的乘积记为 $f \circ g$ ，其值为

$$f \circ g= \begin{pmatrix}a_1,a_2,\cdots,a_n\\a_{q_1},a_{q_2},\cdots,a_{q_n}\end{pmatrix}$$

简单来说就是先后经过 $f$ 的映射，再经过 $g$ 的映射。

循环置换

循环置换是一类特殊的置换，可表示为

$$(a_1,a_2,\cdots,a_m) =\begin{pmatrix}a_1,a_2,\cdots,a_{m-1},a_m\\a_{2},a_{3},\cdots,a_{m},a_1\end{pmatrix}$$

若两个循环置换不含有相同的元素，则称它们是不相交的，有如下定理：

任意一个置换都可以分解为若干不相交的循环置换的乘积，例如

$$\begin{pmatrix}a_1,a_2,a_3,a_4,a_5\\a_3,a_1,a_2,a_5,a_4\end{pmatrix} = (a_1,a_3,a_2) \circ (a_4,a_5)$$

该定理的证明非常简单。如果把元素视为图的结点，映射关系视为有向边，则每个结点的入度和出度都为 $1$ ，因此形成的图形必定是若干个环的集合，而一个环即可用一个循环置换表示。

循环群

循环群是最简单的群

群 $G$ 中任意一个元素 $a$ 都可以表示为 $a=g^k$ ，其 $k$ 为整数。称 $g$ 为群 $G$ 的生成元。

有定理：生成元 $g$ 的阶就是群 $G$ 的阶。

阶为 $m$ 的有限循环群 $G$ 同构于模 $m$ 剩余类对于加法构成的群 $Z_m$。

Burnside 引理

设 $A,B$ 为有限集合，$X$ 为一些从 $A$ 到 $B$ 的映射组成的集合。

$G$ 是 $A$ 上的置换群，且 $X$ 中的映射在 $G$ 中的置换作用下封闭。

$X/G$ 表示 $G$ 作用在 $X$ 产生的所有等价类的集合

（若 $X$ 中的两个映射经过 $G$ 中的置换作用后相等，则它们在同一个等价类中），则

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

其中 $|S|$ 表示集合 $S$ 的基数，即元素个数，且

$$X^g = \{x|x\in X,g(x) =x\}$$

举例：

用 $3$ 种颜色给一个立方体染色，求本质不同的方案数

本质不同指：经过任意翻转后，两种染色方案均不同

则根据上面的模板，有

• $A$ ：立方体 $6$ 个面的集合
• $B$ ： $3$ 种颜色的集合
• $X$ ：直接给每个面染色，不考虑本质不同的方案的集合，共有 $3^6$ 种
• $G$ ：各种翻转操作构成的置换群
• $X/G$ ：本质不同的染色方案的集合
• $X^g$ ：对于某一种反转操作 $g$ ，所有直接染色方案中，经过 $g$ 这种翻转后保持不变的染色方案的集合

下面懒得写了，直接看图片吧。