组合数学（第二版）波利亚(Pólya)定理

波利亚(Pólya)定理6.1群论基础6.2置换群6.3伯恩赛德(Burnside)引理6.4Pólya定理6.5母函数型的Pólya定理6.6应用

6.1群论基础

6.1.1群的概念

定义6.1.1给定非空集合G

及定义在G上的二元运算“·”,若满足以下四个条件,则称集合G

在运算“·”下构成一个群,简称G

为一个群:

(1)封闭性:a,b∈G,则a·b∈G;

(2)结合律:(a·b)·c=a·(b·c);

(3)单位元:存在e∈G,对任意a∈G,有a·e=e·a=a;

(4)逆元素:对任意a∈G,存在b∈G,使得a·b=b·a=e,称b为a的逆元素,记为a-1.)

群的运算符“·”可略去,即a·b=ab.

群的运算并不要求满足交换律.如果某个群G中的代数运算满足交换律,则称G为交换群或Abel群.

群的元素可以是有限个,叫做有限群;也可以是无限个,叫做无限群.以|G|表示有限群中元素的个数,称为群的阶,那么当G为无限群时,可以认为|G|=∞.

【例6.1.1】偶数集,整数集Z,有理数集Q,实数集R,复数集C关于数的加法构成群,称为加法群.

因为数的运算对加法满足定义6.1.1的要求(1)和(2).其中的单位元为0,每个数a关于加法的逆元为:a-1=-a.

但是,关于数的乘法,这些集都不构成群.因为在偶数集中关于普通乘法不存在单位元.而在Z、Q、R、C中,虽然关于普通乘法有单位元1,但数0没有逆元.

6.1.2群的性质

定理6.1.1群具有以下性质:

(1)单位元e唯一;

(2)逆元唯一;

(3)满足消去律:即对a,b,c∈G,若ab=ac,则b=c;若ba=ca,则仍有b=c;

(4)a,b∈G,则(ab)-1=b-1a-1,更一般有(ab…c)-1=c-1…b-1a-1;

(5)若G是有限群,则对任意a∈G,必存在一个最小常数r,使ar=e,从而a-1=ar-1.r称为元素a的阶.

证性质(1)~(4)显然.只证明性质(5).

设|G|=n,由G的定义知:

由抽屉原理知,必存在整数m,k,满足1≤m<k≤n+1,使得am=ak

,即ak-m

=e,令r=k-m,则ar=e,即a.ar-1=e,所以a-1=ar-1.

6.1.3子群

定义6.1.2设G是群,H是G的子集,若H在G的原有运算下也构成一个群,则称H是G的子群.

【例6.1.9】任何群G至少有两个子群:

H1=G,H2={e|e∈G为单位元}.

【例6.1.10】对于乘法运算,H={1,-1}是G={1,-1,i,-i}的子群.

【例6.1.11】偶数加法群是整数Z的子群,Z是有理数加法群Q的子群,Q又是实数加法群R的子群,R是复数加法群C的子群;对乘法群而言,也有Q1

是R1的子群,R1

是C1的子群.

【例6.1.12】任选群G的一个元素a,设a的阶为r,则H={a,a2,…,ar-1,ar=e}是G的子群.这样的群H是由某个固定元素a的乘方组成的,称为循环群,或称H是由元素a生成的群,a叫做H的生成元.

定理6.1.2有限群的阶数必能被其子群的阶数整除.

6.2置换群

定义6.2.1有限集合S到自身的一个一一映射叫做一个置换例如:

说明

(1)将S中的元素ai写在上一行(顺序可任意),ai

的象写在ai

之下,同一列的两个元素的相对关系只要保持不变,即f(ai

)=aki,不同形式的写法都认为是同一个置换.如:

(2)置换就是将n个元的一种排列变为另一种排列.

(3)n元集S共有n!种不同的置换.

定义6.2.2两个置换p1、p2的乘积p1p2

定义为先做置换p1再做p2的结果.

例如,对于S={1,2,3,4},

一般来说,置换的乘法不满足交换律,即p1、p2≠p2p1,如上例中

