「Learning Notes」Burnside's Lemma

前置知识

群论基础.

Definition

Simplified,Unweighted Version

G=\left\{a_{1},a_{2},...,a_{\left|G\right|}\right\} 为目标集 S 上的置换群.

c_{1}\left(a\right) 为在置换 a 下的不动点个数,亦即将置换 a 写成若干个不相交循环的乘积后长度为 1 的循环个数。

通过若干次变换 r\left(r\in G\right) 后可以相等的元素属于同一个等价类.

若置换群 G 将目标集 S 划分为 l 个等价类,则有

l=\frac{1}{\left|G\right|}\sum_{a\in G}c_{1}\left(a\right)

References

循环

置换

置换群

等价类

不动点

Burnside's Lemma

Contacts

Pólya Enumeration Theorem