polya定理幻灯片.ppt

谢谢！ 4 Pólya定理-举例 所求方案数: 例6 骰子的6个面分别有1,…,6点，有多少种不同的方案？ · · ·· · · · ··· ·· ·· ·· ··· ··· · ·· ·· · · · · · 4 Pólya定理-举例 解 1) 6!个图象的目标集,只有单位元有6!个不动 点(图象)其他23个群无不动点。由Burnside引理 有[C1(e)]/24=6!/24=30个方案。 C1(p1)=C1(p2)=…=C1(p23)=0 1点,4点,5点各有一种取向， 2) 2点,3点,6点各有两种取向， 故应有30·23=240种方案。 * 我们这里给出的Polya计数定理其实是一种特殊形式. 一般形式的Polya定理还可以用来解决有条件限制而且互相不等价的染色方案数目. 还有一个问题是如何列举出所有不同类型的染色方案? 显然Polya定理无法告诉我们这些. 它只能告诉我们总数. 母函数形式Polya定理可以满足这个要求. 5母函数形式的Pòlya定理 * 例1. 假设要用b, g, r, y这4种颜色涂染3个同样的球, 则所有方案可形式地表示为(b+g+r+y)3. 由于三个球无区别, 故乘法是可交换的, 例如b2g=gb2. 把这个形式展开: (b+g+r+y)3=b3+g3+r3+y3+3b2g+3b2r+3b2y +3g2b+3g2r+3g2y+3r2b+3r2g+3r2y+3y2g +3y2r+3y2b+6bgr+6bgy+6brg+6gry 展开式中的不同项表示不同的方案, 每项系数表示该方案的数目. 5 母函数形式的Pòlya定理 * 设G是n个对象集合S={a1,a2,…,an}上的一个置换群, 要用m种颜色b1,b2,?, bm进行染色, 我们需要讨论并决定互不等价的染色方案的情况. 根据Polya定理, 不等价的染色方案数目可以通过下面的公式得到: 把上面这种思想方法用于Polya定理, 就得到 母函数形式Polya定理. 5 母函数形式的Pòlya定理 * 其中c(g)是置换g的轮换总数目, 而 如果置换g的类型为: (c1(g),c2(g),…,cn(g)), c(g)=c1(g)+c2(g)+…+cn(g)), 则 5 母函数形式的Pòlya定理 称为置换群G的轮换指标. * 其含义是让置换g的ci个长为i的轮换中每个轮换中 的元素染同样的颜色, 这是为了得到由g诱导出的 置换g*的不动点. 5 母函数形式的Pòlya定理 当时我们并不关注这个同样的颜色究竟是哪一种颜色. 现在我们想列举出染色方案情况, 就需要关注这个问题. 根据刚才例题的思想, 对应于置换g的每个长为i的轮换因子, 其中i个元素的颜色可以形式的表示为: * 既然g有ci=ci(g)个长为i的轮换, 自然长为i的轮换中 出现的元素的染色方案可以形式的表示为: 考虑到g的全部轮换分解情况, 相应于置换g的染色 方案可以形式表示为: 由此可知, 总的染色方案的列举只要在轮换指标中 令: 5 母函数形式的Pòlya定理 * 由此，可得能列举出方案情况的母函数形式的 Polya定理: 此即母函数形式的Polya定理的计数公式, 在具体应用 中展开并按照同类项整理, 即可列举出不同的方案情 况和数目. 5 母函数形式的Pòlya定理 * 例2 有3种不同颜色的珠子, 用它们串成4个珠子的项链. 问一共能串成多少种不同类型的项链? 列举出全部不同类型的方案. 解 先要确定保持图形与原来位置重合的置换群G. v1 v2 v3 v4 5 母函数形式的Pòlya定理 * (v1)(v2)(v3)(v4),(v2)(v4)(v1v3), (v1)(v3)(v2v4), (v1v3) (v2v4), (v1v2) (v3v4), (v1v4) (v2v3), (v1v2v3v4), (v4v3v2v1), 5母函数形式的Pòlya定理 共有4种类型的置换, 容易写出其轮换指标公式: 容易看出来使得项链运动前后重合的置换群G含有以下8个置换: * 总方案数 P=8-1[(b+g+r)4 + 2(b+g+r)2(b2+g2+r2) + 3(b2+g2+r2)2 + 2(b4+g4+r4)] 5 母函数形式的Pòlya定理 如果要列举出具体方案情况, 需要利用母函数形式 的Polya定理. 为书写方便, 我们用