求复合置换的一种技巧就是更改p2各列的前后次序,使其第一行的排列与前者p1第二行的排列相同,那么复合置换p1、p2的第一行就是p1的第一行,其第二行是p2的第二行.如上例:

定理6.2.1设Sn是n元集合上的所有置换构成的集合,则Sn关于置换的乘法构成群,称为n次对称群.

证不失一般性,设S={1,2,…,n}.由置换乘法的定义知,封闭性、结合律显然成立.其次,单位元为恒等置换

逆元素

【例6.2.1】将顶点分别为1,2,3的正三角形(见图6.2.1)绕重心O沿逆时针方向分别旋转0°、120°、240°,视其为顶点集{1,2,3}的置换,则有旋转对称映射图6.2.1S3与正三角形的对应示意图

另一类是反射对称映射,即将三角形123分别绕对称轴1A、2B、3C翻转180°得顶点集的另一类置换

【例6.2.2】(正方形对称群)考察使正多边形回到原来位置的所有可能的逆时针旋转和翻转动作,可以得到一个群,称为二面体群(参见图6.2.2).图6.2.2正方形的刚体变换与4次置换群

第一类:旋转对称关系

第二类:反射对称关系

定义6.2.3

n次对称群的子群称为(n次)置换群.

定义6.2.4设置换p将集合S中的a1换为a2,a2换为a3,……,ak-1换为ak,ak换为a1,称p为k阶循环置换(或轮换),记为(a1a2…ak)或(a1,a2,…,ak).

定义6.2.5设轮换p1=(a1,a2,…,ar),p2=(b1,b2,…,bs),且ai、bj互不相同,称p1与p2不相交.

定理6.2.2不相交的两个轮换p1、p2满足交换律,即p1p2=p2p1.

定理6.2.3任一置换都可以唯一分解为若干个互不相交的轮换之积

证对已知置换

【例6.2.3】将编号为1~52的卡片分为1~26、27~52两组,交错互相插入,则这样的交错插入重复8次后就会恢复到原来的卡片顺序.

证第一次插入相当对1~52作一次置换p=(1)(2,27,14,33,17,9,5,3)(4,28,40,46,49,25,13,7)(6,29,15,8,30,41,21,11)(10,31,16,34,43,22,37,19)(12,32,42,47,24,38,45,23)(18,35)(20,36,44,48,50,51,26,39)(52).其中最长的轮换为8阶,而k阶轮换重复k次后恢复原状,故结论成立.

所以,美国的研究人员认为,扑克牌洗7次最合适.

定义6.2.6称2阶轮换为对换(或换位).

定理6.2.4任何轮换都可以表示为若干个对换之积,但表示方式不唯一.

推论6.2.1一个置换总可以表为若干个对换的乘积.

定理6.2.5每个轮换的对换表示中,对换个数的奇偶性是唯一确定的.从而一个置换在它的不同的对换分解表示式中所含的对换个数的奇偶性是不变的.

定义6.2.7可以分解为奇数个对换之积的置换称为奇置换,可以分解为偶数个对换之积的置换称为偶置换

【例6.2.4】(十五子智力玩具)在一个4×4有方格的正方形盒子中放入15个可以滑动的小方格,而正方形盒子右下角为一空格.规定方格的移动规则是只准与空格相邻的方格移入空格,那么,无论怎么变动,不可能由状态(a)中的初始“布局”变换为状态(b)中的布局(见图6.2.3).图6.2.3十五子智力游戏

定理6.2.6当n≥2时,Sn中偶置换的全体构成一个n!/2阶的子群,称为交代群,记为An.

证先证An为群.

(1)封闭性:设p1,p2∈An,显然p1p2∈An,因为将二者分解的结果相乘,仍得偶数个对换的乘积.

(2)结合律:An⊂Sn,故An中元素自然满足结合律;

(3)单位元:因Sn中单位元e本身就是偶置换,故e∈An;

6.3.1共轭类

定义6.3.1若n次置换p可分解为互不相交的λ1个1轮换,λ2个2轮换,……,λn个n轮换,则称p属于(λ1,λ2,…,λn)类型,或1λ12λ2…nλn型.

类型1λ12λ2…nλn也称为格式.

显然

6.3伯恩赛德(Burnside)引理

