Burnside 引理
设 \(A\) 和 \(B\) 为有限集合，\(X\) 为 \(A\to B\) 的一个映射集合，\(G\) 是 \(A\) 上的一个置换群，\(X/G\) 表示置换群 \(G\) 作用在 \(X\) 上产生的所有映射的等价类的集合（若 \(X\) 中两个映射经过 \(G\) 中的置换作用后相等， 那么这两个映射属于同一个等价类），则：
\[|X/G|=\dfrac{1}{|G|}\sum_{g\in G}|X^g| \]其中 \(X^g=\{x|x\in X ,g(x)=x\}\)，即 \(g\) 作用在 \(X\) 上的不动点。
可以翻译为：等价类个数=置换群中每个置换的不动点的平均数。
证明：
这里给出 Burnside 引理的更一般些的情况。
设有限集 \(F,G\) 和二元运算符 \(*:F\times G\to F\) 和 \(*:G\times G\to G\)。
其中存在 \(e\in G\)，对于任意 \(f\in F,g_1,g_2,g_3\in G\)，满足：
\[\begin{aligned} (g_1*g_2)*g_3&=g_1*(g_2*g_3)\\ g_1*g_2&=g_2*g_1\\ g_1*e&=g_1\\ \exists_{g_1^{-1}\in G},g_1*g_1^{-1}&=e\\ (f*g_1)*g_2&=f*(g_1*g_2) \end{aligned} \]对于任意 \(f_a,f_b\in F\)，定义 \(f_a,f_b\) 等价当且仅当存在 \(g\in G\)，使得 \(f_a*g=f_b\)，记作 \(f_a\equiv f_b\)。容易验证该等价关系是自反、对称、传递的。
定义 \(S:=\{\{h\in F:f\equiv h\}:f\in F\}\)，即所有等价类构成的集合。
定义 \(c:G\to 2^F\) 根据 \(c(g):=\{f\in F:f*g=f\}\)，即 \(g\) 的不动点。
定义 \(c:F\to 2^G\) 根据 \(c(f):=\{g\in G:f*g=f\}\)，即 \(f\) 的稳定核。
那么 Burnside 引理说明的是：
\[|S|=\frac{1}{|G|}\sum_{g\in G}|c(g)| \]为证明此事，我们先将 \(\sum_{g\in G}|c(g)|\) 转化：
\[\begin{aligned} &\sum_{g\in G} |c(g)|\\ =&\sum_{f\in F} |c(f)|\\ =&\sum_{E\in S} \sum_{f\in E}|c(f)| \end{aligned} \]现在对于某个等价类 \(E\) 来考虑。
我们先证明，对于所有 \(f_1,f_2\in E\)，都有 \(c(f_1)=c(f_2)\)。
根据定义，存在 \(g_1\in G\) 使得 \(f_1*g_1=f_2\)，那么对于任意 \(g_2\in c(f_1)\)，有：
\[f_2*g_2=(f_1*g_1)*g_2=f_1*g_2*g_1=f_1*g_1=f_2 \]于是 \(g_2\in c(f_2)\)，那么 \(c(f_1)\subseteq c(f_2)\)。同理可证 \(c(f_2)\subseteq c(f_1)\)，于是 \(c(f_1)=c(f_2)\)。
那么我们不妨记 \(C=c(f)\)，其中 \(f\in E\)。于是：
\[\sum_{f\in E}|c(f)|=\sum_{f\in E}|C|=|E|\cdot |C| \]任取 \(f_s\in E\)。
根据有限选择引理，存在一个映射 \(g_o:E\to G\)，使得对于任意 \(f\in E\) 都有 \(g_o(f)\in \{g\in G:f_s*g=f\}\)，即对于每个 \(f\in E\) 都选出了一个代表元 \(g_o(f)\) 使得 \(f_s*g_o(f)=f\)。
考虑映射 \(T:=E\times C\to G\) 根据 \(T(f,g):=g_o(f)*g\)，那么 \(f_s*T(f,g)=f\)。可以证明 \(T(f,g)\) 为单射。
证明 \(T(f,g)\) 也是满射。对于任意 \(g_v\in G\)，构造 \(f:=f_s*g_v\) 和 \(g:=g_v*g_o(f)^{-1}\)，那么 \(f\in E\) 且 \(g\in C\)（\(f=f_s*g_v=f_s*g_0(f)*g=f*g\)），且 \(T(f,g)=g_v\)。
从而 \(T\) 是双射，于是 \(|E|\cdot |C|=|G|\)。那么：
\[\begin{aligned} &\frac{1}{|G|}\sum_{g\in G}|c(g)|\\ =&\frac{1}{|G|}\sum_{E\in S}|E|\cdot |C|\\ =&\frac{1}{|G|}\sum_{E\in S}|G|\\ =&|S| \end{aligned} \]证毕。
Polya 定理
对于 \(X\) 为 \(A\to B\) 的所有映射的集合的情况，我们有：
\[|X/G|=\dfrac{1}{|G|}\sum_{g\in G}|B|^{c(g)} \]其中 \(c(g)\) 表示置换 \(g\) 能拆分成的不相交的循环置换的数量，即置换 \(g\) 中的环的数量。
解释起来很简单，我们只是把 Burnside 引理中的 \(|X^g|\) 改成了 \(|B|^{c(g)}\)，这是因为 Burnside 引理中 \(g(x)=x\) 的充要条件显然是 \(g\) 中的每一个环内的所有元素都对应的是 \(B\) 中的同一个元素。
标签：引理,映射,sum,等价,Burnside,aligned,Polya From： https://www.cnblogs.com/ez-lcw/p/16843024.html