第6章pólya定理.ppt

第6章 Pólya定理 §6.1 群的概念（1） §6.1 群的概念（2） §6.1 群的概念（3） §6.1 群的概念（4） §6.1 群的概念（5） §6.1 群的概念（6） §6.2 置换群（1） §6.2 置换群（2） §6.2 置换群（3） §6.2 置换群（4） §6.2 置换群（5） §6.2 置换群（6） §6.3 循环、奇循环与偶循环（1） §6.3 循环、奇循环与偶循环（2） §6.3 循环、奇循环与偶循环（3） §6.3 循环、奇循环与偶循环（4） §6.3 循环、奇循环与偶循环（5） §6.3 循环、奇循环与偶循环（6） §6.3 循环、奇循环与偶循环（7） §6.4 Burnside引理（1） §6.4 Burnside引理（2） §6.4 Burnside引理（3） §6.4 Burnside引理（4） §6.4 Burnside引理（5） §6.4 Burnside引理（6） §6.4 Burnside引理（7） §6.4 Burnside引理（8） §6.4 Burnside引理（9） §6.4 Burnside引理（10） §6.4 Burnside引理（11） §6.5 Pólya定理（1） §6.5 Pólya定理（2） §6.5 Pólya定理（3） §6.5 Pólya定理（4） §6.5 Pólya定理（5） §6.6 Pólya定理的应用（1） §6.6 Pólya定理的应用（2） §6.6 Pólya定理的应用（3） §6.6 Pólya定理的应用（4） §6.6 Pólya定理的应用（5） §6.6 Pólya定理的应用（6） §6.6 Pólya定理的应用（7） §6.6 Pólya定理的应用（8） §6.6 Pólya定理的应用（9） §6.6 Pólya定理的应用（10） §6.7 母函数形式的Pólya定理（1） §6.7 母函数形式的Pólya定理（2） §6.7 母函数形式的Pólya定理（3） §6.7 母函数形式的Pólya定理（4） §6.7 母函数形式的Pólya定理（5） §6.7 母函数形式的Pólya定理（6） §6.8 图的计数（1） §6.8 图的计数（2） §6.8 图的计数（3） §6.8 图的计数（4） §6.9 Pólya定理的若干推广（1） 第6章 小结 第6章 习题 课程总结 §6.5 Pólya定理 定理 6.10 Pólya定理 ：设 是目标集[1,n]上的置换群，每个置换都写成不相交循环的乘积， 是置换 的循环的节数，用m种颜色对[1,n]中的元素着色，则不同着色方案数为 分析： Pólya定理中的 群是作用在n个对象上的置换群，相应地，Burnside定理中的G 群是在这n个对象上用m种颜色进行染色后的方案集合上的置换群。 G 群与 群之间的联系是这样的：对应于群 的元素 ，相应地在染色方案集合上也诱导一个属于G 的置换p 。 只要证明 即可。 §6.5 Pólya定理 举例分析如下：在证明以前，先就前面的例子进行分析，然后推广到一般。 右图的染色方案见上节例2题中的图。 其置换群为 分别对应于上节例题中方案集的置换。 p1=(1)(2)…(16) p2=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16) p3=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12)(13 15)(14 16) p4= (1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13) 仔细观察其中的关系，首先，不难发现 2 1 3 4 §6.5 Pólya定理 其次，还可以发现，在pi作用 下不变的图像正好是对应的 的循环节中的对象染以相 同的颜色所得到的图像。 例如， 对应的p2中一阶循环节为(1)(2)。 见图，图像C1 ,C2正好是1,2,3,4 着以同一种颜色所得的结果。 又如 对应的p3中的一阶循环节为 (1)(2)(11)(12)，正好是1和3, 2和4分别着以相同的颜色的 结果。 2 1 3 4 C1 C2 C11 C12 §6.5 Pólya定理 定理 6.10 Pólya定理 ：设 是目标集[1,n]上的置换群，每个置换都写成不相交循环的乘积，