定义6.3.2置换群G中属于同一类型(λ1,λ2,…,λn)的全体置换,叫做与该类型相应的共轭类,记为D(λ1,λ2,…,λn).

【例6.3.3】将S3按共轭情况分类的结果见表6.3.1

【例6.3.4】4次置换群G={(1)(2)(3)(4),(12),(34),(12)(34)},共有3个共轭类:

其中第2类含2个置换

定理6.3.1在n元对称群Sn中,

证设置换p为(λ1,λ2,…,λn)型,将p用轮换表示为

(λn≤1)将n个元素1,2,…,n按上格式填入λi≠0的轮换中,应有n!种填法.但对同一置换p,在计数时被重新统计.其原因有二:

(1)一个k轮换有k种不同表示形式;

(2)λk个k轮换间互换位置,有λk!种情形.

故p被重复统计λ1!λ2!…λk!1λ12λ2…nλn次,定理得证.

【例6.3.5】对称群S3共有3个共轭类,即

实际结果见例6.3.3.

6.3.2不动置换类

定义6.3.3设G是集合S={1,2,…,n}上的一个置换群,k∈S,p∈G,若p(k)=k,即置换p将k变为k,则称k为p的不动点.G中所有以k为不动点的全体置换,构成G的一个子集,称为k的不动置换类(k=1,2,…,n),记为Zk.

定理6.3.2群G中关于k的不动置换类Zk

构成一个子群.

证

(1)封闭性:若P1,P2∈Zk,则pi(k)=k,i=1,2,从而p1p2(k)=p2(p1(k))=p2(k)=k,即p1p2∈Zk.同理可证p2p1∈Zk;

(2)结合律:由于Zk⊂G,故结合律显然成立;

(3)单位元:显然e(k)=k,故e既是G的单位元,也是Zk的单位元;

(4)逆元素:若p∈Zk且p(k)=k,那么p的逆元一定存在,即p-1∈G而且必有p-1(k)=k,即p-1∈Zk.

由定义知,Zk是一个群.

另外,还知道|Zk|必整除|G|.

6.3.3等价类

定义6.3.4设G是集S={1,2,…,n}上的置换群,若存在i,j∈S,满足p(i)=j,则称i与j等价,记为i~j,S中与i等价的元素的全体记为Ei,称为元素i的“轨迹”或“踪迹”.Ei中元素的个数称为轨迹的长度．

不难看出,元素i与j的这种等价关系满足如下三条性质:

(1)反身性:即i~i;

(2)对称性:若i~j,则j~i;

(3)传递性:若i~j,j~k,则i~k.

定理6.3.3|Ek||Zk|=|G|,k=1,2,…,n

6.3.4Burnside引理

定理6.3.4设G是n元集S={1,2,…,n}上的置换群G={p1,p2,…,pr},令λk(p)表示置换p的k阶(不相交)轮换的个数,则G在S上诱导出的等价关系将S分为不同等价类的个数为

其中λ1(p)为置换p中不动点(即1阶轮换)的个数.图6.3.1正方形的2染色

【例6.3.11】制作5位数的十进制卡片(小于10000的数前面补0).其中某些不同的数可以合用一张卡片,例如数字0,1,6,8,9倒转180°后认为还是可读的,像18609倒转后读做60981.这样,共需多少张卡片即可表示所有的5位数?

【例6.3.12】用黄珠和蓝珠穿成长度为2的直线形珠串,如果颠倒一个珠串的两端而得到另一个珠串,则认为二者相同,求不同的珠串数.

解不考虑等价时,所有可能的珠串有{bb,by,yb,yy}=S,置换群G={p1=e,p2=颠倒置换}.即

所以,不同珠串数为

即bb,by,yy.

6.4Pólya定理

Burnside引理的前提是要列出各种涂色方案,方可利用置换的性质将方案分为不同的等价类进行计数.当被染色的对象的个数n或颜色数m较大时,问题就变得非常复杂,且工作量很大,因为首先各种染色方案共有mn

个,一个个枚举出来是比较困难的;其次还要找出在各种置换下互相等价的方案可能更加困难,故W.Burnside自1911年提出Burn-side引理以来,该引理在计数问题中未得到广泛应用.

