OI数学总结-群论

施工中，咕咕咕....

群的基本概念

群的定义

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

封闭性：对于所有 \(G\) 中 \(a, b\) ，运算 \(a·b\) 的结果也在 \(G\) 中。
结合律：对于 \(G\) 中所有的 \(a, b, c\) ，等式 \((a \cdot b)\cdot c = a \cdot (b \cdot c)\) 成立。
标识元（单位元）： \(G\) 中存在一个元素 \(e\) ，使得对于 \(G\) 中的每一个 \(a\) ，都有一个 \(e \cdot a=a\cdot e=a\) 成立。这样的元素是独一无二的。它被称为群的标识元素。
逆元：对于每个 \(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\) 种颜色给一个立方体染色，求本质不同的方案数

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