组合数学(28)

1、1第八章第八章 Polya计数法计数法14.3 Polya计数公式计数公式(二二) 上次课我们通过研究置换中的上次课我们通过研究置换中的循环因子分循环因子分解、型、单项式、循环指数解、型、单项式、循环指数, , 解决不等价的着色解决不等价的着色计数问题。但定理的应用是在已知计数问题。但定理的应用是在已知C是是k种颜色种颜色的前提下。现在我们解决当使用颜色次数的前提下。现在我们解决当使用颜色次数指定指定时时不等价的着色数量。不等价的着色数量。 设集合设集合X = 1,2,3,n中各颜色的元素的中各颜色的元素的2个数是指定的，个数是指定的，C是由集合是由集合X的所有着色构成的的所有着色构成的 集合

2、。对集合。对X中的每个置换中的每个置换 f 与与C中的每种着中的每种着色色c , 一种特定的颜色出现在一种特定的颜色出现在c 中的次数与该中的次数与该颜色出现在颜色出现在 f *c 中的次数相同。换句话说：对中的次数相同。换句话说：对X中的对象与其颜色一起进行置换并不改变各中的对象与其颜色一起进行置换并不改变各种颜色的数目。就是说种颜色的数目。就是说X的任意置换群都可作的任意置换群都可作为着色集为着色集C中的一个置换群。中的一个置换群。 3例：例： (10阶二面体群阶二面体群) 对正五边形的顶点着三点对正五边形的顶点着三点 红色两点蓝色，有多少不等价的着色数量？红色两点蓝色，有多少不等价的着色

3、数量？解：从解：从5个点中任意选择个点中任意选择3点着红色，其余的着蓝点着红色，其余的着蓝色，有组合数求法共有：色，有组合数求法共有：C(5, 3) =10种。用种。用D5 表示旋转和翻转置换群，除了表示旋转和翻转置换群，除了旋转旋转0保持着色不变，其他保持着色不变，其他旋转都不行。右图的翻转可以旋转都不行。右图的翻转可以1432514 可以保持着色不变，下图一样，选择其他顺可以保持着色不变，下图一样，选择其他顺 序着红、蓝两种色都无法保持沿序着红、蓝两种色都无法保持沿1点中垂线点中垂线翻转后着色不变。无论选择哪点作中垂线，该翻转后着色不变。无论选择哪点作中垂线，该点必须着红色，其余两红两蓝四

4、点必须以中垂点必须着红色，其余两红两蓝四点必须以中垂线对称着同一颜色。线对称着同一颜色。 根据前面例题求过的用根据前面例题求过的用D5的循环因子分解和上面的分析的循环因子分解和上面的分析结果，列出下表：结果，列出下表：1432515置置 换换 循环的因式分解循环的因式分解 不变的着色数不变的着色数1 。2 。3 。4 。5 10 1 2 3 4 5 0 1 3 5 2 4 0 1 4 2 5 3 0 1 5 4 3 2 0 1 。2 5 。3 4 2 1 3 。2 。4 5 2 1 5 。3 。2 4 2 1 2 。3 5 。4 2 1 4 。2 3 。5 2051525354512345蓝色

