组合数学基础11

第十一讲 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 共轭类 中置换的数目为：

证明 (见相关知识 注1) 注1

定理 1 共轭类 中置换的数目为：

证明 设 ，将 分解为互不相交的循环的乘积：

将 中的 个点任意排列而保留各循环之间的括号线变，一共

有 个置换，它包括了 有二个，其一如果 中有 个 循环改变了乘积顺序，即变为

中的所有置换，但其间有重复的置换，原因循环

，这里

，它们实质上是相同的，于是每个置换在排列下

，而排列后的置换只是将其

可产生 与有 个

个相同的置换；其二设 有一个 ，

，

循环 ，它

实质上是相同的循环，若 中

循环，则有 个实质相同的循环，这种情形中每个置换在排列中产

生

个相同的置换．从 个置换中去掉这些重复，就得到定理 1 的结论．

作为例子，下表给出了对称群 的共轭类和分划的情况：

分划 1+1+1+1+1 1+1+1+2 1+1+3 1+4 5 1+2+2 2+3

共轭类中的一个置换 §2 Burnside 引理与置换群的循环指标 设 是集 上的置换群，点

使得

，记为

称为“等价”，当且仅当存在置换

. 这种等价关系下的等价类称之为 的轨道，

它是集 的一个子集．

在 的作用下，集合 为 的全部轨道的不交并．事实上，如果存在一点 ，它在含有点 的轨道 对于任意的

，这样

内，同时也在含有点 的轨道

，使得

，即

，因为

内，即

，而

，，故

，则存在 ；同理可证

．换言之 的任意两个

不同的轨道的交是空集，所以置换群 的轨道是集合 上的一个划分．

例如 设 是集 上的置换群，这

里 表示恒等置换（ 中的每个 1-循环省略了），依据轨道的定义，立即可得

;

设点 ， 是 上置换群，集合

为点 的稳定子群．

，易证 是

的一个子群，称

设 ，则

，有：

．事实上因为 ，存在置换 ，使得 ，从而有

，对任意的

，即

；同理可证，故有 ．

关于 ， 和 三者之间的关系：

由轨道的定义，则

，即

．对任意的

，从而

，若 ，

，这说明轨道 中有多少个不，亦即

同的点,就对应着多少个

．

在 中的左陪集，即

定理 2（Burnside 引理） 置换群 作用在点集 上的轨道数目 等于 中平均每个置换 所稳定的点的个数．（ 所稳定的点的个数就是 的 1-循环的数目．）

设置换 稳定的点的数目为 ，Burnside 引理可表示为：

证明 (见相关知识 注2) 设 是抽象群， 是一集合，

，

，对应着 上的置换 ，且满足

设集合 ，则 是集合 上的置换群．这是因为设映射 对任意的

有：

是 的同态像，

， 从而 是同态映射，

故

是置换群．

推论 1 是抽象群， 是集合 上的置换群，且为 的同态像， 则 作用在集合 上的轨道数目为：

这里 是元素 的同态像． 证明 (见相关知识 注3)

设 是点集 上的置换群，（有非负系数的多项式，对每个置换

），已知一个关于 ，如果

的具

共轭类，那么此

置换对应单项式 和得：

对置换群 的每个置换 所对应的单项式求

称此多项式为置换群 的循环指标（circle index）多项式．

例如 假若置换群 是仅有一个恒等置换的单元群，那么这个恒等置换属于共轭类

，故 的循环指标多项式为：

由此可知 的循环指标不仅依赖于抽象群 的结构，同时也依赖于 的每个元素（点集 上的置换）的构成． 下面给出了对称群

的循环指标多项式：

,

对称群 的循环指标 的母函数为：

例 3 设 图 1），设

是三维空间中一立方体的顶点集合（见

的全体置换而构成的群，求

是由此立方体的旋转而产生的

的循环指标多项式．

图 1

解 这样的旋转共有 24 种，它们分别是：

