Burnside 引理

不动点

一个状态置换后与原来完全相同，则称这个状态是不动点

循环

一个置换 $f=\begin{pmatrix} 1 & 2 & i & \dots & n\\ a_1 & a_2 & a_i & \dots & a_n \end{pmatrix}$ ，若存在 $k$ 个元素使得 $a_{x_1}=x_2,a_{x_2}=x_3,\cdots,a_{x_k}=x_1$ ，则 $x_1,x_2,\cdots,x_k$ 就称作一个循环。

定义

对于一个置换群 $G$ ，其不同等价类个数为

$$L=\frac 1{|G|}\sum_{\tau\in G}c_1(\tau) $$

其中， $c_1(\tau)$ 是在置换 $\tau$ 作用下不动点个数。

Polya 定理

Polya 定理对 Burnside 引理具体化，提供计算不定点具体方法。有 $n$ 个格子，每个格子染 $m$ 种颜色，求染色方案。

设 $c(\tau)$ 为置换 $\tau$ 包含的循环个数，一个循环的颜色应该相同，为一个单位。若有 $m$ 种颜色，那么不定点数就有 $m^{c(\tau)}$ 个。

$$L=\frac 1{|G|}\sum_{\tau\in G}m^{c(\tau)} $$