组合数学(28)教材

第八章Polya计数法

14.3Polya计数公式(二)上次课我们通过研究置换中的循环因子分解、型、单项式、循环指数,解决不等价的着色计数问题。但定理的应用是在已知C是k种颜色的前提下。现在我们解决当使用颜色次数指定时不等价的着色数量。

设集合X={1,2,3,…n}中各颜色的元素的1个数是指定的，C是由集合X的所有着色构成的集合。对X中的每个置换f与C中的每种着色c,一种特定的颜色出现在c中的次数与该颜色出现在f*c中的次数相同。换句话说：对X中的对象与其颜色一起进行置换并不改变各种颜色的数目。就是说X的任意置换群都可作为着色集C中的一个置换群。

2例：(10阶二面体群)对正五边形的顶点着三点红色两点蓝色，有多少不等价的着色数量？解：从5个点中任意选择3点着红色，其余的着蓝色，有组合数求法共有：C(5,3)=10种。用D5

表示旋转和翻转置换群，除了旋转0°保持着色不变，其他旋转都不行。右图的翻转可以143253可以保持着色不变，下图一样，选择其他顺序着红、蓝两种色都无法保持沿1点中垂线翻转后着色不变。无论选择哪点作中垂线，该点必须着红色，其余两红两蓝四点必须以中垂线对称着同一颜色。根据前面例题求过的用D5的循环因子分解和上面的分析结果，列出下表：143254置换循环的因式分解不变的着色数[1]

。[2]

。[3]

。[4]。[5]10[12345]0[13524]0[14253]0[15432]0[1]

。[25]

。[34]2[13]

。[2]

。[45]2[15]

。[3]

。[24]2[12]

。[35]

。[4]2[14]

。[23]

。[5]2蓝色的点是中垂线的顶点5注意：沿中垂线翻转时，翻转的型都有(1200)即有一个顶点位置没有改变；我们必须对两个2-循环的每一个着同一种颜色，这样就有两个不等价的着色出现。应用定理14.2.3得不等价的着色方案数为：它们是：两个连续的蓝色顶点或者两个不连续的蓝色顶点。6为了用Burnside定理来求各颜色出现的次数被指定时的不同着色数量,我们必须能够求出置换保持着色不变的着色数。

令f是含有n个元素的集合X的一个置换。假设置换f的型是：

type(f)=(e1,e2,…..en),置换f的单项式为：

7那么在置换f的循环因子分解中有

e1个1阶循环，

e2个2阶循环…..en个n阶循环。为了讨论方便，我们就设仅有红色和蓝色两中颜色。令Cp,q表示所有p个元素着红色和q=n-p个元素着蓝色的X的着色集合。Cp,q中的一种着色在置换

f的作用下保持不变的充要条件是f的循环因子分解中的每个元素的颜色相同。因此，为求Cp,q在置换f的作用下保持不变的8着色数，我们可以认为是对循环指定红色元素的个数为p(从而着指定为蓝色元素的个数为q=n-p)。假定指定红色的1-阶循环有t1个，指定红色的2-阶循环有t2个，…….，指定红色的n-阶循环有tn个。而我们假设红色元素个数是p，必然有下关系成立：

p=1·t1+2·t2+3·t3+…..+n·tn其中t1,t2,t3,…..,tn满足关系9

0≤t1≤e1,0≤t2≤e2,…..0≤tn≤en

于是，在f的作用下使Cp,q中着色保持不变的着色数|Cp,q(f)|等于不等式的解的个数。现在将红色看成变量r，蓝色看成变量b。对f的单项式作代数变换：

z1=r+b,z2=r2+b2,z3=r3+b3,…..zn=rn+bn而得到

10

由于置换群G的循环指数是G中的置换f的单项式的平均值。因此，由P358定理14.2.3，Cp,q中不等价的着色数量等于对G的循环指数做代换zi=ri+bi而得到的表达式：

中rpbq的系数。这意味作上式是当Cp,q中用各种颜色着色的元素个数为指定时，关于不等价着色数的一个二元变量r,b的生成函数。11下面我们给出Polya定理，它的推导、应用已经成为本章的主要目的。定理14.3.3设X是一个元素集合，G是X的一个置换群，{u1,u2,…..uk}是k种颜色的一个集合，C是X的任意着色集并且G为C上的一个置换群，那么，根据各个颜色的数目，C的不等价着色数的生成函数是：由循环指数

PG

(z1,z2,…zn)通过做变量代换：12而得到的表达式：换而言之,上面表达式的展开式中：的系数等于集合X中的p1个元素着颜色u1，p2个元素着颜色u2，……,pk个元素着颜色uk，的C中不等价着色总数。13