） 恒等旋转对应的顶点置换为：，它在共轭

类 中，对应的单项式为 ；

）绕相对二面的中点的连线的 旋转，因为有三个面相对面，所以共

有 3 个这样的旋转，其中一个旋转对应的顶点的置换为:

它们在共轭类 中，对应的单项式为

）绕相对二面的中点的连线的 中一个旋转对应的顶点的置换为：

旋转，易见共有 6 个这样的旋转，其

，它在共轭类

中，对应的单项式为 ；

的旋转，因有六队相对的棱，所以共有

，

）绕相对二棱的中点的连线

6 个这样的旋转，其中一个旋转对应的顶点的置换为：

它们在共轭类 中，对应的单项式为 ；

）绕相对二顶点的联线 的旋转，这里有四对相对的顶点，共有 8 个

，它们

这样的旋转，其中一个旋转对应的顶点的置换为：

在共轭类 中，对应的单项式为 ．

立方体中一共有这 24 种互不相同的旋转，它形成立方体的旋转群，此旋转群

所产生的顶点的旋转置换群的循环指标多项式为：

若进一步设

是由立方体的旋转群而产生的边集 为：

是三维空间中立方体的边的集合，上的置换群，

中的置换所在的共轭类

）置换属于共轭类 ；

）置换属于共轭类 ；

）置换属于共轭类 ；

）置换属于共轭类 ；

）置换属于共轭类 ．

从而置换群 的循环指标多项式为

设

方体的旋转而产生的面集

是三维空间中立方体的面的集合，上的置换群，

是由立

中的置换所在的共轭类为：

） ） ）

） ）

从而置换群 的循环指标多项式为：

设 是 阶有限群，定义 上的置换 ：

由定义可知 换群．设映射

， 设 ，由推论 1知 是置

，它是同构映射，称 群为 的 Cayley 表

示．我们感兴趣的是群 的循环指标多项式．

对任意 ，设 的阶为 ，即 ， 是有限群 中的单位元，

-循环

再置换 表示为互不相交的循环的乘积时， 中必有一个

，由 的定义知， 的所有不相交循环的长度都

是

．这样 只有

个

-循环,即置换 对应的单项式是

，由于 的任意性，故置换群 的循环指标多项式为

它又可写为：

这里的整数 跑遍 的全部整除因子，且

作为特殊情形，取 是 次单位根群， 是虚数

，

单位． 是 阶循环群，故它的 Cayley 表示也是 阶循环群．设

，这里

是

的最大公约数， 则群 的循环指标多项式为：

它又可写为：这里

为 Euler 函数，即

．

，令

设 是 集上的置换群， 是 集上的置换群，且

，对每个

，

，定义集上的置换

集上的任意两个置换的乘积定义为：

，

这样在 集上形成一个置换群 与 的直积（direct product）． 由此定义，不难推出：

，称其为置换群

若 定义得时

；当

，且 ，，这里

时

．故

，且 ，由 ，显然当

的

所对应的单项式为

这样我们就得到置换群

为：

的循环指标多项式

结论：两个置换群的直积的循环指标多项式等于各置换群的循环指标多项式的乘积．

例 4 4 次交错群

求

的轨道数目．

解 稳定点 1 的稳定子群为：

，

同样稳定点的稳定子群为：

，

由 Burnside 引理知轨道数目 .

的轨道就是点集 递”置换群．

§3 Burnside 引理的应用

具有这种性质的置换群被称为“可迁”或“传

对于 Burnside 引理，读者可能感到比较抽象，下面举几个实际例子，帮助读者了解 Burnside 引理的应用．

例 5 在二维平面内有图形：方格着色，一共

，用“白色”与“花色”独立的给这四个

有种着色方法，问其中有多少种“本质”不同的着色？

这里的“本质”相同着色的意义是指由一种着色图形经适当旋转可得的另一种着色图形．例如下面四种着色：

是本质上相同的着色． 在二维空间中旋转 ，全部可能的着色，即分别为

