抽象代数

· · 算法·理论

群

概念

对于非空集合 G，\cdot 为集合内元素的二元运算。如果满足：

  1. 封闭性。对于 \forall a,b\in G，满足 a\cdot b\in G。
  2. 结合律。对于 \forall a,b,c\in G，满足 (a\cdot b)\cdot c=a\cdot(b\cdot c)。
  3. 单位元。\exists e\in G，\forall a\in G，满足 a\cdot e=e\cdot a=a。
  4. 逆元。\forall a\in G，\exists b\in G，满足 a\cdot b=b\cdot a=e。

则称 (G,\cdot) 为群。只满足 1,2 称为半群，满足 1,2,3 称为幺半群。

交换群：满足交换律的群。

有限群：元素有限的群，|G| 为群的阶。

对于一张正 n 边形纸片，考虑所有对称变换

不难发现所有的变换即 r^k 和 r^ks(0\le k<n)，构成 2n 阶群，记作 D_{2n}。

对于 a\in G，定义 a 的阶为使 a^k=e 的最小正整数 k，记作 o(a)=|a|=k。

有限群元素必有阶，无限群未必，如 (\Z,+)。

若 |a|=n，则

其他性质

  1. |a|\mid |G|。
  2. ## 子群 设有群 $(G,\cdot)$，若 $H\subseteq G$ 且 $(H,\cdot)$ 构成群，称 $H$ 为 $G$ 的子群，记作 $H\le G$。

子群和子群的交集一定是子群，但并集不一定。

判定定理

当且仅当 \forall g,h\in H 有 g^{-1}h\in H，则 H\le G。

陪集

设群 G 及其子群 H，g\in G，则集合 gH=\{gh|h\in H\} 称为子群 H 包含 g 的左陪集，右陪集同理。陪集不一定构成群。

拉格朗日定理

