1、第六章 波利亚(Plya)定理第六章第六章 波利亚波利亚(Plya)(Plya)定理定理6.1 群论群论基础基础6.2 置换群置换群6.3 伯恩赛德伯恩赛德(Burnside)引理引理6.4 Plya定理定理6.5 母函数型的母函数型的 Plya定理定理 6.6 应用应用第六章 波利亚(Plya)定理6.1 群论基础群论基础6.1.1 群的概念群的概念 定义定义 6.1.1 给定非空集合G 及定义在G 上的二元运算“”,若满足以下四个条件,则称集合G 在运算“”下构成一个群,简称G 为一个群:第六章 波利亚(Plya)定理(1)封闭性:a,bG,则abG;(2)结合律:(ab)c=a(bc);
2、(3)单位元:存在eG,对任意aG,有ae=ea=a;(4)逆元素:对任意a G,存在bG,使得ab=ba=e,称b 为a 的逆元素,记为a-1.)群的运算符“”可略去,即ab=ab.群的运算并不要求满足交换律.如果某个群G 中的代数运算满足交换律,则称G 为交换交换群群或 Abel群群.群的元素可以是有限个,叫做有限群有限群;也可以是无限个,叫做无限群无限群.以|G|表示有限群中元素的个数,称为群的阶,那么当G 为无限群时,可以认为|G|=.第六章 波利亚(Plya)定理【例例 6.1.1】偶数集,整数集 Z,有理数集 Q,实数集 R,复数集C关于数的加法构成群,称为加法群.因为数的运算对加
3、法满足定义6.1.1的要求(1)和(2).其中的单位元为0,每个数a 关 于加法的逆元为:a-1=-a.但是,关于数的乘法,这些集都不构成群.因为在偶数集中关于普通乘法不存在单位元.而在 Z、Q、R、C中,虽然关于普通乘法有单位元1,但数0没有逆元.第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理6.1.2 群的性质群的性质 定理定理 6.1.1 群具有以下性质:(1)单位元e唯一;(2)逆元唯一;(3)满足消去律:即对a,b,cG,若ab=ac,则b=c;若ba=ca,则仍有b=c;(4)a,bG,则(ab)-1=b-1a-1,更一般有(abc)-1
4、=c-1b-1a-1;(5)若G 是有限群,则对任意aG,必存在一个最小常数r,使ar=e,从而a-1=ar-1.r 称为元素a 的阶.第六章 波利亚(Plya)定理证证 性质(1)(4)显然.只证明性质(5).设|G|=n,由G 的定义知:由抽屉原理知,必存在整数m,k,满足1mkn+1,使得am=ak,即ak-m=e,令r=k-m,则ar=e,即a.ar-1=e,所以a-1=ar-1.第六章 波利亚(Plya)定理6.1.3 子群子群 定义定义 6.1.2 设G 是群,H 是G 的子集,若 H 在G 的原有运算下也构成一个群,则称 H 是G 的子群.【例【例 6.1.9】任何群G 至少有两
5、个子群:H1=G,H2=e|eG 为单位元.【例【例 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 的子群.第六章 波利亚(Plya)定理【例【例 6.1.12】任选群G 的一个元素a,设a 的阶为r,则 H=a,a2,ar-1,ar=e是G 的子群.这样的群 H 是由某个固定元素a 的乘方组成的,称为循环群,或称 H 是 由元素a 生成的群,a 叫做H 的生成元生成元.定
6、理定理 6.1.2 有限群的阶数必能被其子群的阶数整除.第六章 波利亚(Plya)定理6.2 置置 换换 群群定义定义 6.2.1 有限集合S 到自身的一个一一映射叫做一个置换例如:第六章 波利亚(Plya)定理说明说明(1)将S 中的元素ai 写在上一行(顺序可任意),ai 的象写在ai 之下,同一列的两个 元素的相对关系只要保持不变,即f(ai)=aki,不同形式的写法都认为是同一个置换.如:(2)置换就是将n 个元的一种排列变为另一种排列.(3)n 元集S 共有n!种不同的置换.第六章 波利亚(Plya)定理定义定义 6.2.2 两个置换p1、p2 的乘积p1p2 定义为先做置换p1 再
7、做p2 的结果.例如,对于S=1,2,3,4,第六章 波利亚(Plya)定理一般来说,置换的乘法不满足交换律,即p1、p2p2p1,如上例中求复合置换的一种技巧就是更改p2各列的前后次序,使其第一行的排列与前者p1第 二行的排列相同,那么复合置换p1、p2的第一行就是p1 的第一行,其第二行是p2 的第二 行.如上例:第六章 波利亚(Plya)定理定理定理 6.2.1 设Sn 是n 元集合上的所有置换构成的集合,则Sn 关于置换的乘法构成 群,称为n 次对称群.证证 不失一般性,设S=1,2,n.由置换乘法的定义知,封闭性、结合律显然成 立.其次,单位元为恒等置换逆元素第六章 波利亚(Plya
8、)定理【例【例 6.2.1】将顶点分别为1,2,3的正三角形(见图6.2.1)绕重心O 沿逆时针方向分 别旋转0、120、240,视其为顶点集1,2,3的置换,则有旋转对称映射第六章 波利亚(Plya)定理图 6.2.1 S3 与正三角形的对应示意图第六章 波利亚(Plya)定理另一类是反射对称映射,即将三角形123分别绕对称轴1A、2B、3C 翻转180得顶点 集的另一类置换第六章 波利亚(Plya)定理【例【例 6.2.2】(正方形对称群)考察使正多边形回到原来位置的所有可能的逆时针旋转 和翻转动作,可以得到一个群,称为二面体群(参见图6.2.2).图 6.2.2 正方形的刚体变换与4次置
9、换群第六章 波利亚(Plya)定理第一类:旋转对称关系第六章 波利亚(Plya)定理第二类:反射对称关系第六章 波利亚(Plya)定理定义定义 6.2.3n 次对称群的子群称为(n 次)置换群.定义定义 6.2.4 设置换p 将集合S 中的a1 换为a2,a2 换为a3,ak-1换为ak,ak 换为a1,称p 为k 阶循环置换(或轮换),记为(a1a2ak)或(a1,a2,ak).第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理定义定义 6.2.5 设轮换p1=(a1,a2,ar),p2=(b1,b2,bs),且ai、bj 互不相 同,称p1 与p2 不相交.定理定理 6.2.2
10、不相交的两个轮换p1、p2 满足交换律,即p1p2=p2p1.第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理定理定理 6.2.3 任一置换都可以唯一分解为若干个互不相交的轮换之积证证 对已知置换第六章 波利亚(Plya)定理【例【例 6.2.3】将编号为152的卡片分为126、2752两组,交错互相插入,则这样 的交错插入重复8次后就会恢复到原来的卡片顺序.证证 第一次插入相当对152作一次置换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,
11、19)(12,32,42,47,24,38,45,23)(18,35)(20,36,44,48,50,51,26,39)(52).其中 最长的轮换为8阶,而k 阶轮换重复k 次后恢复原状,故结论成立.所以,美国的研究人员认为,扑克牌洗7次最合适.第六章 波利亚(Plya)定理定义定义 6.2.6 称2阶轮换为对换(或换位).定理定理 6.2.4 任何轮换都可以表示为若干个对换之积,但表示方式不唯一.第六章 波利亚(Plya)定理推论推论 6.2.1 一个置换总可以表为若干个对换的乘积.定理定理 6.2.5 每个轮换的对换表示中,对换个数的奇偶性是唯一确定的.从而一个置换 在它的不同的对换分解表
12、示式中所含的对换个数的奇偶性是不变的.定义定义 6.2.7 可以分解为奇数个对换之积的置换称为奇置换,可以分解为偶数个对换 之积的置换称为偶置换第六章 波利亚(Plya)定理【例【例 6.2.4】(十五子智力玩具十五子智力玩具)在一个44有方格的正方形盒子中放入15个可以滑动 的小方格,而正方形盒子右下角为一空格.规定方格的移动规则是只准与空格相邻的方格移 入空格,那么,无论怎么变动,不可能由状态(a)中的初始“布局”变换为状态(b)中的布局(见 图6.2.3).第六章 波利亚(Plya)定理图 6.2.3 十五子智力游戏第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理定理定理 6
13、.2.6当n2时,Sn 中偶置换的全体构成一个n!/2阶的子群,称为交代群,记为An.证证 先证An 为群.(1)封闭性:设p1,p2An,显然p1p2An,因为将二者分解的结果相乘,仍得偶数个对换的乘积.(2)结合律:AnSn,故An 中元素自然满足结合律;(3)单位元:因Sn 中单位元e本身就是偶置换,故eAn;第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理6.3.1 共轭类共轭类 定义定义 6.3.1 若n 次置换p 可分解为互不相交的1 个1轮换,2 个2轮换,n 个n 轮换,则称p 属于(1,2,n)类型,或 1122nn 型.类型1122
14、nn 也称为格式.显然6.3 伯恩赛德伯恩赛德(Burnside)引理引理第六章 波利亚(Plya)定理定义定义 6.3.2 置换群G 中属于同一类型(1,2,n)的全体置换,叫做与该类型相 应的共轭类,记为D(1,2,n).【例【例 6.3.3】将S3 按共轭情况分类的结果见表6.3.1第六章 波利亚(Plya)定理【例【例 6.3.4】4次置换群 G=(1)(2)(3)(4),(12),(34),(12)(34),共有3个 共轭类:其中第2类含2个置换第六章 波利亚(Plya)定理定理定理 6.3.1 在n 元对称群Sn 中,证证 设置换p 为(1,2,n)型,将p 用轮换表示为第六章 波
15、利亚(Plya)定理(n1)将n 个元素1,2,n 按上格式填入i0的轮换中,应有n!种填法.但对同一 置换p,在计数时被重新统计.其原因有二:(1)一个k 轮换有k 种不同表示形式;(2)k 个k 轮换间互换位置,有k!种情形.故p 被重复统计1!2!k!1122nn 次,定理得证.第六章 波利亚(Plya)定理【例【例 6.3.5】对称群S3 共有3个共轭类,即实际结果见例6.3.3.第六章 波利亚(Plya)定理6.3.2 不动置换类不动置换类 定义定义6.3.3 设G 是集合S=1,2,n上的一个置换群,kS,pG,若p(k)=k,即置换p 将k 变为k,则称k 为p 的不动点.G 中
16、所有以k 为不动点的全体置换,构成 G 的一个子集,称为k 的不动置换类不动置换类(k=1,2,n),记为Zk.第六章 波利亚(Plya)定理定理定理 6.3.2 群G 中关于k 的不动置换类Zk 构成一个子群.证证(1)封闭性:若P1,P2Zk,则pi(k)=k,i=1,2,从而p1p2(k)=p2(p1(k)=p2(k)=k,即p1p2Zk.同理可证p2p1Zk;(2)结合律:由于ZkG,故结合律显然成立;(3)单位元:显然e(k)=k,故e既是G 的单位元,也是Zk 的单位元;(4)逆元素:若pZk 且p(k)=k,那么p 的逆元一定存在,即p-1 G 而且必有 p-1(k)=k,即p-
17、1Zk.由定义知,Zk 是一个群.另外,还知道|Zk|必整除|G|.第六章 波利亚(Plya)定理6.3.3 等价类等价类 定义定义 6.3.4 设G 是集S=1,2,n上的置换群,若存在i,jS,满足p(i)=j,则称i与j等价,记为ij,S 中与i等价的元素的全体记为Ei,称为元素i的“轨迹”或“踪迹”.Ei 中元素的个数称为轨迹的长度不难看出,元素i与j的这种等价关系满足如下三条性质:(1)反身性:即ii;(2)对称性:若ij,则ji;(3)传递性:若ij,jk,则ik.第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理定理定理 6.3.3|Ek|Zk|=|G|,k=1,2,n
18、第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理6.3.4 Burnside引理引理 定理定理 6.3.4 设G 是n 元集S=1,2,n上的置换群G=p1,p2,pr,令 k(p)表示置换p 的k 阶(不相交)轮换的个数,则G 在S 上诱导出的等价关系将S 分为不 同等价类的个数为其中1(p)为置换p 中不动点(即1阶轮换)的个数.第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理图 6.3.1 正方形的2染色第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理【例【例 6.3.11】制作5位数的十进制卡片(小于10000的数前面补
19、0).其中某些不同的 数可以合用一张卡片,例如数字0,1,6,8,9倒转180后认为还是可读的,像18609倒转 后读做60981.这样,共需多少张卡片即可表示所有的5位数?第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理【例【例 6.3.12】用黄珠和蓝珠穿成长度为2的直线形珠串,如果颠倒一个珠串的两端而 得到另一个珠串,则认为二者相同,求不同的珠串数.解解 不考虑等价时,所有可能的珠串有bb,by,yb,yy=S,置换群G=p1=e,p2=颠倒置换.即所以,不同珠串数为即bb,by,yy.第六章 波利亚(Plya)定理
20、第六章 波利亚(Plya)定理6.4 Plya 定理定理Burnside引理的前提是要列出各种涂色方案,方可利用置换的性质将方案分为不同的 等价类进行计数.当被染色的对象的个数n 或颜色数m 较大时,问题就变得非常复杂,且 工作量很大,因为首先各种染色方案共有 mn 个,一个个枚举出来是比较困难的;其次还 要找出在各种置换下互相等价的方案可能更加困难,故 W.Burnside自1911年提出 Burn-side引理以来,该引理在计数问题中未得到广泛应用.第六章 波利亚(Plya)定理问题问题 设有n 个对象,今用m 种颜色对其染色,其中每个对象任涂一种颜色,问有多 少种不同的染色方案.其中,对
21、n 个对象作某一置换,若其中一种染色方案变为另一种方 案,则认为该两个方案是相同的,或者说是等价的.从集合与置换的角度来描述这个问题则是:S 是有n 个元素的集合,Q 是S 上的置换 群,C 是m 种颜色的集合,用C 中的颜色对S 中的元素染色,对每个元素任选一色染之,共有多少种不等价的方案?两种方案称为等价:指存在qQ,将S 中元素的一种染色方案变为另一种方案.第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理例如:q1 有4个轮换因子,将每个轮换因子中的顶点染以某种颜色,由于每个轮换因 子可选两 色 之 一,故 共 得 24=16 种 方 案,它 恰
22、 好 对 应 CS 中 在 不 动 置 换p1 作 用 下 的 1(p1)=16种方案,而且可以看出在恒等置换p1 作用下,16种染色方案确实不等价.同理,q2 只有一个轮换因子,即4个元素涂同一种颜色,共有21=2种涂法(一般情况 下,使用m 种颜色,应为m 种涂法),对应CS 中在p2 作用下不变的方案f1、f2.其它情 形依此类推第六章 波利亚(Plya)定理总之,由上面的讨论,可以得到以下结论:(1)1(pi)=2(qi),i=1,2,3,4.(2)|G|=|Q|.定理定理 6.4.1(Plya定理定理)设Q 是n 个对象的一个置换群,用 m 种颜色涂染这n 个对 象,一个对象涂任意一
23、种颜色,则在Q 作用下不等价的方案数为第六章 波利亚(Plya)定理【例【例 6.4.1】用红、黄、蓝三色对等边三角形的顶点着色,共有多少种不同方案?解 设针对S=1,2,3的置换群为所求不等价的方案数为所有着色方案见图6.4.1.第六章 波利亚(Plya)定理图 6.4.1 三角形顶点的3染色方案(互不等价)第六章 波利亚(Plya)定理若置换群为 Q2=(1)(2)(3),(123),(132),即只有旋转,没有翻转,则不等价 的方案数比在Q1 作用下的着色方案多了一个,即此时除了图6.4.2的10种涂法外,还有一种如图 6.4.3所示的涂法,它是图6.4.2中最后一种涂法翻转过来的情形.
24、由于Q2 不含相应于翻转 的置换,故在Q2 作用下,二者不等价.第六章 波利亚(Plya)定理图 6.4.2 仅有旋转置换时增加的不等价方案第六章 波利亚(Plya)定理若改为用4种颜色染色,则第六章 波利亚(Plya)定理【例【例 6.4.2】用两种颜色给正立方体的8个顶点着色,试问有多少种不同的方案.解解 使正立方体重合的关于顶点的运动群是(参见图6.4.3):(1)单位元(1)(2)(3)(4)(5)(6)(7)(8),格式为(1)8;(2)绕 xx 轴 旋 转 90,可 得 两 个 置 换 分 别 为(1234)(5678)和(4 3 2 1)(8 7 6 5),格式为(4)2,同类的
25、置换共有6个;(3)绕xx轴旋转180,可得置换为(13)(24)(57)(68),格式为(2)4,同类的置换 有3个;第六章 波利亚(Plya)定理(4)绕yy轴旋转180,可得置换为(17)(26)(35)(48),格式为(2)4,同类的置换 有6个;(5)绕 zz轴 旋 转 120,可 得 两 个 置 换 分 别 为(136)(475)(8)(2)和(6 3 1)(5 7 4)(2)(8),格式为(1)2(3)2,同类置换有8个.由 Plya定理,不同的染色方案数为第六章 波利亚(Plya)定理图 6.4.3 正方体8个顶点的置换示意第六章 波利亚(Plya)定理6.5 母函数型的母函数
26、型的Plya 定理定理母函数型的P方lya案定进理行也枚称举为.带权的 Plya定理,它主要用于带有限制条件的染色方案问题或对具体的方案进行枚举.第六章 波利亚(Plya)定理首先,考虑用4种颜色涂3个编号分别为1、2、3的球,设颜色为b(蓝)、g(绿)、r(红)、y(黄).为了“详细枚举”各种涂色方案,用bi 表示第i号球涂蓝色,gi 表示第i号 球涂绿色,那么,用4种颜色染3个球的各种方案可表示如下:第六章 波利亚(Plya)定理右边的每一项都代表一种染色方案,且各种方案互不相同,即互不等价.例如b1r2g3 表示1号球涂蓝色,2号球涂红色,3号球涂绿色;而b1r2b3 则表示1、3号球涂
27、蓝色,2号 球涂红色.欲知总共有多少种不等价的方案,也就是统计上式右边有多少项.只要在等式右 端令bi=gi=ri=yi=1(i=1,2,3)就可得染色方案总数L.为方便计算,从左端看,有第六章 波利亚(Plya)定理若只关心某方案用了哪些颜色,不关心具体对象染了什么颜色,即将各种方案按使用 颜色情况“分类枚举”,或称“分类统计”.例如欲知道2个球染蓝色、1个球染绿色的方案有多少个,那么,展开多项式第六章 波利亚(Plya)定理下面考虑分组染色的方案数.问题来源于 Plya定理的推导过程.如上一节中用 m 种 颜色 对 构 成 大 正 方 形 的 4 个 相 同 的 小 正 方 形 进 行 染
28、 色,大 正 方 形 的 空 间 变 换 为 置 换 q2=旋转180,那么,只有当小正方形1和3同色,2和4同色时,才能保证在q2 作用 下,所染的方案保持不变.这实质上就是将不同的球先分组,同一组的球颜色相同,求不等 价的染色方案数.第六章 波利亚(Plya)定理个 用3种颜色b(蓝色)、r(红色)、y(黄色)染4个不同的球,将4个球分为2组,每组2个，要求同组的球同色(如1、3号球为第一组,2、4号球为第二组),各种方案的详细枚举情况如下:第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理
29、第六章 波利亚(Plya)定理【例【例 6.5.1】用三种不同颜色的珠子穿成4个珠子的项链,共有多少不同的方案?解解 如图6.5.1所示,使之重合的运动有关于圆环中心旋转90和180,以及关于 xx和yy轴翻转180.故有置换群G=p1,p2,p8,其中第六章 波利亚(Plya)定理图 6.5.1 四珠项链的几何变换第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理图 6.5.2 两蓝、一红一绿珠子组成的不等价的项链第六章 波利亚(Plya)定理【例【例 6.5.2】由4颗红色的珠子嵌在正六面体的4个角,试问有多少种方案.第六章 波利亚(Plya)定理图 6.5.3 正方体顶点两种颜
30、色数相等的2染色第六章 波利亚(Plya)定理6.6 应应 用用【例【例 6.6.1】将两个相同的白球和两个相同的黑球放入两个不同的盒子里,问有多少 种不同的放法.列出全部方案.又问每盒中有两个球的放法有多少种.解解 这是一个典型的球分类相同的分配问题.即将4个球放入两个不同的盒子,但4 个球既不是全相同,也不是全不同,而是分类相同.第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理又如将题目改为白球两个、黑球3个,则相应的置换群为第六章 波利亚(Plya)定理【例【例 6.6.2】用红、黄、蓝三种颜色对正六边形的顶点进行着色,共有多少种不同的方 案?其
31、中正六边形可以绕几何中心旋转或沿其对称轴翻转.解解 图6.6.1的正六边形可以分别绕其中心O 逆时针旋转0、60、120、180、240、300以及过 3 对顶点、3个对称边的中点连线翻转,从而得置换群Q 所含的置换如下:第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理图 6.6.1 正六边形顶点的置换示意第六章 波利亚(Plya)定理【例【例 6.6.3】3个布尔变量x1,x2,x3 的布尔函数装置(见图6.6.2)有多少种不同的 结构?图 6.6.2 3个输入端的布尔装置第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理由此可得各种状态,
32、即集合S 的置换群Q 为第六章 波利亚(Plya)定理求不同布尔函数装置的问题,相当于求服从群 Q 的变换的8个顶点a0,a1,a2,a3,a4,a5,a6,a7 用两种颜色(相当于布尔函数的0、1状态)对之着色的方案数.故由 Plya 定理,有种方案.也就是说,三个变量的256个布尔函数中,只有80个是不等价的,其余的函数可 通过改变输入端的顺序而得到.第六章 波利亚(Plya)定理【例【例 6.6.4】用红、蓝两色给正立方体的六个面着色,可得多少种不同方案?解解 将正方体的上、下、左、右、前、后6个面分别编号为1、6、4、2、3、5,使正立方 体的面重合的刚体运动群有以下几种情况(参见图6
33、.6.3):(1)不动置换:即单位元素(1)(2)(3)(4)(5)(6),格式为(1)6;(2)绕 过(1)和(6)面 中 心 的 AB 轴 旋 转 90(图 6.6.3(a),对 应 置 换 为(1)(2 3 4 5)(6),(1)(5432)(6),格式为(1)2(4)1.类似的面共有3对,故这种格式 的置换共有6个;第六章 波利亚(Plya)定理(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对,
34、故同类置换有6个;(5)绕对角线EF 旋转120(图6.6.3(c)的置换分别为(346)(152)和(643)(251),格式都是(3)2.这样的对角线有4个,即同类置换有8个.第六章 波利亚(Plya)定理所以,不同的染色方案为第六章 波利亚(Plya)定理图 6.6.3 正方体6个面的置换示意第六章 波利亚(Plya)定理【例【例 6.6.5】骰子的六个面分别为1点,2点,6点,问有多少种不同的方案.解解解法一解法一 用 Burnside引理求解:问题相当于对正六面体的6个面,用6种颜色对其染 色,要求各面的颜色都不一样,求不同的方案数.第六章 波利亚(Plya)定理6个面用6种颜色涂染
35、,各面颜色不同,应有6!种方案.但其中经旋转变换而重合的 两个方案只能算1种.由前面的例子已知关于正立方体的6个面的旋转运动群 Q 共有24 个置换q,从而相应于所有方案集合CS 的置换群G 也有24个置换p,观察这6!种方案 在G 的作用下的置换关系:设6!种方案为f1,f2,f6!,则(1)恒等置换:p1=(f1)(f2)(f6!),故1(p1)=6!;第六章 波利亚(Plya)定理(2)由于6个面的颜色均不相同,故在其它23个置换p2p24的作用下,没有一种方 案fi 能保持不变,即由 Burnside引理知,不同的方案数为第六章 波利亚(Plya)定理解法二解法二 用 Plya定理和容
36、斥原理求解:由例 6.6.4 知用m 种颜色对正六面体的6个面染色,可得不同的方案数,设为nm,则有所以n1=1,n2=10,n3=57,n4=240,n5=800,n6=2226.第六章 波利亚(Plya)定理再考虑用i(1im)种颜色对正六面体的6个面进行染色所得到的所有不同的方案 中,去掉所用颜色少于i的方案,剩下的就是恰好使用i种颜色的不同方案.设其有li 个,那么有第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理【例【例 6.6.6】三个顶点的不同形的简单图共有多少种?解解 对于三个顶点的简单图,设其顶点集为V=v1,v2,v3,相应的置换群及其轮 换指标分别为第六章 波
37、利亚(Plya)定理从P(x,y)可知,对三角形的边着色,其中三条边都着以颜色x 的方案有1个;同理,两条边,或一条边,或无一边着x 色的方案各为1个.把着以颜色y 的边消除即得4个具 有三个顶点的简单图(见图6.6.4)图 6.6.4 具有三个顶点的不同形的简单图第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理图 6.6.5 具有四个顶点6条边的简单图第六章 波利亚(Plya)定理图 6.6.6 由顶点置换(v1,v2)(v3)(v4)导致的边的置换第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理图 6.6.7 四个顶点的所有简单图第六章 波利亚(Plya)定理图 6.6.8 仅有一条边的四顶点简单图第六章 波利亚(Plya)定理【例【例 6.6.8】四个顶点的(不含圈的)有向图的不同图像有多少种?第六章 波利亚(Plya)定理第六章 波利亚(Plya)定理图 6.6.9 具有4个顶点12条边的有向图第六章 波利亚(Plya)定理图 6.6.10 四个顶点两条边的不等价的有向图第六章 波利亚(Plya)定理图 6.6.11 与图6.6.10(c)等价的四个顶点两条边的有向图