，

和

，它们构成 4 阶旋转群．取集为

，这样每个旋转产生 集上的一个循环，设它们，它们构成 上的置换群 ．显然在同一轨道上的任

意两种着色是本质相同的着色，本质不同的着色数目就等于 在集 上的轨道数目，由 Burnside 引理，需要求每个置换的 1-循环的数目．（ Burnside 引理就在于将轨道数目的计算问题转变为比较容易的 1-循环的数目的计算问题）．

为了叙述的方便，将图形的四个方格编号为：向．容易计算

，旋转方向为顺时针方

下稳

，因为它将集 中的每个“点”都不动；在

定不变的着色满足： 与 着色相同， 与 ， 与 着色均同，即四个格同色，

由于一共有两色，故得 ；同理可知 ；在 下稳定不

变的着色满足： 与 同色， 与 同色同，一共有 种这样的着色，故得

；于是本质不同的着色数目为：

它们是：

.

上面我们用置换群

作用在全部可能着色集 上

，则 4 阶

的轨道数目解决了问题．下面换一种方法，取编号集 旋转群对应的

上的置换群

这就是说 和 群．

是此 4 阶旋转群在不同集合 和 上产生的置换

复杂的

，但由于，这使得 中的置换的表达方式要

多，对这样的计数问题，能否用 她们之间的关系．在集 分别分别对应

和

而不用 呢？要解决这个问题，就要弄清楚

的旋转

中的每个“点”（号）都可着两种颜色，， 我们知道

不变 中“点”的条件是方格 上，即在同一循环的数要着同色，

着同色，这个特点反映到元素

所以 ，在 中稳定点的个数共有 ；同理

与

与 相对应， 在

中稳定点的个数也有 ； 共有 个，于是

相对应， 在中稳定点的个数一

.

由此例可知，用置换群 代替 计数时，它与 的每个置换的不相交的

循环个数有关，当然与颜色的数目也有关．

类似地如果用红，白，黑三色独立地给图形 的每个格着色，有多少种

本质不同的着色？由上面的分析，利用置换群计算，可得：

感兴趣的读者可将这 种着色具体画出来．

如果用 种 颜色给图形 每个格着色，那么有

种本质不同的着色．注意到置换群的循环指标多项式

为：

，

取 时：

由次可略知引入置换群循环指标多项式的意义．

例 6 用红，蓝，绿三色独立地给一个三角形着色，有多少种不

同的着色方法？（图 2-的着色被看作相同的）

图 2

解 实质上这是三角形顶点之间的置换，将三角形的顶点标号（见图 2-），三角形顶点集

上的对称群 为：

它的循环指标多项式为：

，

取 这

，得

种不同的着色为：

同理可知用 种颜色独立地给三角形的顶点着色，有

解 设珠子集合为 为 (蓝)

, (红)

, (黄)

,

, 颜色集 {蓝、红、黄}, 赋权

上的置换群是二面体群:

,

的循环指标多项式为:

中全部模型的存储为:

,

所求模型的权 , 其系数为 2, 即有两种不同的项链.

例 14 设 是有限集, 是 上的置换群, 称 的子集 (记为

), 如果存在

, 使得

与 等价

, 试求等价类的数目.

解 设集 , 赋权为: , 映射 ,

其中 , 这样集 的子集与 中的映射一一对应, , 均有

中

, 从而子集的等价类为映射的等价类, 故子集等价类的数目等于

全部模型(在

.

)的存储, 由 Redfidld-Polya 定理, 等价类的数目为

如果对集 重新呀赋权为 素的子集对应的映射 的权 储为:

, 从而

, 这里 是变量, 有 个元中全部模型在此赋权下的存

的系数

是个有 个

, 在细多项式中

元素的子集的等价类的数目, 当 取遍全部非负整数时, 多项式 数.

.

是有 个元素子集的等价类的数目的母函

本文来源：https://www.bwwdw.com/article/jqnf.html