|G|=[G:H]|H| 推论：子群的阶是群的阶的约数。 ## 循环群 循环群 $C_n$：由一个元素 $a$ 反复自乘获得 $G$ 中所有元素。 称 $a$ 为生成元，由这种方式生成的群称为 $\left \langle a \right \rangle $，读作 $a$ 的生成子群。循环群必是交换群。 --- 若 $a$ 为 $C_n$ 的一个生成元，则所有的生成元为 $$ \{a^k|1\le k<n,\gcd(k,n)=1\} $$ 数量为 $\varphi(n)$ 个。可以将它视作为原根。 ### 群同构 若群 $(G1,\cdot)$ 和 $(G_2,\times)$ 之间存在双射 $f:G_1\to G_2$，$\forall a,b\in G_1$ 满足 $f(a\cdot b)=f(a)\times f(b)$，称 $G_1,G_2$ 同构，记作 $G_1\cong G_2$。 $(\Z_p^*,\times)\cong (\Z_{p-1},+)\cong C_{p-1}$。只需构造双射 $f(g^a)=a$，$g$ 是 $p$ 的一个原根。 ### 群同态 把双射改成映射。 ## 置换群 置换：有限集合的一一变换，可用排列表示 $p_1p_2p_3\dots p_n$。 即 $a_{1},a_{2},\dots,a_{n}$ 变为 $a_{p_1},a_{p_2},\dots,a_{p_n}$。 - 置换是映射且是双射，可复合 $\circ $。 - 置换可以分解为若干轮换（环）或对换的复合。 --- 置换群：若干 $n$ 阶置换构成的集合 $G$ 与复合 $\circ$ 运算。 全体 $n$ 阶置换构成的群成为循环群，用 $S_n$ 表示，$|S_n|=n!$。$\left\langle r,s\right\rangle=D_3\cong S_3$。 凯莱定理：任意群 $G$ 同构某个置换群。 ## 群作用 若映射（二元函数） $\alpha:G\times X\to X$， 满足（$g,h\in G$，$x\in X$，$\alpha(g,x)=g\cdot x=g(x)$） - $(gh)\cdot x=g\cdot (h\cdot x)$。 - $e\cdot x=x$。 则映射 $\alpha$ 为 $G$ 在 $X$ 上的群作用。 ### 轨道 设 $G$ 作用在 $X$ 上，定义集合 $$ O_x=\{g(x),g\in G\}) $$ 为群作用下的一个轨道，所有轨道构成 $X$ 的划分。同一轨道上的元素属于同一个等价类。 ### 稳定子 若 $g(x)=x$，称 $x$ 为 $g$ 的一个不动点。 $$ G_x=\{g,g(x)=x\} $$ 称为 $x$ 的稳定子群。 ### 轨道 $\cdot$ 稳定子定理 $|G|=|O_x||G_x|$。 # Burnside 引理 轨道个数 $$ |X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g| $$ $X^g$ 表示 $g$ 作用下的不动点集合。 考虑证明： $$ \begin{aligned} \sum_{g\in G}|X^g|&=\sum_{x\in X}|G_x|\\ &=\sum_{x\in X}\frac{|G|}{|O_x|}\\ &=|G|\sum_{O\in X/G}\sum_{x\in O}\frac{1}{|O|}\\ &=|G|\sum_{O\in X/G}1\\ &=|G||X/G| \end{aligned} $$ --- 考虑在染色模型下 Burnside 的本质。 对于一个置换群，$|X/G|$ 即求所有本质不同的染色方案，使得两种方案不会在经过若干次置换后相同。 而 $|X^g|$ 即代表有多少种染色方案在经过置换 $g$ 之后与原方案相同。 ## Pólya 定理 设 $G$ 作用在 $X$ 上，在染色模型下，假设颜色集合为 $C$，则本质不同的染色方案个数为 $$ |C^X/G|=\sum_{g\in G}|C|^{c(g)} $$ $c(g)$ 表示 $g$ 分解的轮换数量。 --- 再关注其本质。 对于置换 $g$，把 $(i,p_i)$ 看做一条边，考虑将它分解成若干个环，如 $3412$ 可以分解为 $(13)(24)$，这即为轮换分解，环的个数即为轮换数量。 对于置换 $g$，称它的型为 $(x_1)^{r_1}(x_2)^{r_2}\cdots$，表示共有 $r_i$ 个长度为 $x_i$ 的轮换，在部分限定颜色数量的题目中需要用到轮换的长度。 然后考虑 $|C|^{c(g)}$ 的意义。要求经过置换 $g$ 本质不变，那么对于每个环的染色必须相同，共有 $c(g)$ 个环，每个环有 $|C|$ 种染色方案，即为上式。 ## 模型一：空间几何体 给定一个正方体，用 $n$ 种颜色对它的边/棱/角染色，求本质不同的方案数。 先确定置换群，以棱为例。 对 $12$ 条棱标号，对于所有旋转置换求出对应后的标号，然后进行轮换分解，求出答案。可以这样考虑 - 恒等置换，$1$ 种，型为 $(1)^{12}$。 - 面面中心旋转 $90^{\circ}$，$3\times 2=6$ 种，型为 $(4)^3$。 - 面面中心旋转 $180^{\circ}$，$3$ 种，型为 $(2)^6$。 - 相对棱中心旋转 $180^{\circ}$，$6$ 种，型为 $(1)^2(2)^5$。 - 对角旋转 $120^{\circ}$，$4\times 2=8$ 种，型为 $(3)^4$。 令 $L$ 表示向左旋转 $90^{\circ}$，$F$ 表示向前旋转 $90^{\circ}$，则所有旋转变换可以表示为 $L^aF^b$，分别写转换函数可以方便求出所有置换。 --- [UVA10601 Cubes](https://www.luogu.com.cn/problem/UVA10601)。 限制了每种颜色的个数。 一种方法是 [[HNOI 2008] Cards](https://www.luogu.com.cn/problem/P1446) 的思路，写一个 $O(n^6)$ 背包 dp，看一个环选择哪种颜色。 另一种是注意到五种变换中只有第四种变换是存在长度不同的环的，而对于长度为 $l$ 相同的环，可以视作有 $\frac{12}{l}$ 个球；然后对于颜色 $c$，假如个数为 $k$，那么可以视作所有球中有 $\frac{k}{l}$ 个颜色为 $c$ 的球，如果 $l$ 不整除 $k$ 显然方案数是为 $0$ 的。 然后问题就变成有 $6$ 种颜色的球求排列数，转换成可重集的排列数。而对于第四种变换，显然可以枚举两个长度为 $1$ 的环怎么染色，然后同理即可。 ## 模型二：环染色 如果旋转翻转同构，那么即为 $D_{2n}$。 考察旋转操作。 - 设 $g_k$ 为顺时针旋转 $k$ 个点的置换，对于单个点，其周期 $T$ 满足 $kT\equiv 0\pmod n$，可得 $T$ 的最小值为 $\frac{n}{\gcd(k,n)}$。 - 于是 $g_k$ 对应的型为 $(\frac{n}{\gcd(k,n)})^{\gcd(k,n)}$。 考察翻转操作。 - 如果 $n$ 为奇数，则 $n$ 种翻转操作一致，对称轴上的点为 $1$ 轮换，型为 $(1)^1(2)^{\frac{n-1}{2}}$。 - 如果 $n$ 为偶数，两点为轴时型为 $(1)^2(2)^{\frac{n}{2}-1}$，两边中点为轴时型为 $(2)^{\frac{n}{2}}$。 --- 旋转翻转同构同时，可以将所有颜色变为 $+1\pmod m$。 显然是不能分开考虑的，因为不构成群。所以考虑复合。 翻转复合操作较为简单，考察旋转复合操作。 考虑旋转 $i$ 个点，并且颜色 $+d$，对于一个环来说，长度为 $k=\frac{n}{(n,i)}$，那么对于环上的染色，需要满足 $a_2\equiv a_1+d$，$a_3\equiv a_2+d$ 以此类推。最终可以知道 $kd\equiv 0\pmod m$。于是 $d$ 的取值有 $(k,m)$ 种，然后推一下式子即可。 --- [[SHOI2006] 有色图](https://www.luogu.com.cn/problem/P4128)。 置换群显然是点的排列。考虑对于一种点的置换，其边的等价类的数量。 假如说该置换划分出了长度分别为 $b_1,b_2,\cdots,b_k$ 的置换环（相当于轮换）。那么对于一条边，如果端点属于同一个环中，则等价类的个数为 $\lfloor \frac{b_i}{2}\rfloor$，因为长度相同的环一定可以互相得到；如果不属于同一个环中，则周期为 $\text{lcm}(b_i,b_j)$，所以等价类个数为 $\frac{b_ib_j}{\text{lcm}(b_i,b_j)}=\gcd(b_i,b_j)$。 但是显然不能直接枚举排列，考虑枚举 $b$，钦定单调顺序那么方案数即为自然数的划分，在 $n=53$ 的条件下在 $3\times 10^5$ 级别左右。现在问题就转换成对于一类置换环，统计有多少个排列。 首先是一个多重集的排列，即 $\dfrac{n!}{\prod b_i!}$，然后对于环需要乘上圆排列即 $\prod(b_i-1)!$。又因为对于 $b_i$ 相同的可能会算重，所以需要除以 $\prod c_i!$，$c_i$ 表示个数。