群论
群的基本概念
定义：给定一个集合 \(G\) 和关于该集合的一种二元运算 \(*\)。我们称 \(G\) 在 \(*\) 的运算下是一个群（\(*\) 在表示的时候可以省略），当且仅当满足以下条件。
- 若有 \(a,b\in G\)，则一定有 \((a*b)\in G\)；
- 若有 \(a,b,c\in G\)，则 \((a*b)*c=a*(b*c)\)；
- 存在单位元，我们称元素 \(e\in G\) 为单位元当且仅当 \(\forall\ x\in G\)，\(x*e=e*x=1\)；
- 存在逆元，对于 \(G\) 中的任意一个元素 \(x\)，如果 \(\exists\ y\in G\)，\(x*y=y*x=e\)，则称 \(y\) 为 \(x\) 的逆元，即 \(y=x^{-1}\)；
群的定理
- 单位元唯一
证明：考虑反证法。若存在两个不同的单位元，表示成 \(e_1,e_2\)，那么有 \(e_1=e_1e_2=e_2\)，与假设矛盾。
- 逆元唯一
证明：仍然考虑反证。对于一个元素 \(x\in G\)，如果存在两个逆元 \(y_1,y_2\)，那么有 \(y_1=y_1*e=y_1*(y_2*x)=(y_1*x)*y_2=e*y_2=y_2\)，与假设矛盾。
- 具有消去律，即若 \(a*c=b*c\)，则 \(a=b\)
证明：\(a*c=b*c\Rightarrow a*c*c^{-1}=b*c*c^{-1}\Rightarrow a*e=b*e\Rightarrow a=b\)
- \(a^{-1^{-1}}=a\)
证明：因为 \(a^{-1^{-1}}\) 和 \(a\) 均为 \(a^{-1}\) 的逆元，由定理一单位元唯一可知，\(a^{-1^{-1}}=a\)
置换的基本概念
定义：令 \(x\) 是一个非空有限集合，将 \(x\) 的一种到自身的一一映射称作一个置换。记为：
\[\sigma=\begin{bmatrix}a_1&a_2&a_3&\cdots&a_{n-1}&a_n\\b_1&b_2&b_3&\cdots&b_{n-1}&b_n\end{bmatrix} \]其中，\(b\) 是 \(a\) 的一组排列。
例如：\(x=\{1,2,3\}\)，\(\sigma=\begin{bmatrix}1&2&3\\2&3&1\end{bmatrix}\)
这里，我们可以将置换中的轮换简记在一起。
例：
\[\sigma = \begin{bmatrix}1&2&3&4&5&6\\2&3&1&6&4&5\end{bmatrix} \]其中，\(1\rightarrow2\rightarrow 3\) 是一组轮换，\(4\rightarrow6\rightarrow 5\) 也是一组轮换。故可以记为
\[\sigma=\begin{bmatrix}1&2& 3\end{bmatrix}\begin{bmatrix}4&6&5\end{bmatrix} \]置换的集合：对于 \(n\) 个元素的集合 \(x\)，其所有的置换共有 \(n!\) 个，所有的置换所构成的集合记为 \(S_n\)。
例：
\[S_3=\begin{Bmatrix}\begin{bmatrix}1&2&3\\1&2&3\end{bmatrix},\begin{bmatrix}1&2&3\\1&3&2\end{bmatrix},\begin{bmatrix}1&2&3\\2&1&3\end{bmatrix}\\\begin{bmatrix}1&2&3\\2&3&1\end{bmatrix},\begin{bmatrix}1&2&3\\3&1&2\end{bmatrix},\begin{bmatrix}1&2&3\\3&2&1\end{bmatrix}\end{Bmatrix} \]置换的合成
也叫做置换的乘法。
设有两个置换 \(f=\begin{bmatrix}1&2&3&\cdots&a_n\\i_1&i_2&i_3&\cdots&i_n\end{bmatrix}\)，\(g=\begin{bmatrix}1&2&3&\cdots&a_n\\j_1&j_2&j_3&\cdots&j_n\end{bmatrix}\)，那么有
\[\begin{aligned} g*f(k) & = g(f(k)) \\ & = j_{i_k} \end{aligned} \]不难发现，置换合成的本质就是重复映射。
例：
\(f=\begin{bmatrix}1&2&3&4&5\\2&5&1&3&4\end{bmatrix}\)，\(g=\begin{bmatrix}1&2&3&4&5\\4&3&2&5&1\end{bmatrix}\)
写的直白点，就是
\[1\xrightarrow{f}2\xrightarrow{g}3 \]\[2\xrightarrow{f}5\xrightarrow{g}1 \]\[3\xrightarrow{f}1\xrightarrow{g}4 \]\[4\xrightarrow{f}3\xrightarrow{g}2 \]\[5\xrightarrow{f}4\xrightarrow{g}5 \]就可以得到
\[\begin{aligned}f*g&=\begin{bmatrix}1&2&3&4&5\\2&5&1&3&4\end{bmatrix}*\begin{bmatrix}1&2&3&4&5\\4&3&2&5&1\end{bmatrix}\\&=\begin{bmatrix}1&2&3&4&5\\3&1&4&2&5\end{bmatrix}\end{aligned}\]当然，置换中的元素顺序是可以更改的，那么可以重排元素使得更好地表示结果。
\[\begin{aligned}f*g&=\begin{bmatrix}1&2&3&4&5\\2&5&1&3&4\end{bmatrix}*\begin{bmatrix}2&5&1&3&4\\3&1&4&2&5\end{bmatrix}\\&=\begin{bmatrix}1&2&3&4&5\\3&1&4&2&5\end{bmatrix}\end{aligned}\]置换合成运算的性质。
- 没有交换律；
- 有结合律；
- 置换合成后依然是一个置换；
- 恒等变换（单位元）
-
逆元
对于一个置换 \(f\)，称 \(g\) 为 \(f\) 的逆元，当且仅当满足 \(f*g=\tau\)，记为 \(f^{-1}\)。
置换群
定义：对于含 \(n\) 个元素的置换集合 \(S_n\)，有子集 \(G\in S_n\)，且满足：
- 合成运算的封闭性，即 \(\forall\ f,g\in G\)，\((f*g)\in G\)；
- \(\tau\in G\)；
- 存在逆元，即 \(\forall\ f\in G\)，\(f^{-1}\in G\)；
置换的循环
如果将置换的一条映射看作是一条有向边，由 \(i\) 连向 \(a_i\)，每个点的出入度均为 \(1\)，那么整个图就是若干个环。
-
不变元：
我们将 \(x\) 中在置换后不变的元素称为不变元，也可以称为稳定核。 -
\(k\) 不变置换类：
符号 \(Z_k\)，对于 \(x\in G\)，如果 \(k\) 为 \(x\) 的不变元，则称 \(x\) 属于 \(k\) 不变置换类，记作 \(x\in Z_k\)。显然，\(Z_k\) 为 \(G\) 的子群。 -
等价类：
等价类 \(E_k\) 表示对元素 \(k\) 施加任意的 \(G\) 中置换后能够得到的元素集合。- 定理：当 \(x,y\) 属于同一个等价类时，有 \(\vert Z_x\vert =\vert Z_y\vert\)；
证明：考虑在 \(Z_x\)，\(Z_y\) 间构造双射，构造完后显然有元素个数相同。由定义，\(\exists\ p\in G\)，\(x\xrightarrow{p}y\)，\(y\xrightarrow{p^{-1}}x\)，\(\forall\ o\in Z_x\)，都有 \(y\xrightarrow{p^{-1}}x\xrightarrow{o}x\xrightarrow{p}y\)，可以构造 \(o'=p^{-1}*o*p\) 满足 \(o'\in Z_y\)。因为 \(o'=(p^{-1}*p)*o=o\)，所以 \(\forall\ o\in Z_x\)，\(o\in Z_y\)，反之亦然。
- 定理：当 \(x,y\) 属于同一个等价类时，有 \(\vert Z_x\vert =\vert Z_y\vert\)；
Q. 给定一个 \(4\) 个顶点的正方形，现在用黑白两种颜色为正方形的顶点染色，求本质不同的正方形数量。（正方形旋转算同一种）
下面用 \(\circ\) 表示白色，\(\bullet\) 表示黑色。
\[\ \circ-\circ\ \quad \ \bullet-\circ\ \quad \ \circ-\bullet\ \quad \ \circ-\circ\\ \ |\ \ 1 \ \ | \quad\ \ \ |\ \ 2 \ \ | \quad\quad |\ \ 3 \ \ | \quad\ \ \ |\ \ 4 \ \ |\\ \ \circ-\circ\ \quad \ \circ-\circ\ \quad \ \circ-\circ\ \quad \ \circ-\bullet\\ \ \circ-\circ\ \quad \ \bullet-\bullet\ \quad \ \circ-\bullet\ \quad \ \circ-\circ\\ \ |\ \ 5 \ \ | \quad\ \ \ |\ \ 6 \ \ | \quad\quad |\ \ 7 \ \ | \quad\ \ \ |\ \ 8 \ \ |\\ \ \bullet-\circ\ \quad \ \circ-\circ\ \quad \ \circ-\bullet\ \quad \ \bullet-\bullet\\ \ \bullet-\circ\ \quad \ \bullet-\circ\ \quad \ \circ-\bullet\ \quad \ \bullet-\bullet\\ \ \ |\ \ 9 \ \ | \quad\ \ \ |\ 10 \ | \quad\quad |\ 11 \ | \quad\ \ \ |\ 12\ |\ \\ \ \bullet-\circ\ \quad \ \circ-\bullet\ \quad \ \bullet-\circ\ \quad \ \circ-\bullet\\ \ \circ-\bullet\ \quad \ \bullet-\circ\ \quad \ \bullet-\bullet\ \quad \ \bullet-\bullet\\ \ \ |\ 13\ | \quad\ \ \ |\ 14 \ | \quad\quad |\ 15 \ | \quad\ \ \ |\ 16\ |\ \\ \ \bullet-\bullet\ \quad \ \bullet-\bullet\ \quad \ \bullet-\circ\ \quad \ \bullet-\bullet\\ \]- 情况1：顺时针旋转 \(0\) 度，不变元 \(16\) 个；
- 情况2：顺时针旋转 \(90\) 度，不变元 \(2\) 个；
- 情况3：顺时针旋转 \(180\) 度，不变元 \(4\) 个；
- 情况4：顺时针旋转 \(270\) 度，不变元 \(2\) 个；
应该如何计数，需要引入定理。
Burnside 定理
对于置换群 \(G\)，定义 \(cnt(\sigma)\) 表示 \(\sigma\) 中不变元的数量，那么 \(G\) 中的不等价种类（即染色方案）为
\[ T = \tfrac{1}{\vert G\vert}\sum_{\sigma \in G} cnt(\sigma) \]简单来说，等价类的数量 \(=\) 各置换下不变元数量的和的平均数。
证明：
令 \(siz=\vert G\vert\)，\(G=\{\sigma_1,\sigma_2,\cdots,\sigma_m\}\)，记 \(b_{i,k}=[k\xrightarrow{\sigma_i}k]\)。显然有 \(cnt(\sigma_i)=\sum\limits_{k=1}^n b_{i,k}\)，且 \(\vert Z_k\vert=\sum\limits_{i=1}^ms_{i,k}\)。故 \(\sum\limits_{i=1}^m\sum\limits_{k=1}^nb_{i,k}=\sum\limits_{i=1}^mcnt(\sigma_i)=\sum\limits_{k=1}^n\vert Z_k\vert\)。
设这 \(T\) 个互不相同的等价类为 \(E_1,E_2,\cdots,E_T\)，有 \(N=E_1,E_2,\cdots,E_T\)。
\[\begin{aligned} \sum\limits_{i=1}^mcnt(\sigma_i)&=\sum\limits_{k=1}^n\vert Z_k\vert\\ &= \sum\limits_{i=1}^T\sum\limits_{j\in E_i}\vert Z_j\vert\\ &= \sum\limits_{i=1}^T\sum\limits_{j\in E_i}\vert Z_i\vert\\ &= \sum\limits_{i=1}^T\vert E_i\vert\vert Z_i\vert\\ &= \sum\limits_{i=1}^TG\\ &= T\times G \end{aligned}\]\[\Rightarrow T = \tfrac{1}{\vert G\vert}\sum\limits_{i=1}^mcnt(\sigma_i) \]
在上述给正方形端点染色的实例中，根据旋转角度可以分成四种置换，每个置换的不变元数量分别为 \(16\)、\(2\)、\(4\)、\(2\)。根据 Burnside 定理，染色方案为 \(\tfrac{16+2+4+2}{4}=6\) 种。
Q：将数字 \(1\sim n\) 摆放到一个环中，允许旋转，求本质不同的摆放方案。
A：\(n\) 种旋转，可以对应成 \(n\) 种置换。不旋转时，不变元为 \(n!\) 个，其余情况不变元数量皆为 \(0\) 个，故本质不同的摆放方案为 \(\tfrac{n!+0+0+\cdots+0}{n}=(n-1)!\)。
Q：在上一问的基础上，还允许翻转，求本质不同的摆放方案。
A：\(n\) 种旋转，\(n\) 种翻转，总共有 \(2n\) 种置换。不旋转且不反转时，不变元有 \(n!\) 个，其余情况置换都一一错开，没有不变元。故方案数为 \(\tfrac{n!+0+0+\cdots+0}{2n}=\tfrac{(n-1)!}{2}\)。
Polya 定理
设有置换群 \(G=\{f_1,f_2,\cdots,f_n\}\)。用 \(m\) 种颜色对 \(n\) 个点染色的不等价种类数为：
\[\tfrac{1}{\vert G\vert}\sum\limits_{f\in G}T(f) \]其中 \(T(f)\) 指在置换 \(f\) 下置换前后染色状态均相同的方案数。
证明：设 \(G'\) 是对状态的置换群。不难发现大置换和小置换有对应关系,使用小置换对每种状态讨论即可得到大置换。
也即，设 \(f\in G\) 对应 \(f'\in G'\)。如果一种染色方案 \(x\) 在经过 \(f\) 的变换后变成了 \(y\)，则有 \(x\xrightarrow{f'}y\)，显然 \(\vert G\vert =\vert G'\vert\)。
由 Burnside 定理，结果为 \(\tfrac{1}{\vert G'\vert}\sum\limits_{f'\in G'}cnt(f')\)，而 \(cnt(f')\) 的意义正是 \(G\) 中相对应的置换 \(p\) 下不动的染色方案数。由此得证。
那如何求解 \(T(f)\)。我们令 \(s(f)\) 表示置换 \(f\) 种的循环个数，那么显然每个循环中必须染上同一种颜色，不同循环之间没有影响。故 \(T(f)=m^{s(f)}\)。
所以最后方案书可化简为
\[\tfrac{1}{\vert G\vert}\sum\limits_{f\in G}m^{s(f)} \]