组合数学幻灯片65

1§6.5母函数型的Polya定理上节例4用Pólya定理导出了用m种色对正方体的面着色的着色方案的计数公式。进一步若问其中三个面着红色、两个面着蓝色、一个面着绿色的方案的个数是多少?求这类问题如何计算，这就是本节所要讨论的。在Pólya定理的公式

(6.11)2的证明中曾述及mc(σi)代表的是对置换σi的c(σi)个不相交的循环用m种色着染，使同一个循环中的元素着同色的着色方案数。又每个这样的方案中，k循环中的k个元素着同色又对应该色用了k次，用类似于前面章节建立某组合问题的母函数的方法，色r出现k次,用rk代表，m种色r1,r2,…,rm，每种均允许出现k次,用r1k+r2k+…+rmk代表。将这样的k次多项式替换σi中每个k-循环(k=1,2,…,n),再用所有这样的k次多项式的乘积替换式(611)中的mc(σi)。对每个mc(σi)做如此处理可得母函数型的Pólya定理，可用来对着色方案进行列举。3设N是n个对象的集合，G是N上的置换群，用m种色b1,b2,…,bm对n个对象着色，则着色方案的列举可表达为其中ck(σ)为σ中k-循环的个数，

(6.12)展开P经合并同类项后，前的系数即为i1个对象着b1色，i2个对象着b2色，…，im个对象着bm色的本质不同的着色方案数，其中i1+i2+…+im=n。在式(6.12)中，令b1=b2=…=bm=1,即得式(611)。4例1对§6.4节例2中的问题，求两个“o”着红色、一个“o”着蓝色和一个“o”着绿色的着色方案数。解：由§6.4的例2，置换群G有6个元，其中格式为(1)4的有一个，格式为(1)1(3)1的有两个，格式为(1)2(2)1的有三个。由式(6.12)得因r2bg有的系数为3，所以所求数为3。

5循环指标多项式

在§6.2中曾引入n次对称群Sn的共轭类的概念，即共轭类为Sn中格式相同的置换构成的集合，此概念可推广到一般的置换群。设G是n元集M上的一个置换群，集合[(1)c1(2)c2…(n)cn]=｛σ｜σ∈G,σ的格式为(1)c1(2)c2…(n)cn｝称为G的一个共轭类。对上述G，令F为G中置换的所有不同格式构成的集合，称(6.13)为G的循环指标多项式。

6例2 对{1,2,3,4}上的置换群G=｛(1)(2)(3)(4),(1)(2)(34),(12)(3)(4),(12)(34)｝,求G的循环指标多项式。解：由G，F＝｛(1)4,(1)2(2)1,(2)2｝，且｜[(1)4]｜＝｜｛(1)(2)(3)(4)｝｜＝1｜[(1)2(2)1]｜＝｜｛(1)(2)(34),(12)(3)(4)｝｜＝2｜[(2)2]｜＝｜｛(12)(34)｝｜＝1故P(x1,x2,x3,x4)=(x14+2x12x2+x22)/47注设k=1,2,…,n代入式(6.13)得此即式(6.12)的另一形式。8例3

证明n次对称群Sn的循环指标多项式为

9证明： 因对Sn,(1)c1(2)c2…(n)cn∈F等价于c1,c2,…,cn是满足方程c1+2c2+…+ncn=n的一组非负整数解。再由定理6.10得

10实例与说明对S3因满足c1+2c2+3c3=3的非负整数解(c1,c2,c3)为(3,0,0)、(1,1,0)、(0,0,1),故设置换σ∈［(1)c1(2)c2…(n)cn］,则c1+c2+…+cn为σ所含的循环个数，即式(6.11)中的c(σ)。所以对多项式P(x1,x2,…,xn)令x1=x2=…=xn=m，便可得式(6.11)中的t，即Pólya定理中的着色方案数t=P(m,m,…,m)。11例4由红(r)色和黄(y)色的珠子，装成五个珠子的项链，问不同的项链有几种?其中恰含3个红珠的项链又有多少种?解：此问题相当于对右图中的“图形”中的“0”用两种颜色着染，求其本质上不同的着色方案数。而使“图形”重合的运动及相应的M=｛1,2,3,4,5｝上的置换有：

12解不动，对应的置换为(1)(2)(3)(4)(5)，格式为(1)5。绕中心0反时针转2π/5,4π/5,6π/5,8π/5,对应4个格式相同的置换，其中一个为(12345)，格式为(5)1绕轴10，20，30，40，50翻转，对应5个格式相同的置换，其中一个为(1)(25)(34)，格式为(1)1(2)2共10个置换，构成一个M上的10阶置换群。其循环指标多项式为13解(续)所以用两色可装成个不同的项链。对k=1,2,3,4,5,用rk+yk代入P(x1,x2,x3,x4,x5)中的xk，得其中r3y2前的系数为[C(5,3)+5×2]/10＝2，即含3个红珠2个黄珠(也即恰含3个红珠)的不同项链数为两个。14例5若颜色使用黑、白两色，求｛an｝的普通母函数。若颜色使用黑、白、红三色，求｛an｝的普通母函数，并求a3。对右图中“○”着色，经旋转与翻转能使之重合的方案算一种，记an为恰有n个点着黑色的方案数。15解：用y代表黑色，w代表白色，若用wk+yk代入式(6.14)中的xk(k=1,2,3,4,5),则可得含参数w与y的多项式P，展开此多项式后形如wiyn(i任意，n固定)的所有项的系数之和，即为an。所以若在多项式P中令w=1，记图中的点“○”的集合为M=｛1,2,3,4,5｝，由例4知使“图形”重合的运动而导出的M上的置换群G的循环指标多项式为(6.14)16解(续1) 则yn前的系数即为an，这样便可得｛an｝的母函数f1(y)。在P中令w=1，这又等价于用1+yk代入式(6.14)中的xk，所以即为｛an｝的母函数。17解(续2)类似于1)的讨论可知用1k+1k+yk=2+yk代入式(6.14)中的xk，即可得用黑、白、红三种色着色时｛an｝的母函数其中y3前系数即为a3，可得18例6骰子有六个面，分别标有1，2，3，4，5，6个点，问有多少种赋点方案。解法1问题相当于对正方体的六个面用6种颜色着色，使各面的颜色均不相同的本质不同的着色方案数。设面的集合为M=｛1,2,3,4,5,6｝，由§6.4节例4，使正方体重合的旋转而导出的M上的置换群G中含24个置换，其中格式为(1)6的1个，格式为(1)2(4)1的6个，格式为(1)2(2)2的3个，格式为(2)3的6个，格式为(3)2的8个。从而G的循环指标多项式为19解法1设6种色为r1,r2,r3,r4,r5,r6,对k=1,2,3,4,5,6,将代入多项式中的xk得将P展开，r1r2r3r4r5r6项系数即为所求，因该项只能出现在(r1+r2+r3+r4+r5+r6)6

的展开式中。而r1r2r3r4r5r6相当于在6个(r1+r2+r3+r4+r5+r6)中每一个取ri作乘积，且6个ri均不相同，故有6!个r1r2r3r4r5r6

，因而P中有6!/24＝30个，即不同的赋点方案有30种。20解法2将正方形的上下前后左右六个面用6种颜色着色，使各面着不同色，有6!种着色方案。将这些着色方案作成一个集合M。由§6.4节例4