问题设有n个对象,今用m种颜色对其染色,其中每个对象任涂一种颜色,问有多少种不同的染色方案.其中,对n个对象作某一置换,若其中一种染色方案变为另一种方案,则认为该两个方案是相同的,或者说是等价的.

从集合与置换的角度来描述这个问题则是:S是有n个元素的集合,Q是S上的置换群,C是m种颜色的集合,用C中的颜色对S中的元素染色,对每个元素任选一色染之,共有多少种不等价的方案?

两种方案称为等价:指存在q∈Q,将S中元素的一种染色方案变为另一种方案.

例如:q1有4个轮换因子,将每个轮换因子中的顶点染以某种颜色,由于每个轮换因子可选两色之一,故共得24=16种方案,它恰好对应CS中在不动置换p1作用下的λ1(p1)=16种方案,而且可以看出在恒等置换p1作用下,16种染色方案确实不等价.

同理,q2只有一个轮换因子,即4个元素涂同一种颜色,共有21=2种涂法(一般情况下,使用m种颜色,应为m种涂法),对应CS中在p2作用下不变的方案f1、f2.其它情形依此类推

总之,由上面的讨论,可以得到以下结论:

(1)λ1(pi)=2λ(qi),i=1,2,3,4.

(2)|G|=|Q|.

定理6.4.1(Pólya定理)设Q是n个对象的一个置换群,用m种颜色涂染这n个对象,一个对象涂任意一种颜色,则在Q作用下不等价的方案数为

【例6.4.1】用红、黄、蓝三色对等边三角形的顶点着色,共有多少种不同方案?解设针对S={1,2,3}的置换群为

所求不等价的方案数为

所有着色方案见图6.4.1.图6.4.1三角形顶点的3染色方案(互不等价)

若置换群为Q2={(1)(2)(3),(123),(132)},即只有旋转,没有翻转,则不等价的方案数

比在Q1作用下的着色方案多了一个,即此时除了图6.4.2的10种涂法外,还有一种如图6.4.3所示的涂法,它是图6.4.2中最后一种涂法翻转过来的情形.由于Q2不含相应于翻转的置换,故在Q2作用下,二者不等价.图6.4.2仅有旋转置换时增加的不等价方案

若改为用4种颜色染色,则

【例6.4.2】用两种颜色给正立方体的8个顶点着色,试问有多少种不同的方案.

解使正立方体重合的关于顶点的运动群是(参见图6.4.3):

(1)单位元(1)(2)(3)(4)(5)(6)(7)(8),格式为(1)8;

(2)绕xx'轴旋转±90°,可得两个置换分别为(1234)(5678)和(4321)(8765),格式为(4)2,同类的置换共有6个;

(3)绕xx'轴旋转180°,可得置换为(13)(24)(57)(68),格式为(2)4,同类的置换有3个;．

(4)绕yy'轴旋转180°,可得置换为(17)(26)(35)(48),格式为(2)4,同类的置换有6个;

(5)绕zz'轴旋转±120°,可得两个置换分别为(136)(475)(8)(2)和(631)(574)(2)(8),格式为(1)2(3)2,同类置换有8个.

由Pólya定理,不同的染色方案数为图6.4.3正方体8个顶点的置换示意

6.5母函数型的Pólya定理

母函数型的Pó方lya案定进理行也枚称举为.带权的Pólya定理,它主要用于带有限制条件的染色方案问题或对具体的方案进行枚举.

首先,考虑用4种颜色涂3个编号分别为1、2、3的球,设颜色为b(蓝)、g(绿)、r(红)、y(黄).为了“详细枚举”各种涂色方案,用bi表示第i号球涂蓝色,gi表示第i号球涂绿色,……,那么,用4种颜色染3个球的各种方案可表示如下:

右边的每一项都代表一种染色方案,且各种方案互不相同,即互不等价.例如b1r2g3表示1号球涂蓝色,2号球涂红色,3号球涂绿色;而b1r2b3则表示1、3号球涂蓝色,2号球涂红色.欲知总共有多少种不等价的方案,也就是统计上式右边有多少项.只要在等式右端令bi=gi=ri=yi=1(i=1,2,3)就可得染色方案总数L.为方便计算,从左端看,有

