第12讲pólya定理.pdfVIP

应用组合数学 第12讲Pólya定理 张坤龙 zhangkl@tju.edu.cn 目录 • 特殊形式的Pólya定理 • 一般形式的Pólya定理 • 图的计数 特殊形式的Pólya定理 [定理1] 设G是n个对象的一个置换群，用m种颜色涂染这n个对 象，则不同的染色方案数为 1 c (g 1 ) c (g 2 ) c (g |G| ) l [m +m +L+m ] | G | 其中G={g , g , …, g }，c(g)表示置换g 中轮换的个数。 1 2 |G| 证明：对象集D ={1,2,…,n}，颜色集R={1,2,…,m}，着色集S有 mn个元素。D上的置换群G诱导出S上的一个置换群P ，|P |=|G|。 为了应用Burnside引理，要求出P 中的每个置换包含的1-轮换 个数。 假设g诱导出p ,如果给g 的每一个轮换着相同的颜色，那么 这个着色在p 中将保持不动。例如g=(1 2 3)(4 5 6)(7) ，着色 红1，红2 ，红3，蓝4 ，蓝5，蓝6，绿7 在p 中将保持不动。因此p 中1-轮换的个数是mc(g) 。 例题1 [例1] 一正方形均分成4格，用两种颜色着色，能得到多少种 不同的图像？如果一个图像旋转后与另一个图象吻合，则 两个图象算相同的。 解：运动群G={g , g , g , g } 1 2 3 4 g =(1)(2)(3)(4) c(g )=4 1 1 2 1 g =(1 2 3 4) c(g )=1 2 2 3 4 g =(1 3)(2 4) c(g )=2 3 3 g =(1 4 3 2) c(g )=1 4 4 根据Pólya定理 1 4 1 2 1 l [2 +2 +2 +2 ] 6 4 例题2 [例2] 求用三种颜色对一个等边三角形顶点着色的方法数。如 果一种着色可由另一种着色旋转产生，或者如果一种着色 是另一种着色的翻转，则认为两种着色是相同的。 1 解：运动群G正好是S3 g =(1)(2)(3) c(g )=3 3 0 0 1 1 1 2 3 g =(1 2 3) c(g )=1 0 0 1 2 2 1 2 3