定义
群：\((S,\circ)\)，集合\(S\) 和二元运算 \(\circ\)，其中 \(\cdot\) 满足：
封闭性；结合律；存在单位元 \(e\)；任意元素 \(a\) 存在逆元 \(a^{-1}\)．
若仅满足存在左单位元和左逆元，可证左右单位元/逆元唯一且相等。
交换群 / 阿贝尔群：满足交换律的群。
半群：运算仅要求封闭性和结合律。
幺半群：有幺元（单位元）的半群。
置换群：对于一个集合 \(A\)，若集合 \(G\) 中每个元素都是 \(A\) 到 \(A\) 的双射，则 \(G\) 为 \(A\) 上的置换群。
子群：群的子集，关于母群的运算成群。
Burnside 引理
lagrange 定理：群 \(G\) 的子群 \(H\) 一定满足 \(|H|\) 整除 \(|G|\)．
一些前置证明与陪集分解
自己编的证明，是不是最简单的证明不管了（
定义左陪集：\(aH=\{ah|h\in H\}\)．
引理一：对于 \(x\in aH\) 有 \(xH=aH\)（\(xi=(aj)i=a(ji)=ak\)）
根据引理一可以导出 \(aH=bH\Leftrightarrow a,b\in aH\)
引理二：\(H\) 和 \(aH\) 要不然同构，要不然不交。
若不满足，则以下两个命题均成立：
- \(\exist i\in aH,i\notin H\)
- \(\exist j\in aH,j\in H\)
根据引理一，\(iH=jH=aH\)；其中 \(j\in H\) 则 \(jH=H\)（引理一的特殊形> 式，\(a=e\) 时）
那么 \(iH=jH=aH=H\)，则 \(i,j,a\in H\)，与假设矛盾。引理二得证。
根据引理二，可得 \(aH,bH\) 要不然同构，要不然不交（等价于 \(H\) 和 \(> (a^{-1}b)H\)）。
\(G\) 是有限群，则存在正整数 \(k\) 使得 \(G=a_1H\cup a_2H\cup > \cdots\cup a_kH\)，且这 \(k\) 个陪集两两不交，则 lagrange 定理得证。
这个玩意叫陪集分解。
构造考虑当前已经有 \(a_1H\cup a_2H\cup \cdots\cup a_iH\subseteq G\)，选取补集中任意一个元素作为下一个 \(a\) 即可。
轨道-稳定子定理
现在作用在 \(S\) 上有个置换群 \(G\)．
轨道：\(x\in S\)，其轨道为 \(O(x)=\{fx|f\in G\}\)，也就是在这个置换群作用下 \(x\) 的等价类。
稳定子：\(x\in S\)，其稳定子为 \(\text{Stab}(x)=\{f\in G|f(x)=x\}\)，也就是作用之后 \(x\) 不动的置换集合。容易验证其是 \(G\) 的一个子群。
轨道-稳定子定理：\(G=|O(x)|\cdot |\text{Stab}(x)|\)，\(x\) 所在等价类的大小，乘上使 \(x\) 不动的置换个数。
考虑 \(\text{Stab}(x)\) 的陪集分解，然后就显然了（）而且还有同一等价类中的 \(O\) 和 \(\text{Stab}\) 均相等。
Burnside 引理
令 \(F(g)\) 为置换 \(g\) 作用下不动点构成的集合，则等价类个数（本质不同轨道数）为：
\[\frac{1}{|G|}\sum_{g\in G}|F(g)| \]让每个等价类中每个元素 \(x\) 贡献 \(\frac{1}{|O(x)|}=\frac{|\text{Stab}(x)|}{|G|}\)，然后交换一下求和号即证。
所谓 Pólya 就是将 \(F(g)\) 写出来，也就是 \(m^c\)，其中 \(m\) 是颜色数，\(c\) 是 \(g\) 的置换环数。
与 exp 区分
注意区分 exp 和 burnside 的区别，如果拼接了若干个组合对象，它们之间没有顺序。对这个新的组合对象奇数，是用 exp 还是 burnside 呢？现在考虑一下拼接 \(k\) 个组合对象：
如果有标号，那么考虑将单个组合对象的 EGF \(F\) 直接 \(k\) 次幂，考虑答案的任意一种方案，其中每个组合对象之间都是有区分的，所以一共被算了 \(k!\) 次，那么确实是 \(F^k/{k!}\)，例子就是有标号无向图计数。
如果无标号，考虑 OGF \(F\) 直接 \(k\) 次幂，但是这个时候发现答案的各个方案，被算重的个数实际上是一个多重集的排列数，并不好算。这个时候就要用 burnside，例子就是烷基计数。
标签：cup,aH,Stab,text,Burnside,引理,陪集 From： https://www.cnblogs.com/do-while-true/p/17300687.html