组合数学幻灯片65..ppt

§6.5　母函数型的Polya定理 上节例4用Pólya定理导出了用m种色对正方体的面 的证明中曾述及mc(σi)代表的是对置换σi的c(σi)个不 相交的循环用m种色着染，使同一个循环中的元素着同 　　设N是n个对象的集合，G是N上的置换群，用m种色 b1,b2,…,bm对n个对象着色，则着色方案的列举可表达为 例1 对§6.4节例2中的问题，求两个“o”着红色、一个“o” 循环指标多项式 在§6.2中曾引入n次对称群Sn的共轭类的概念，即共轭类为 例2 对{1,2,3,4}上的置换群G=｛(1)(2)(3)(4), 注 设 例3 证明n次对称群Sn的循环指标多项式为 证明： 因对Sn,(1)c1(2)c2…(n)cn∈F等价于c1,c2,…,cn是满 实例与说明 对S3因满足c1+2c2+3c3=3的非负整数解(c1,c2,c3)为 例4 　　由红(r)色和黄(y)色的珠子，装成五个珠子的项 解 不动，对应的置换为(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 解(续) 所以用两色可装成 例5 若颜色使用黑、白两色，求｛an｝的普通母函数。 若颜色使用黑、白、红三色，求｛an｝的普通母函数，并求a3。 解： 用y代表黑色，w代表白色，若用wk+yk代入式(6.14)中的xk(k=1,2,3,4,5),则可得含参数w与y的多项式P，展开此多项式后形如wiyn(i任意，n固定)的所有项的系数之和，即为an。所以若在多项式P中令w=1， 解(续1) 则yn前的系数即为an，这样便可得｛an｝的母函数f1(y)。在P中令w=1，这又等价于用1+yk代入式(6.14)中的xk，所以 解(续2) 类似于1)的讨论可知用1k+1k+yk=2+yk代入式(6.14)中的xk，即可得用黑、白、红三种色着色时｛an｝的母函数 例6 骰子有六个面，分别标有1，2，3，4，5，6个点， 解法1 设6种色为r1,r2,r3,r4,r5,r6,对k=1,2,3,4,5,6,将 解法2 将正方形的上下前后左右六个面用6种颜色着色， 本节习题 习题六 13. 14. * * 着色的着色方案的计数公式。进一步若问其中三个面着红色、两个面着蓝色、一个面着绿色的方案的个数是多少?求这类问题如何计算，这就是本节所要讨论的。 　　在Pólya定理的公式 (6.11) 色的着色方案数。又每个这样的方案中，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定理，可用来对着色方案进行列举。 其中ck(σ)为σ中k-循环的个数， (6.12) 展开P经合并同类项后，　　　　　　前的系数即为i1个对象着b1色，i2个对象着b2色，…，im个对象着bm色的本质不同的着色方案数，其中i1+i2+…+im=n。 　　在式(6.12)中，令b1=b2=…=bm=1,即得式(611)。 着蓝色和一个“o”着绿色的着色方案数。 解：由§6.4的例2，置换群G有6个元，其中格式为(1)4的有一个，格式为(1)1(3)1的有两个，格式为(1)2(2)1的有三个。由式(6.12)得 因r2bg有的系数为3，所以所求数为3。 Sn中格式相同的置换构成的集合，此概念可推广到一般的置换群。设G是n元集M上的一个置换群，集合 [(1)c1(2)c2…(n)cn]=｛σ｜σ∈G,σ的格式为(1)c1(2)c2…(n)cn｝ 称为G的一个共轭类。 　　对上述G，令F为G中置换的所有不同格式构成的集合，称 (6.13) 为G的循环指标多项式。 (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)/4 k=1,2,…,n代入式(6.13)得 此即式(