若只关心某方案用了哪些颜色,不关心具体对象染了什么颜色,即将各种方案按使用颜色情况“分类枚举”,或称“分类统计”.例如欲知道2个球染蓝色、1个球染绿色的方案有多少个,那么,展开多项式

下面考虑分组染色的方案数.问题来源于Pólya定理的推导过程.如上一节中用m种颜色对构成大正方形的4个相同的小正方形进行染色,大正方形的空间变换为置换q2={旋转180°},那么,只有当小正方形1和3同色,2和4同色时,才能保证在q2作用下,所染的方案保持不变.这实质上就是将不同的球先分组,同一组的球颜色相同,求不等价的染色方案数.

个用3种颜色b(蓝色)、r(红色)、y(黄色)染4个不同的球,将4个球分为2组,每组2个，要求同组的球同色(如1、3号球为第一组,2、4号球为第二组),各种方案的详细枚举情况如下:

【例6.5.1】用三种不同颜色的珠子穿成4个珠子的项链,共有多少不同的方案?

解如图6.5.1所示,使之重合的运动有关于圆环中心旋转±90°和±180°,以及关于xx'和yy'轴翻转180°.故有置换群G={p1,p2,…,p8},其中图6.5.1四珠项链的几何变换图6.5.2两蓝、一红一绿珠子组成的不等价的项链

【例6.5.2】由4颗红色的珠子嵌在正六面体的4个角,试问有多少种方案.图6.5.3正方体顶点两种颜色数相等的2染色

6.6应用

【例6.6.1】将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少种不同的放法.列出全部方案.又问每盒中有两个球的放法有多少种.

解这是一个典型的球分类相同的分配问题.即将4个球放入两个不同的盒子,但4个球既不是全相同,也不是全不同,而是分类相同.

又如将题目改为白球两个、黑球3个,则相应的置换群为

【例6.6.2】用红、黄、蓝三种颜色对正六边形的顶点进行着色,共有多少种不同的方案?其中正六边形可以绕几何中心旋转或沿其对称轴翻转.

解图6.6.1的正六边形可以分别绕其中心O逆时针旋转0°、60°、120°、180°、240°、300°以及过3对顶点、3个对称边的中点连线翻转,从而得置换群Q所含的置换如下:图6.6.1正六边形顶点的置换示意

【例6.6.3】3个布尔变量x1,x2,x3的布尔函数装置(见图6.6.2)有多少种不同的结构?图6.6.23个输入端的布尔装置

由此可得各种状态,即集合S的置换群Q为

求不同布尔函数装置的问题,相当于求服从群Q的变换的8个顶点a0,a1,a2,a3,a4,a5,a6,a7用两种颜色(相当于布尔函数的0、1状态)对之着色的方案数.故由Pólya定理,有

种方案.也就是说,三个变量的256个布尔函数中,只有80个是不等价的,其余的函数可通过改变输入端的顺序而得到.

【例6.6.4】用红、蓝两色给正立方体的六个面着色,可得多少种不同方案?

解将正方体的上、下、左、右、前、后6个面分别编号为1、6、4、2、3、5,使正立方体的面重合的刚体运动群有以下几种情况(参见图6.6.3):

(1)不动置换:即单位元素(1)(2)(3)(4)(5)(6),格式为(1)6;

(2)绕过(1)和(6)面中心的AB轴旋转±90°(图6.6.3(a)),对应置换为(1)(2345)(6),(1)(5432)(6),格式为(1)2(4)1.类似的面共有3对,故这种格式的置换共有6个;

(3)绕AB轴旋转180°的置换为(1)(24)(35)(6),格式为(1)2(2)2,同类的置换有3个;

(4)绕CD轴旋转180°(图6.6.3(b))的置换为(16)(25)(34),格式为(2)3,而正立方体对角线位置的平行的棱有6对,故同类置换有6个;

(5)绕对角线EF旋转±120°(图6.6.3(c))的置换分别为(346)(152)和(643)(251),格式都是(3)2.这样的对角线有4个,即同类置换有8个.

所以,不同的染色方案为图6.6.3