例：分别用2种颜色和3种颜色对一个正方形的顶点着色，分别求它们不等价着色的生成函数。解：由上次课的计算可知，正方形的顶点对称群D4的循环指数为：14(1)设两种颜色为r与b,则二元生成函数为：于是,不等价的着色数是各个项系数的和，等于6其中，全部顶点着红色或者蓝色的各一种；三红一蓝和三蓝一红各一种；两红两蓝两种。15

(2)设三种颜色为r,b与g,则三元生成函数为：利用第五章P91“多项式定理”

，我们总能够将上式展开后求得各个单项式的系数；例如：项rb2g的系数是：16就是说存在一红、两蓝、一绿的顶点着色，共有不等价的两种。总不等价的着色总数为：例:分别用2种颜色和3种颜色对一个正五边形的顶点着色，分别求它们不等价着色的生成函数。解：由上次课的计算可知，正五边形的顶点对称群D5的循环指数为：17这个循环指数中没有z1和z3出现，这是因为

D4中的置换在其循环因子分解中均无3-循环和4-循环。(1)设两种颜色为r与b,则二元生成函数为：18不等的着色总数为系数之和：1+1+2+2+1+1=8。

(2)设三种颜色为r,b与g,则三元生成函数为:19例:有三种不同颜色的珠子，用它们装成四粒珠子的项链，问有哪些方案？解:不难写出四边形的4个顶点v1,v2,v3,v4所对应的二面体群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)。20其中,格式为(1)4的1个，(4)1的2个，(2)2的3个，(1)2(2)的2个。根据Polya定理，不同方案数为:具体方案是:P=((b+g+r)4+2(b4+g4+r4)+3(b2+g2+r2)2

+2(b2+g2+r2)(b+g+r)2)/821=b4+r4+g4+b3r+b3g+br3+r3g+bg3+rg3+2b2r2+2b2g2+2r2g2+2b2rg+2br2g+2brg2

其中b2rg的系数为2，故知由两蓝、一红、一绿四颗珠子组成的方案有2种，即红、绿、蓝、蓝及红、蓝、绿、蓝,再换蓝珠的位置会重复。上式中各单项式中b、r、g的幂是所用各种颜色珠子的数量，各单项式的系数就是这种组合的方案数。22例(立方体的顶点与面的着色)用指定颜色对一个立方体的顶点与面进行着色，求立方体的对称群和不等价的着色数。解:一个立方体的对称共有24种，它们属于四种不同类型的旋转：1)平面恒等旋转τ(1个)2)绕3对垂直对立面中心旋转14235623

a)90度（3个）

b)180度（3个）

c)270度（3个）3)绕对边中点连线旋转180度（6个，有6根连线）4)绕对角点连线旋转

a)120度（4个）

b)240度（4个）14235624立方体对称的总计数是：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,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)25

由上表我们看出立方体的顶点对称群GC的循环指数为:立方体的面对称群GF的循环指数为:用红色和蓝色对立方体的顶点着色，不等价着色的生成函数为:26关于立方体面的生成函数为：27由上面两式的系数我们可以得到立方体关于顶点的不等价着色总数是：23；关于面的不等价着色总数是10。如果我们用k种颜色去对顶点着色，则：不价的顶点着色数是：28不等价的面着色数是：29例:把四颗红色的珠子嵌在正六面体的四个角，试求不等价的方案数？解:问题相当于对正六面体的8个顶点用两种颜色着色并求染色数相等的方案数。从6.5节例2知，置换群G，的阶为24，其中格式为(1)８的1个，(4)2的6个，(2)4的9个，(1)2(3)2的8个。故：30由多项式定理，其中b4r4的系数为：31总结

本次课在利用循环指数,

解决不等价的着色计数问题的基础上。增加了：已知是k种颜色的前提下。解决当使用颜色次数指定时不等价的着色数量问题。我们是用颜色变量替换循环指数中的变元得到生成函数。再通过生成函数中颜色变量的系数得到各种着色方案数。32本次授课到此结束

作业如下:P3763833总复习第二章2.1鸽巢原理

简单形式

(P17)

第三章3.1两个基本计数原理

乘法原理与加法原理(P27)

3.2集合的排列

基本线性排列(P32)

环形排列(P35)343.3集合的组合

基本组合(P36)

3.4多重集的排列、组合

多重集的排列和多重集的组合公式(P40)第五章5.2二项式定理

二项式系数公式(P79)

5.4牛顿二项式定理、多项式定理多项式展开公式，展开后的系数(P91)牛顿二项式展开公式(P94)35第六章6.1容斥原理

基本公式(P104)第七章7.1某些数列

Fibonacci序列(P126)

7.2线性齐次递推关系

用特征方程的解法(P132)

7.3非齐次递推关系