第十一讲 Burnside 引理与 Polya 定理
§1 (置换群基本概念) (本页） §2 (Burnside 引理与循环指标) §3 (Burnside 引理的应用) §4 (Polya 定理及其应用)
Redfield-Polya 定理是组合数学理论中最重要的定理之一．自从 1927 年 Redfield 首次运用 group reduction function 概念，现在称之为群的循环指标（circle index of a group），至今 60 多年来，他在许多实际计数问题上得到了广泛的应用，它以置换群为理论基础，与生成函数有机地结合在一起，揭示了一类具有组合意义的计数的规律性．
抽象地说在一集合内，定义了一个等价关系，人们往往关心由这个等价关系所决定的等价类的数目，Refield-Polya 理论就是为解决这类问题而发展起来的复杂计数理论．
为了帮助读者理解，本章例举了较多的实例． §1 置换群的基本概念
设有限集合 换 是从 到自身上的
，集合中的元素称为“点”．集合 上的一个置对应的映射：
设 是集合 上的另一个置换，置换 与 的乘积定义为复合映射：
例 1 设 上的二个置换：
求乘积
和 ，
解 从定义出发，
得：
设 下，集合
是集合
上的全部置换构成的集合，在复合映射定一的乘义
．对称群的任意子群称为置换群，
构成一个群，称为 次对称群
因为它们都与集合 有关，一般也称为作用在 上的置换群．因为集合 的
排列有 个，而每个排列对应一个置换，反之一个置换也对应一个排列，从而有
置换的另一种表示方法是循环表示，它可简化置换的表达方式．
设 是正整数，且满足 ，在置换 中就有一个循环
我们称它为置换 的一个 是使
循环． 显然这里要求 个点互不相同，从而整数
成立的最小正整数．由循环的定义，不难推出任意一个置换 都
可以表示成若干个互不相交的循环的积，即
例 2 将
解 先从点 计算， 再从点 计算，，最后得：
化为互不相交循环积的形式．
故 有一个 3-循环
，
. 即 有 3-循环一个，2-循
环一个，1-循环两个．有时为了简便，可将 1-循环省略不写，即：
由例 2 可看到 与 表示的置换是相同的．推
广到一般情形，互不相交的循环积是可交换的，即：
这里 是 的互不相交的循环，
当两个循环的交非空时，两循环的乘积一般是不可交换的． 例如取例 1 中的 和 ，将它们分别化为不相交循环的乘积：
计算 知
，
，比较可
设置换 ，它的逆置换为：
这是因为 为恒等置换．
设置换 为互不相交的循环，则
对置换 ，使 为
．由定义容易证明
成立的最小正整数 称为置换 的阶记
其中 当
表示最小公倍数． 时，
循环总可以写成若干个
循环和若干个 循环的乘积，
此时若置换 中有偶数个 循环， 称为偶置换；若有奇数个 2-循环， 称
循环
，
，
为奇置换．这个定义是有意义的，因为对任意的
有：若 是一个偶置换，那么 或 就一定是奇置换，由此可知，在对称群 中，偶置换的数目与奇置换的数目相等，都等于 偶置换，在
中全部偶置换构成一个子群
设 与 是对称群 使得
中的置换划分为若干个共轭类，同
中的两个置换， 与 称之为共轭，如果存在
偶置换与奇置换的乘积仍为
，称为 次交错群，显然
易知共轭关系为一个等价关系，从而
一共轭类的所有置换在分解为互不相交循环的乘积下，具有相同的循环长度．这里的循环的长度是指一个循环中点的个数；反之具有相同的循环长度的两个置换
一定共轭．即：在对称群 循环长度．
中，两置换共轭的充分必要条件是它们具有相同的
在对称群 中有多少个共轭类呢？先看一个简单的例子：
在对称群 中全部的共轭类为： 一个 一个 二个 一个 四个
循环， 循环和一个
循环
循环， 循环，二个
循环，
循环，
在 中一共有五个共轭类，而每一个共轭类恰好对应着数 4 的一种划分，即共轭类的数目等于整数4的划分数
．
一般地，任意 次对称群
．（
中的共轭类的数目等于正整数 的划分数
的定义见第十一章）
在对称群 的每个共轭类中至少有多少个置换呢？我们知道循环长度决定
循环， 个 ，
循环，， 个 这里
一个共轭类，若此共轭类中的置换有 个
循环，这个共轭类记为
.若
，
，则 被分解为
个互不相交的循环的乘积．
定理 1 共轭类 中置换的数目为：