群论小记

· · 算法·理论

或许更好的浏览体验

1.群

1.1.群的定义

定义集合 G 的作用于集合 G 的运算符 \times，若满足一下己个性质则称之为一个群（{\text{Group}}），记为 (G,\times)：

1.封闭性

若满足 a,b \in G，则有 a\times b \in G。

2.结合律

若满足对于任意的 a,b,c 都有 a \times (b \times c) = (a \times b) \times c。

3.单位元

对于所有的 a \in G，都有 e \times a = a \times e = a。

4.逆元

对于所有的 a \in G，都有 a^{-1} \times a = 1。

1.2.群的简单性质

1.3.子群和其衍生

1.3.1.定义

子群： 对于一个群 G(S,\times)，若有 T \subseteq S，并且 H(T,\times) 也是一个群，那么我们称之为 H 是 G 的子群，记作 H \le G。

生成子群： 对于 S 的一个子集 T，我们求出所有的 G 的所有使 T \subseteq T^` 的子群 (T^`,\times) 的交 G^`，我们称 G^` 为 T 的生成子群，同时 T 也是 G^` 的生成集合，记作 \langle T\rangle，当 T = \{x\} 时，也记作 \langle x\rangle。

循环群：可由一个元素生成的群。

陪集：对于一个群 G 的子群 H。

注意陪集不一定是一个群，因为陪集显然可能没有单位元。

1.3.2.陪集的性质

这是一些有关于陪集的性质，这里只讨论右陪集。

1.3.3.拉格朗日定理

若 H \le G，那么有：

|G| = |H| \times [G : H]

其中 [G : H] 表示 G 中 H 不同的陪集个数。

2.置换群

2.1.置换的定义

集合到自己的映射，也就是双射，我们称之为置换。比如不可重集合 S = \{a_1,a_2,a_3,a_4 ,\cdots \cdots,a_n\} 上的置换为：

f=\left(\begin{array}{c}{a_1, a_2, \cdots\cdots, a_n} \\{a_{p_1}, a_{p_2}, \cdots\cdots, a_{p_n}}\end{array}\right)

表示把 a_i 映射到 a_{p_i}，及 f(a_i) = a_{p_i}，其中 p 为一个 1 \sim n 的一个排列。由于我们没有规定 a_1,a_2 \cdots \cdots a_n 的排列顺序，所以 S 上的置换的个数就是 n!。

2.2.置换的乘法

假如有两个置换 f=\left(\begin{array}{c}{a_1, a_2, \cdots\cdots, a_n} \\{a_{p_1}, a_{p_2}, \cdots\cdots, a_{p_n}}\end{array}\right) 和 g=\left(\begin{array}{c}{a_1, a_2, \cdots\cdots, a_n} \\{a_{q_1}, a_{q_2}, \cdots\cdots, a_{q_n}}\end{array}\right)，那么他们连个置换的乘积就表示为：

f \circ g = \left(\begin{array}{c}{a_1, a_2, \cdots\cdots, a_n} \\{a_{p_{q_1}}, a_{p_{q_2}}, \cdots\cdots, a_{p_{q_n}}}\end{array}\right)

及 (f \circ g)(x) = f(g(x)) 其实就是先通过 g 的置换，再通通过 f 的置换。

2.3.置换群

集合 S 上所有的置换的乘法明显满足组成一个群的要求。

通常我们把在 \{1,2,3,\cdots \cdots ,n\} 上的所有置换构成的群称为 n 元对称群，记为 S_n。

这个群的任意一个子群即称为置换群。

2.4.循环置换

循环置换是一种特殊的置换，可以表示为：

{a_{1}, a_{2}, \cdots\cdots, a_{m-1}, a_{m}} \\{a_{2}, a_{3}, \cdots\cdots, a_{m}, a_{1}} \end{array}\right)

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

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

3.轨道-稳定子定理

定义 A,B 是两个有限集合，X = B^A 表示从 A 到 B 的所有映射，G 是作用在 A 上的一个置换群。

我们定义，对于每一个 x \in X：

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

并且

G(x) = {g(x)|g \in G}

其中我们称 G^x 为 x 的稳定子，G(x) 为 x 的轨道。

那么就有：|G| = |G^x| \cdot |G(x)|。

4.Burnside 引理和 Pólya 定理

4.1.Burnside 引理

4.1.1.内容

定义 A,B 是两个有限集合，X=B^A 表示所有从 A 到 B 的映射，G 是作用在 A 上的一个置换群（跟上面一样）。

$X/G$ 其实就是，对于所有的 $x \in X$，不同轨道的集合，这些轨道必定是不交的。因此我们也将 $|X/G|$ 叫做 $X$ 关于 $G$ 的轨道数。同时我们定义 $X^g = \{x|g(x) = x,x \in X\}$。我们称 $X^g$ 是 $X$ 在置换 $g$ 下的不动点集合。 那么 Burnside 引理就是 $|X/G| = \frac{1}{|G|} \sum_{g \in G} |X^g|$。 ### 4.2.Pólya 定理 是 Burnside 引理的一种特殊形式，前置条件也与 Burnside 引理相同。 我们定义 $c(g)$ 表示置换 $g$ 拆出的不相交轮换数量。 这个定理的内容为： $$|X/G|=\frac{1}{|G|}\sum_{g\in G} |B|^{c(g)}$$ **注意：这个定理的满足条件为 $X=B^A$，否则次定义不一定成立。** ## 5.举例 **注意：以下为纯数学部分。** ### 5.1.例题一 > 长度为 $6$ 的透明的方格，用红蓝黄绿 $4$ 种进行染色。请问有多少种不同的方案。 我们考虑使用 Pólya 定理来解决。我们发现题目就相当于用 $4$ 种字符填充 $6$ 个空位，那么我们将两个字符串看成相同的当且仅当本身一样或者其中一个翻转后一样。 那么，群 $G: P_2 = \left(\begin{array}{c}{1,2,3,4,5,6} \\{6,5,4,3,2,1}\end{array}\right) = (1 6)(2 5)(3 4)

那么不同方案的数量就是 \dfrac{1}{2}(4^6 + 4^3)。

5.2.例题二

用 6 种颜色给立方体染色，每一个面所然对的颜色都不一样，请问有多少种方案。

我们发现如果不算旋转的话那么应该有 6! 方案。那么我们定义 6! 种染色方案分别为 S_1,S_2,S_3,\cdots \cdots,S_{6!}。那么在单位元素的作用下有置换 (S_1),(S_2),\cdots \cdots (S_{6!})。

由于 6 个面的颜色均不相同，那么对于其余的 23 种置换不能保持不变。设在 24 个置换中 p_0 为单位元素，即不动置换，其余为 p_1,p_2,p_3 \cdots \cdots,p_23。因此：

c_1(p_1) =c_1(p_2) = \cdots \cdots = c_1(p_23) = 0

根据 Burnside 引理，那么不同的方案数为 \frac{1}{24} \times 6! = 30。