5、的点是中垂线的顶点蓝色的点是中垂线的顶点6注意：沿中垂线翻转时，翻转的型都有注意：沿中垂线翻转时，翻转的型都有(1 2 0 0) 即有一个即有一个顶点顶点位置没有改变；我们必须对位置没有改变；我们必须对两个两个2-循环的每一个着同一种颜色，这样就有循环的每一个着同一种颜色，这样就有两个不等价的着色出现。应用定理两个不等价的着色出现。应用定理14.2.3得不得不等价的着色方案数为：等价的着色方案数为：它们是：两个连续的蓝色顶点或者两个不连续的它们是：两个连续的蓝色顶点或者两个不连续的蓝色顶点。蓝色顶点。21020102.20.010)(1),(GffCGCGN7 为了用为了用Burnside定理

6、来求各颜色出现的次数定理来求各颜色出现的次数 被被指定时指定时的不同着色数量的不同着色数量,我们必须能够求我们必须能够求出置换保持着色不变的着色数。出置换保持着色不变的着色数。 令令 f 是含有是含有n个元素的集合个元素的集合X的一个置换。的一个置换。假设置换假设置换 f 的型是：的型是： type( f ) = (e1, e2 ,. en),置换置换 f 的单项式为：的单项式为： neneeezzzzfmon.)(3213218那么在置换那么在置换 f 的循环因子分解中有的循环因子分解中有 e1个个1阶循环，阶循环， e2个个2阶循环阶循环. en个个n阶循环。为了讨论方阶循环。为了讨论方便

7、，我们就设仅有红色和蓝色两中颜色。便，我们就设仅有红色和蓝色两中颜色。 令令Cp,q表示所有表示所有p个元素着红色和个元素着红色和q = n- p个元个元素着蓝色的素着蓝色的X的着色集合。的着色集合。Cp,q中的一种着色在中的一种着色在置换置换 f 的作用下保持不变的充要条件是的作用下保持不变的充要条件是f 的的循环循环因子分解因子分解中的每个元素的中的每个元素的颜色相同颜色相同。因此，为。因此，为求求Cp,q在置换在置换 f 的作用下保持不变的的作用下保持不变的9着色着色数，我们可以认为是对循环指定红色元素数，我们可以认为是对循环指定红色元素 的个数为的个数为p( 从而着从而着指定为蓝色元素

8、的个数指定为蓝色元素的个数为为q = n - p)。假定。假定指定红色的指定红色的1-阶循环有阶循环有t1个，个，指定红色的指定红色的2-阶循环有阶循环有t2个，个，.，指定红色指定红色的的n-阶循环有阶循环有tn个。而我们假设红色元素个数是个。而我们假设红色元素个数是p，必然有下关系成立：必然有下关系成立： p = 1t1+2t2+ 3t3+ . +ntn其中其中 t1,t2,t3, . ,tn满足关系满足关系10 0 t1e1, 0t2e2 , . 0tnen 于是，在于是，在 f 的作用下使的作用下使Cp,q中着色保持不中着色保持不变的着色数变的着色数| Cp,q( f )|等于不等式的

9、解的个数。等于不等式的解的个数。 现在将红色看成变量现在将红色看成变量r，蓝色看成变量，蓝色看成变量b。对对f 的单项式作代数变换：的单项式作代数变换： z1= r+b, z2= r2+b2, z3= r3+b3,. zn= rn+bn而得到而得到 nnenneeeneebrbrbrzzz).()()(.2121222111 由于置换群由于置换群G的的循环指数循环指数是是G中的置换中的置换 f 的的 单项式的平均值。因此，由单项式的平均值。因此，由P358定理定理14.2.3，Cp,q中不等价的着色数量等于对中不等价的着色数量等于对G的的循环指数循环指数做做代换代换 zi= ri+bi 而得到

10、的表达式：而得到的表达式：),(),.,(22brPbrbrbrPnnG 中中 rpbq 的的系数系数。这意味作上式是当。这意味作上式是当Cp,q中用各中用各种颜色着色的元素个数为指定时，关于不等价种颜色着色的元素个数为指定时，关于不等价着色数的一个二元变量着色数的一个二元变量r,b的生成函数。的生成函数。12下面我们给出下面我们给出Polya定理，它的推导、应用已经定理，它的推导、应用已经 成为本章的主要目的。成为本章的主要目的。定理定理14.3.3 设设X 是一个元素集合是一个元素集合，G是是X的一个的一个置换群，置换群，u1, u2,. uk 是是k种颜色的一个集合，种颜色的一个集合，C

11、是是X的任意着色集并且的任意着色集并且G为为C上的一个置换群，上的一个置换群，那么，根据各个颜色的数目，那么，根据各个颜色的数目， C的不等价着色的不等价着色数的生成函数是：数的生成函数是： 由循环指数由循环指数 PG (z1, z2 , zn) 通过做变量代换：通过做变量代换：13 而得到的表达式：而得到的表达式：),.,2, 1(.321njuuuuzjkjjjj).,.,.,.(12211nknkkGuuuuuuP 换而言之换而言之, 上面表达式的展开式中：上面表达式的展开式中：项kpkpppuuuu.321321 的系数等于集合的系数等于集合X中的中的 p1个元素着颜色个元素着颜色u1

12、， p2个元素着颜色个元素着颜色u2，, pk个元素着颜色个元素着颜色uk，的的C中不等价着色总数。中不等价着色总数。14 例：分别用例：分别用2种颜色和种颜色和3种颜色对一个正方形的种颜色对一个正方形的 顶点着色，分别求它们不等价着色的生成顶点着色，分别求它们不等价着色的生成函数。函数。解：由上次课的计算可知，正方形的顶点对称解：由上次课的计算可知，正方形的顶点对称群群D4的循环指数为：的循环指数为：)232(811),(1221221441543215432154321zzzzzzzzzzGzzzzzPGfeeeeeG15(1)设两种颜色为设两种颜色为 r 与与 b , 则二元生成函数为：

13、则二元生成函数为：43223443223422224444433222)881688(81)(2)(3)(2)(81),(4brbbrbrrbrbbrbrrbrbrbrbrbrbrbrbrbrPD于是于是, 不等价的着色数是各个项系数的和，不等价的着色数是各个项系数的和，等于等于6其中，全部顶点着其中，全部顶点着红色红色或者或者蓝色蓝色的各一种；的各一种；三三红一蓝红一蓝和和三蓝一红三蓝一红各一种；各一种；两红两蓝两种两红两蓝两种。16 (2)设三种颜色为设三种颜色为 r, b与与g , 则三元生成函数为：则三元生成函数为：利用第五章利用第五章P91“多项式定理多项式定理” ，我们总能够将，我

14、们总能够将上式展开后求得各个单项式的系数；例如：上式展开后求得各个单项式的系数；例如： 项项 r b2g 的系数是：的系数是：)(2)( 3)(2)(81),(22222244444443332224gbrgbrgbrgbrgbrgbrgbrgbrgbrPD2)40012(8117就是说存在一红、两蓝、一绿的顶点着色，共就是说存在一红、两蓝、一绿的顶点着色，共 有不等价的两种。总不等价的着色总数为：有不等价的两种。总不等价的着色总数为：)54(101),(2211155154321zzzzzzzzzPG例例:分别用分别用2种颜色和种颜色和3种颜色对一个正五边形的顶种颜色对一个正五边形的顶点着色

15、，分别求它们不等价着色的生成函数。点着色，分别求它们不等价着色的生成函数。解：由上次课的计算可知，正五边形的顶点对称解：由上次课的计算可知，正五边形的顶点对称群群D5的循环指数为：的循环指数为：;32)3,3,3(5DP18 这个循环指数中没有这个循环指数中没有z1和和z3出现，这是因为出现，这是因为 D4中的置换在其循环因子分解中均无中的置换在其循环因子分解中均无3-循循环和环和4-循环。循环。 (1)设两种颜色为设两种颜色为 r 与与 b , 则二元生成函数为：则二元生成函数为：543223452225555544332222)(5)(4)(101),(4brbbrbrbrrbrbrbrb

16、rbrbrbrbrbrPD19不等的着色总数为系数之和：不等的着色总数为系数之和：1+1+2+2+1+1=8。 (2)设三种颜色为设三种颜色为 r, b与与g , 则三元生成函数为则三元生成函数为:种不等价着色总数为39)335343 (101)( 5)( 4)(101),(2522255555554443332225gbrgbrgbrgbrgbrgbrgbrgbrgbrPD20例例:有三种不同颜色的珠子，用它们装成四粒珠有三种不同颜色的珠子，用它们装成四粒珠 子的项链，子的项链， 问有哪些方案？问有哪些方案？解解:不难写出四边形的不难写出四边形的4个顶点个顶点v1, v2, v3, v4所对

17、应所对应的二面体群的二面体群G的元素为的元素为: (v1)(v2)(v3)(v4); (v2)(v4)(v1, v3); (v1, v2, v3, v4); (v1)(v3)(v2 , v4); (v1, v3)(v2, v4); (v1, v4)(v2, v3); (v1, v2)(v3, v4); (v4, v3, v2, v1) 。21其中其中, 格式为格式为(1)4的的1个，个， (4)1的的2个，个， (2)2的的3个，个， (1)2(2)的的2个。个。 根据根据Polya定理，定理， 不同方案不同方案数为数为: 具体方案是具体方案是:P=(b+g+r)4+2(b4+g4+r4)+3

18、(b2+g2+r2)2 +2(b2+g2+r2)(b+g+r)2)/82183233323224L22=b4+r4+g4+b3r+b3g+br3+r3g+bg3+rg3 +2b2r2+2b2g2+2r2g2+2b2rg+2br2g+2brg2 其中其中b2rg的系数为的系数为2，故知由两蓝、，故知由两蓝、 一红、一绿四一红、一绿四颗珠子组成的方案有颗珠子组成的方案有2种，种， 即即红红、 绿绿、 蓝蓝、 蓝蓝及及红红、 蓝蓝、 绿绿、 蓝蓝,再换蓝珠的位置会重复。再换蓝珠的位置会重复。 上式中各单项式中上式中各单项式中b、r、g的的幂是所用各种颜幂是所用各种颜色珠子的数量，各单项式的系数就是这

