第1个回答 2013-04-01
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 共轭类 中置换的数目为：
证明 (见相关知识 注1)
作为例子，下表给出了对称群 的共轭类和分划的情况：
分划
共轭类中的一个置换
1+1+1+1+1
1+1+1+2
1+1+3
1+4
5
1+2+2
2+3