伯恩赛德定理（集合S的 置换群 诱导出来的等价关系 对集合S 划分 得到的 等价类个数）

前言：仅个人小记。这个定理就是用来计数的，用来数一数等价类的个数，而等价类本质上是一种降维表示，即把同种东西归类，进而达到简化的目的，进而更能凸现事物的本质。等价类的个数类似于线性代数里面 “秩” 这个概念，而不同的等价类则类似于不同的 “基向量” 。

前要知识和规定

1.由集合 S 上的一个置换群 $<G,\ast >$诱导的二元关系 R是一个等价关系 。证明参看 https://blog.csdn.net/qq_25847123/article/details/100253596
2. $X_{ab}$ 表示所有将 a 置换成 b 的置换的集合。

伯恩赛德(Burnside)定理内容

由集合 S 上的一个置换群 $<G,\ast >$诱导的等价关系 R 将集合 S 划分所得到的等价类数目等于
$$\frac{1}{|G|}\sum _{\pi \in G}\psi (\pi )$$$\psi (\pi )$表示 在置换 $\pi$ 作用下不变元个数。不变元指的是满足 $\pi (a)=a$ 的元素 a 。

引入 $\eta (a)$ 表示元素 a 在多少个作用下是保持不变的，由上图，显然有$$\sum _{\pi \in G}\psi (\pi )=\sum _{s\in S}\eta (s)$$$$所有行和的总和=所有列和的总和$$

故而， 想要求解等价类个数，只要数一数 G 中各个元素 $\pi$分别有多少个不变元，然后加起来，再除以置换群 G 的阶，就得到等价类的个数了。

定理证明

显然，证明$$等价类的个数=\frac{1}{|G|}\sum _{\pi \in G}\psi (\pi )$$就等价于证明$$等价类的个数=\frac{1}{|G|}\sum _{s\in S}\eta (s)$$

前要证明（1）

证明： 如果 a, b 同属一个等价类，则必然有且仅有 $\eta (a)$ 个作用，使得 a 置换成 b。

记所有作用于 a 结果仍为 a 的作用为集合 $X_{aa}$，该集合元素个数为 $|X_{aa}|=\eta (a)$。
因为 a, b 同属一个等价类，所以必然存在 ${\pi }_t$ ，有 ${\pi }_t(a)=b$。用 ${\pi }_t$和集合$X_a$中的每个元素相乘，容易证明

$${\pi }_t\ast {\pi }_i≠{\pi }_t\ast {\pi }_j,i≠j,{\pi }_i,{\pi }_j\in X_{aa}$$故而， ${\pi }_t$和集合$X_{aa}$中的每个元素相乘结果互不相同，故而可以记为集合$X_{ab}$，显然该集合元素个数为$|X_{ab}|=|X_{aa}|=\eta (a)$。

X a b = { π ∣ π ( a ) = b , ∀ π ∈ X a a } X_{ab}=\{\pi|\pi(a)=b, \forall \pi \in X_{aa}\} Xab​={π∣π(a)=b,∀π∈Xaa​}显然，集合$X_{ab}$中的每个元素都满足$$\pi (a)=b,\forall \pi \in X_{ab}$$我们认为不可能再有其他的不属于集合$X_{ab}$的作用 ${\pi }_k$ 能够 ${\pi }_k(a)=b$。反证法如下：
假定
$$\exists {\pi }_k\in ̸X_{ab},使得{\pi }_k(a)=b$$则，因为这些元素都来自置换群 G，所以这些元素都可逆。进而取集合$X_{ab}$中任一元素${\pi }_t$,则其逆元为
$${{\pi }_t}^{-1},有{{\pi }_t}^{-1}(b)=a$$进而显然$${{\pi }_t}^{-1}\ast {\pi }_k(a)={{\pi }_t}^{-1}(b)=a$$又因为封闭性，所以

$${{\pi }_t}^{-1}\ast {\pi }_k\in G$$又因为所有能够是的 a 仍作用为 a 的作用都在集合$X_{aa}$中，所以必然

$${{\pi }_t}^{-1}\ast {\pi }_k\in X_a$$进而$${\pi }_k={\pi }_t\ast ({{\pi }_t}^{-1}\ast {\pi }_k)\in X_{ab}$$与上述${\pi }_k\in ̸X_{ab}$矛盾。故而不存在其他的作用能够使得 a 作用成 b，所以，所有的能够使得 a 作用成 b 的作用都在集合 $X_{ab}$中，故而，当 a, b 同属一个等价类时，必然有且仅有 $\eta (a)$个作用，使得 a 作用成 b。证毕！

正式证明

对于任意一个置换，必然将元素 a 置换成 a 所在等价类中的某个元素，假设 a 的等价类为 [a]={a,b,…,k}，则

$$|X_{aa}|+|X_{ab}|+...+|X_{ak}|=|G|$$又根据前要证明(1)，知

$$\eta (a)=|X_{aa}|=|X_{ab}|=...=|X_{ak}|$$进而

$$\eta (a)=\eta (b)=...=\eta (k)=\frac{|G|}{k}$$由于 a 是从 S 中任意选取的，根据上面知道，$$\forall 等价类[a],\sum _{s\in [a]}\eta (s)=|G|$$进而，如果有 p 个等价类，则

$$\sum _{s\in S}\eta (s)=p|G|$$故而等价类数目为

$$p=\frac{1}{|G|}\sum _{s\in S}\eta (s)=\frac{1}{|G|}\sum _{\pi \in G}\psi (\pi )$$证毕！