19、种组合色珠子的数量，各单项式的系数就是这种组合的方案数。的方案数。23例例(立方体的顶点与面的着色立方体的顶点与面的着色)用指定颜色对一个用指定颜色对一个 立方体的顶点与面进行着色，求立方体的立方体的顶点与面进行着色，求立方体的对称群和不等价的着色数对称群和不等价的着色数。 解解:一个立方体的对称共有一个立方体的对称共有24种，它们属于四种种，它们属于四种不同类型的旋转：不同类型的旋转：1)平面恒等旋转平面恒等旋转(1个个)2)绕绕3对垂直对立面中心旋转对垂直对立面中心旋转14235624 a)90度（度（3个）个） b)180度（度（3个）个） c)270度（度（3个）个）3)绕绕对边中点连

20、线对边中点连线旋转旋转180度（度（6个，有个，有6根连线）根连线）4)绕绕对角点连线对角点连线旋转旋转 a)120度（度（4个）个） b)240度（度（4个）个）14235625立方体对称的总计数立方体对称的总计数是：是：24个；我们把每类对称个；我们把每类对称 看成是看成是8个点个点(6个顶点和个顶点和2个对称轴的端点个对称轴的端点)的的置换和置换和6个面的置换，下表列出了各类情况：个面的置换，下表列出了各类情况：对称类 个 数 顶 点 类面 类 1)1(8,0,0,0,0,0,0,0,0)(6,0,0,0,0,0,0) 2)a)3(0,0,0,2,0,0,0,0,0)(2,0,0,1,0

21、,0,0) 2)b)3(0,4,0,0,0,0,0,0,0)(2,2,0,0,0,0,0) 2)c)3(0,0,0,2,0,0,0,0,0)(2,0,0,1,0,0,0) 3)6(0,4,0,0,0,0,0,0,0)(0,3,0,0,0,0,0) 4)a)4(2,0,2,0,0,0,0,0,0)(0,0,2,0,0,0,0) 4)b)4(2,0,2,0,0,0,0,0,0)(0,0,2,0,0,0,0)26 由上表我们看出立方体的由上表我们看出立方体的顶点顶点对称群对称群GC的的 循环指数为循环指数为:)896(241),.,(23214224818321zzzzzzzzzPCG立方体的立方体

22、的面面对称群对称群GF的循环指数为的循环指数为:)8636(241),.,(23322221422616321zzzzzzzzzzzPFG 用红色和蓝色对立方体的顶点着色，不等用红色和蓝色对立方体的顶点着色，不等价着色的生成函数为价着色的生成函数为:27关于立方体面的生成函数为：关于立方体面的生成函数为：656253443526782332422244888332233733)()( 8)(9)(6)(241),.,(brbbrbrbrbrbrbrrbrbrbrbrbrbrbrbrbrPCG)(8)(6)()(3)()(6)(241),.,(23332222224426663322brbrbr

23、brbrbrbrbrbrbrbrPFG28 由上面两式的系数我们可以得到立方体关由上面两式的系数我们可以得到立方体关于顶点的不等价着色总数是：于顶点的不等价着色总数是：23；关于面的不；关于面的不等价着色总数是等价着色总数是10。 如果我们用如果我们用k种颜色去对顶点着色，则：种颜色去对顶点着色，则：不价的顶点着色数是：不价的顶点着色数是：6542332456663322222),.,(brbbrbrbrbrrbrbrbrbrPFG29不等价的面着色数是：不等价的面着色数是：)617(241)896(241),.,(24822428kkkkkkkkkkkkPCG)8123(241)8636(2

24、41),.,(2346232226kkkkkkkkkkkkkkkPFG30例例:把四颗红色的珠子嵌在正六面体的四个角，把四颗红色的珠子嵌在正六面体的四个角， 试求不等价的方案数？试求不等价的方案数？解解:问题相当于对正六面体的问题相当于对正六面体的8个顶点用两种颜色个顶点用两种颜色 着色并求染色数相等的方案数。从着色并求染色数相等的方案数。从6.5节例节例2知，知，置换群置换群G，的阶为，的阶为24，其中格式为，其中格式为(1)的的1个，个， (4)2的的6个个， (2)4的的9个，个， (1)2(3)2的的8个。个。 故：故： 24)()(8)(9)(6)(23324222448rbrbrb

25、rbrbP31由多项式定理，其中由多项式定理，其中b4r4的系数为的系数为 ：7243254127024891212122448CCCC32总总 结结 本次课在利用本次课在利用循环指数循环指数, , 解决不等价的着色计数解决不等价的着色计数问题的基础上。增加了：已知是问题的基础上。增加了：已知是k种颜色的前提下。种颜色的前提下。解决当使用颜色次数指定时不等价的着色数量问题。解决当使用颜色次数指定时不等价的着色数量问题。 我们是用颜色变量替换我们是用颜色变量替换循环指数中的变元得到循环指数中的变元得到生成函数。再通过生成函数中生成函数。再通过生成函数中颜色变量的系数得到颜色变量的系数得到各种着色方案数。各种着色方案数。33本次授课到此结束本次授课到此结束作业如下作业如下:P376 3834总复习第第二二章章 2.1 鸽巢原理鸽巢原理 简单形式简单形式 (P17) 第三第三章章 3.1 两个基本计数原理两个基本计数原理 乘法原理与加法原理乘法原理与加法原理(P27) 3.2 集合的排列集合的排列 基本线性排列基本线性排列(P32) 环形排列环形排列(P35) 35 3.3 集合的组合