为了防止明天就把好不容易听完的东西都还给 rabbit_lb 了，还是记一点吧。
1. 群论基础
1.1 群(group) 的定义
给定集合 \(G\) 和 \(G\)上的二元运算 \(\cdot\)，满足下列条件称之为群：
- 封闭性：若 \(a,b\in G\)，则 \(a\cdot b\in G\)。
- 结合律：对于任意 \(a,b,c\in G\)，有 \((a\cdot b)\cdot c=a\cdot (b\cdot c)\)。
- 单位元：存在单位元 \(e\in G\)，\(\forall a\in G,\, a\cdot e=e\cdot a=a\)。
- 逆元：对于任意 \(a\in G\)，存在 \(b\in G\)，使得 \(a\cdot b=b\cdot a=e\)。记为 \(b=a^{-1}\)。
1.2 一些概念
-
群元素个数有限则称为有限群，无限则称为无限群。
-
有限群 \(G\) 的元素个数叫做群的阶，记做 \(|G|\)。
-
设 \(G\) 和 \(G\)上的二元运算 \(\cdot\) 构成一个群，\(H\) 是 \(G\) 的子集，且 \(H\) 在原有运算下也是一个群，则 \(H\) 为 \(G\) 的一个子群。
-
若群 \(G\) 的任意两元素均满足交换律，则称 \(G\) 为交换群（Abel 群）。
1.3 群的性质
- 单位元唯一：\(e_1e_2=e_1=e_2\)
- 消去律：\(ab=ac\Rightarrow b=c\)
- 每个元的逆元唯一：反证，若 \(aa^{-1}=a^{-1}a=e,\, ab^{-1}=a^{-1}b=e\)，则 \(aa^{-1}=ab^{-1}\)，即 \(a^{-1}=b\)。
- 若 \(G\) 有限，且 \(a\in G\)，则存在最小正整数 \(r\)，使得 \(a^r=e\)，且 \(a^{-1}=a^{r-1}\)。\(r\) 称为 \(a\) 的阶。
2. 置换群
2.1 置换
\([1,n]\) 到自身的一个映射称为 \(n\) 阶置换，表示为 \(\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix}\)，其中 \(a_1,a_2,\dots,a_n\) 是 \([1,n]\) 的一个排列。
\(n\) 阶置换共有 \(n!\) 个，同一个置换有 \(n!\) 中表示方法，如 \(p_1=\begin{pmatrix}1&2&3&4\\3&1&2&4\end{pmatrix}=\begin{pmatrix}3&1&4&2\\2&3&4&1\end{pmatrix}\)。\(n\) 阶置换也可以看作 \([1,n]\) 上的一元运算。
设 \(P_1=\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix},\, P_2=\begin{pmatrix}1&2&\dots & n\\b_1&b_2&\dots&b_n\end{pmatrix}\)，则定义置换乘法 \(P_1P_2=\begin{pmatrix}1&2&\dots & n\\b_{a_1}&b_{a_2}&\dots&b_{a_n}\end{pmatrix}\)。
置换乘法不满足交换律，但满足结合律。
2.2 置换群
\([1,n]\) 上由多个置换组成的集合，在 2.1 的乘法定义下构成的群，称为置换群。
- 封闭性：\(\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix} \begin{pmatrix}a_1&a_2&\dots & a_n\\b_1&b_2&\dots&b_n\end{pmatrix}=\begin{pmatrix}1&2&\dots & n\\b_1&b_2&\dots&b_n\end{pmatrix}\)
- 结合律：由 2.1 知置换乘法满足结合律。
- 单位元：\(e=\begin{pmatrix}1&2&\dots & n\\1&2&\dots&n\end{pmatrix}\)
- 逆元：\(\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix}^{-1}=\begin{pmatrix}a_1&a_2&\dots & a_n\\1&2&\dots&n\end{pmatrix}\)
\([1,n]\) 上的所有（\(n!\) 个）置换构成的群，称为 \(n\) 阶对称群，记作 \(S_n\)。平时所说的 \([1,n]\) 上的一个置换群，一定是 \(S_n\)的子群。
2.3 循环
2.3.1 置换的循环表示
置换 \(\begin{pmatrix}1&2&\dots & n\\a_1&a_2&\dots&a_n\end{pmatrix}\) 可以写作 \((1,a_1,a_{a_1},\dots)(\dots)\) 的形式，称为置换的循环表示。E.g. \(\begin{pmatrix}1&2&3 & 4&5\\3&1&2&5&4\end{pmatrix}=(132)(45)\)，\(\begin{pmatrix}1&2&3 & 4&5\\5&2&3&1&4\end{pmatrix}=(154)(2)(3)\)。
\((a_1a_2\dots a_m)\) 称为 \(m\) 阶循环，有 \(m\) 种表示方法。
通常情况下，我们可以忽略所有阶为 \(1\) 的循环。两个不相交的循环之间满足交换律。
定理：任意置换可表示成若干不相交循环的积。
证明：考虑令置换 \(i\) 向 \(a_i\) 连边，图由若干个环构成。显然每个环都可以表示成一个循环。
2.3.2 共轭类
我们设置换 \(p\) 的循环表示为 $p=(a_1a_2\dots a_{k_1})(b_1,b_2\dots b_{k_2})\dots (h_1h_2\dots h_{k_n})，其中 $$\sum\limits_{i=1}^n k_i=n$。设 \(k\) 阶循环出现的次数为 \(c_k\)。
那么置换 \(p\) 的格式为 \((1)^{c_1}(2)^{c_2}\dots(n)^{c_n}\)。E.g. \((1)(23)(4567)\) 的格式为 \((1)^1(2)^1(4)^1\)。
则 \(S_n\) 中所有相同格式的置换构成一个共轭类。
定理：\(S_n\) 中 \((1)^{c_1}(2)^{c_2}\dots(n)^{c_n}\) 所在的共轭类元素个数为 \(\dfrac{n!}{(c_1!c_2!\dotsc_n!)(1^{c_1}2^{c_2}\dots n^{c_n})}\)。
可以这样理解这个式子：
- 一个长度为 \(i\) 的循环共有 \(i\) 种表示，\(c_i\) 个长度为 \(i\) 的循环有 \(i^{c_i}\) 种表示；
- 对互不相交的 \(c_i\) 个循环枚举全排列，共有 \(c_i!\) 种表示。
2.3.3 对换与奇偶置换
\(2\) 阶循环叫做对换。
定理：任意循环都可以表示为若干对换的积。
推柿子：
\[\begin{aligned} &(1\, 2\, 3\dots n-1)(1\, n)\\ =&\begin{pmatrix}1&2&\dots & n-1\\2&3&\dots&1\end{pmatrix}\begin{pmatrix}1&2&\dots & n-1&n\\n&2&\dots&n-1&1\end{pmatrix}\\ =&\begin{pmatrix}1&2&\dots & n-1&n\\2&3&\dots&n&1\end{pmatrix}\\ =&(1\,2\,\dots\,n) \end{aligned} \]那么进一步地，有分解 \((1 2\dots n)=(12)(13)\dots(1n)\)。注意每个置换的分解不唯一。
若一个置换能分解为奇数个对换之积，则为奇置换；否则为偶置换。
Warning. 置换相乘的奇偶性类似于自然数加法，而非自然数乘法：奇 x 奇 = 偶，奇 x 偶 = 奇。
3. Burnside 引理
3.1 等价类与 \(k\) 不动置换类
设 \(G\) 是 \([1,n]\) 上的一个置换群，\(k\in [1,n]\)。\(G\) 中使 \(k\) 元素保持不变的置换全体，称为 \(k\) 不动置换类，记作 \(Z_k\)。
定理：置换群 \(G\) 的 \(k\) 不动置换类 \(Z_k\) 是 \(G\) 的子群。
- 封闭性：\(k\) 怎么置换都不动。
- 结合性：显然。
- 单位元：\(G\) 的单位元也在 \(Z_k\) 中。
- 逆元：\(Z_k\) 中的置换 \(p\) 在 \(G\) 中的逆元 \(p^{-1}\) 也在 \(Z_k\) 中。
置换 \(p_i\) 使图像 \(k\) 变为 \(l\)，则称 \(k\) 和 \(l\) 属于同一个等价类。设 \(k\) 所在的等价类记为 \(E_k\)。
如图，将正方形四个顶点红蓝染色，等价类个数为 \(6\)。（每行是一个等价类）
3.2 轨道稳定子定理
定理：设 \(G\) 是 \([1,n]\) 上的一个 置换群，\(E_k\) 是 \([1,n]\) 在 \(G\) 的作用下包含 \(k\) 的等价类，\(Z_k\) 是 \(k\)不动置换类。有 \(|E_k||Z_k |=|G|\)。
证明：每个等价类有 \(|E_k|\) 个元素，同时因为它们属于同一等价类，每个元素的 \(Z_k\) 相同。因此这些 \(Z_k\) 覆盖了整个 \(G\)，即每个等价类都有 \(|E_k||Z_k |=|G|\)。
3.3 Burnside 引理
将上式变形，有：
\[\sum_{k=1}^n \frac{|Z_k|}{|G|}=\sum_{k=1}^n \frac{1}{|E_k|} \]仔细想一下会发现 \(\sum_{k=1}^n \frac{1}{|E_k|}\) 就是等价类个数。
然而问题并没有解决，因为 \(Z_k\) 不好求。进一步地，我们定义 \(c_1(a_k)\) 表示在置换 \(a_k\) 的作用下不动点的个数，即长度为 \(1\) 的循环个数。那么等价类个数为：
\[l=\frac{1}{|G|}\sum_{j-1}^n c_1(a_j) \]这个式子就是 Burnside 引理。
4. Pólya 定理
Pólya 定理是 Burnside 引理的推广，应用于 染色问题 的 循环同构 方案计数。
设 \(G=\{P_1,P_2,\dots,P_g\}\) 是 \(n\) 个对象 的一个置换群，\(C(P_k)\) 是置换 \(P_k\) 的循环的个数，用 \(m\) 种颜色对 \(n\) 个对象着色，着色方案数为
\[l=\frac{1}{|G|} \sum_{j=1}^g m^{C(P_j)} \]
接下来用一个例题说明该定理的具体用法。
用火柴搭一个足球，有多少种方案？
Tips: 足球有 \(60\) 个顶点，\(90\) 条棱，\(12\) 个五边形，\(20\) 个六边形。
- 不动：\(1\) 种置换，\(2^{90}\) 种染色；
- 五边形对五边形转：\(6\times 4=24\) 种置换，\(2^{90/5}\) 种染色；
- 六边形对六边形转：\(10\times 2=20\) 种置换，\(2^{90/3}\) 种染色；
- 棱中点对棱中点转：\(15\) 种置换，\(0\) 种染色（一定都会变）。
则本质不同的方案数为 \((2^{90}+24\times 2^{18}+20\times 2^{30})/(1+24+20+15)\)。
5. 例题
P4980【模板】Polya 定理
板子。发现置换只有旋转，考虑枚举旋转的角度，有：
\[\frac{1}{n}\sum_{k=1}^n n^{\gcd(k,n)} \]枚举 \(\gcd\)，可以变成
\[\frac{1}{n} \sum_{d\mid n}n^d \sum_{k=1}^{\frac{n}{d}}[\gcd(k,\frac{n}{d})=1] \]也就是
\[\frac{1}{n}\sum_{d\mid n}n^d\varphi(\frac{n}{d}) \]暴力计算欧拉函数即可通过。
ARC062F Painting Graphs with AtCoDeer
别急，还没写完。
标签：dots,begin,end,cdot,置换,pmatrix,lya,Burnside,引理 From： https://www.cnblogs.com/ying-xue/p/burnside-polya.html