Burnside引理与Polya定理.ppt

第4章 Burnside引理与Polya定理,2019/12/4,2,问题：用黑、白两种颜色对22棋盘的格子着色，问有几种不同的着色方案？,引论,2019/12/4,3,(1) 若正方形的位置固定，则有16种不同的着色方案; (2) 若正方形可以转动，则有6种不同的着色方案。 Polya定理是解决不等价的诸物的记数问题。,引论,2019/12/4,4,定义 给定一个集合G和G上的一个二元运算*, 若下列四个条件成立: (1) 对任 , 有 ; (2) 对任 , 有 ; (3) 存在 , 对任 有 ; (4) 对任 , 存在 , 使得 则称集合G在运算*下构成一个群. 或称代数结构 是一个群。,群,2019/12/4,5,基本性质: 定理4.1 群的单位元是唯一的。 定理4.2 如果 是一个群，则对任 , 有 (a) a*b=a*c b=c (b) b*a=c*a b=c 定理4.3 群中每一个元素的逆元素是唯一的。 定理4.4 如果 是一个群，那么对任 ,有,群,2019/12/4,6,定义 设 是一个群, H是G的非空子集, 并满足以下条件: (1) 若 , 则 ; (2) 若 , 则 ; (3) , e 是 的单位元 则称 为 的子群。,群,2019/12/4,7,定理 设 是有限群, H是G的非空子集，若H关于*封闭，则 是 的子群。 证 设|H|=n。 , 中必有两个相等. 设为 , 则 . 若 , 则由 知 若 , 则由 知 这就证明了对 , 有 , 故 所以 是 的子群。,群,2019/12/4,8,定义 集合S上的双射函数P称为S上的一个置换。 当S为无限集时, S上的置换称为无限次的。当S为n个元素的有限集时, 则S上的置换称为n次的。 n次置换一般记为 其中 为 的一个排列.,置换群,2019/12/4,9,例 若S=1,2,3, 那么S上的所有置换为 设 为1,2,n上的置换的全体，显然有 。 对任 , 定义它们的乘积 为：,置换群,2019/12/4,10,例 定理 关于置换乘积运算构成群, 称为n次对称群. 证 (1) 封闭性: 若 , 则 , 因而,置换群,2019/12/4,11,(2) 结合性: 故 (3) 单位元:,置换群,2019/12/4,12,置换群,(4) 逆元素: 的子群称为置换群。,2019/12/4,13,一个置换可以表示为若干循环之积。 定理4.6 任何一个置换都可以表示为若干循环之积. 证 , 考虑 其中 是第一次出现重复的元素。,置换群,2019/12/4,14,置换群,下面证明 。 若不然, 则有 , 使得 , 即有 , 但 , 这与p是 单射相矛盾。 具体分解过程: 从1开始, 考虑 得到一个包含1的循环 , 若 包含了所有的元素, 则停止;,2019/12/4,15,置换群,否则, 令 是不在上述循环中的最小元素, 构造 得到包含 的循环 。 这样继续下去, 直到所有的元素取完为止。 例,2019/12/4,16,1. 共轭类 设G是 的子群, 对任 , 若存在 , 使得 , 则称 s 与 t 是G共轭的. G共轭关系是一个等价关系: (1) 自反性: , 有 ; (2) 对称性: ; (3) 传递性: 若 , 则,Burnside引理,2019/12/4,17,设Sn中置换p分解如下互不相交的循环之积: 其中 . 若k阶循环出现的次数为 , 则称置换 p 的型(格式)为 显然有 .,Burnside引理,2019/12/4,18,Burnside引理,例 的型为 引理 两个置换 是关于 共轭的当且仅当它们是同型的. 在Sn中同型置换的全体, 称为与该型相应的共轭类.,2019/12/4,19,定理4.9 Sn中属于 共轭类的置换个数为 例 S4中22共轭类有 个置换. S4中1221共轭类有 个置换。,Burnside引理,2019/12/4,20,2. k不动置换类 设G是1,2,n上的置换群, 令 称 为G之k不动置换类. 例 若G=e, (1 2), (3 4), (1 2)(3 4), 则有 Z1=e, (3 4), Z2=e, (3 4) Z3=e, (1 2), Z4=e, (1 2),Burnside引理,2019/12/4,21,定理 4.10 群G的k不动置换类Zk是G之一个子群. 证 显然 , 故Zk非空. 又若 , 由 知 , 故Zk是G之一个子群。,Burnside引理,2019/12/4,22,3. 等价类 设G是S=1,2,n上的置换群, 在S上定义G等价关系: 对任 , 若存在 , 使得 , 则称 是G等价的. 定理4.10 G 等价关系是 S 上的等价关系. 证 (1) 自反性: 对任 , 有 ; (2) 对称性: 若 , 则 (3) 传递性: 若 , , 则,Burnside引理,2019/12/4,23,元素k所在的等价类记为Ek。 例 若G=e, (1 2), (3 4), (1 2)(3 4), 那么有 E1=E2=1,2, E3=E4=3,4,Burnside引理,2019/12/4,24,习题,4.8 4.10,2019/12/4,25,k不动置换类 设G是1,2,n上的置换群, 令 称 为G之k不动置换类. 例 若G=e, (1 2), (3 4), (1 2)(3 4), 则有 Z1=e, (3 4), Z2=e, (3 4) Z3=e, (1 2), Z4=e, (1 2),Burnside引理,2019/12/4,26,等价类 设G是S=1,2,n上的置换群, 在S上定义G等价关系: 对任 , 若存在 , 使得 , 则称 是G等价的. 元素k所在的等价类记为Ek。 例 若G=e, (1 2), (3 4), (1 2)(3 4), 那么有 E1=E2=1,2, E3=E4=3,4,Burnside引理,2019/12/4,27,定理4.11 |Ek|Zk|=|G|, k=1,2,n. 证 设 , 由 Ek 之定义知, 存在 , 使得 令 性质: (1) , 故,Burnside引理,2019/12/4,28,(2) 中的置换将 映射为 , 而 中的置换将 映射为 . (3) 显然有 任取 , 若 , 则a与a1(=k)等价, 故 , 不妨设 , 则由,Burnside引理,2019/12/4,29,由 知 所以,Burnside 引理,2019/12/4,30,例 E1=1,2,3,4, Z1=e, (2 3 4), (2 4 3). |E1|=4, |Z1|=3, |E1|Z1|=12=|G|,Burnside 引理,2019/12/4,31,Burnside 引理 设 是1,2,n上的置换群, 则G诱导出来的等价类个数为 其中 表示在 作用下保持不变的元素个数. 证 设在置换群G的诱导下, 把1,2,n划分为 个 等价类： . 首先证明: 若j与k在同一个等价类中, 则 .,Burnside 引理,2019/12/4,32,由j与k在同一个等价类中知 , 于是,Burnside 引理,2019/12/4,33,其中,Burnside 引理,2019/12/4,34,例1 G=e, (1 4)(2 3), (1 2)(3 4)(5 6), (1 3)(2 4)(5 6)是1,2,6上的置换群. 由Burnside引理, G诱导出来的等价类个数为 这两个等价类为: E1=1, 2, 3, 4, E5=5, 6.,Burnside 引理,2019/12/4,35,例2 一正方形分成4 个格子, 用两种颜色对4 个格子着色, 问有多少种不同的着色方案？经旋转使之吻合的两种方案算同一方案. 解 当不考虑旋转的情况下, 有下列16种着色方案:,Burnside 引理,2019/12/4,36,S=C1,C2,C16, S上的置换群为G=p1,p2,p3,p4,其中p1,p2,p3,p4分别为正方形绕中心顺时针旋转 所得到着色方案的置换. 即有,Burnside 引理,2019/12/4,37,于是所求着色方案为,Burnside 引理,2019/12/4,38,例3 一个圆环, 按顺时针方向 位置上装一红或蓝的珠子, 问有多少种不同的方案？刚体运动使之吻合的算一种方案. 解 对应的置换群除了 , 还包括 (1) 沿轴 翻转,Burnside 引理,2019/12/4,39,(2) 沿轴 翻转 (3) 沿轴1-3翻转,Burnside 引理,2019/12/4,40,(4) 沿轴2-4翻转 所求方案数为,Burnside 引理,2019/12/4,41,例4.8 假定要把全部5码数印刷在纸条上, 因为0, 1, 6, 8, 9倒过来看时, 变成了0, 1, 9, 8, 6, 所以若一张纸条既可以正看, 又可以倒看时, 有些5码数对可以共用一张纸条, 问题是需要多少张不同的纸条才能作出这105个5码数？ 解 S为105个5码数的集合, 是S上的置换群,其中 是恒等置换, 是这样的置换, 如果一个数倒过来看是不成数的, 则将这个数映射为它自身,Burnside 引理,2019/12/4,42,如果一个数倒过来看是一个数, 则将该数映射为将该数倒过来之后所得到的数. 所求不同纸条的张数为,Burnside 引理,2019/12/4,43,习题,3.2 求从1到500的整数中被3和5整除但不被7整除的数的个数。 解 令A1表示从1到500的整数中被3整除的数的集合，A2表示从1到500的整数中被5整除的数的集合，A3表示从1到500的整数中被7整除的数的集合。 从1到500的整数中被3和5整除的数的个数为,2019/12/4,44,习题,而在这些数中，又能被7整除的数的个数为 故所求个数为：33-4=29。,2019/12/4,45,习题,3.62 一书架有m层，分别放置m类不同种类的书，每层n册。现将书架上的图书全部取出清理。清理过程要求不打乱所在的类别。试问 (a) m类书全不在各自原来层次上的方案数有多少？ (b) 每层的n本书都不在原来位置上的方案数等于多少？ (c) m层书都不在原来层次，每层的n本书也都不在原来位置上的方案数等于多少？,2019/12/4,46,习题,解 (1) m类书全不在各自原来层次上的放法有Dm种，对每一种放法，每一层的书有n!种放法，故共有种 方案。 (2) 将m类书全放到各层上的放法有m!种，对每一种放法，每一层的书有Dn种放法，故共有种 方案。 (3) 所求方案数为： 。,2019/12/4,47,习题,4.6若H是G的子群，x和y是G的元素，试证或为 空，或 。 证 若 ，那么存在 ，使得 。因而有 。于是对任 ，有 ，即有 同理可证 。所以 。,2019/12/4,48,习题,4.7 若H是G的子群， ，试证： ，其中 。 证 作映射 。 (1) 是单射。 (2) 是满射. 所以 。,2019/12/4,49,习题,4.8 有限群G的阶为n，H是G的子群，则H的阶整除G的阶. 证 若 ，取 ，作 若 ，取 ，作 若 ,取 ,作 这样继续下去，由于G是有限的，故存在 ，使 所以,2019/12/4,50,习题,4.10 若x和y在群G的作用下属于同一等价类，则x所属的等价类 ，y所属的等价类 有 。 证 由题意， ，使得 。 即有 ，同理可证 。 所以,2019/12/4,51,从理论上来讲, Burnside引理可以解决用m种颜色对n个物体进行着色的方案数的计数问题. 但当m, n较大时, 把 种着色方案编上号, 研究这些着色方案在置换群作用下等价分类情况, 工作量之大是可想而知的. 正因为如此, Burnside引理在1911年提出后并没有得到广泛应用. Polya于1937年对此引理作出了重大改进, 形成Polya定理之后,它在化学、遗传学、图论、编码以及计算机科学中得到了广泛的应用.,Polya定理,2019/12/4,52,置换群的循环指标: 设n个元素的置换p的型为 则称 为置换p的循环指标. 置换群G的循环指标定义为G中诸置换的循环指标之和被G中置换的个数所除的商, 即有,置换群的循环指标,2019/12/4,53,例1 G=e, (1 2), (3 4), (1 2)(3 4), 则 例2 G=e, (1 2), (1 3), (2 3), (1 2 3), (1 3 2),置换群的循环指标,2019/12/4,54,定理(Polya) 设G是n个元素集合上的一个置换群, 用m种颜色b1,b2,bm对这n个元素进行着色, 则不同的着色方案数为 而所有的染色方案可表示为 其中项 的系数为n个元素有 个着 色, 个元素着 色, 个元素着 色的方案数.,Polya定理,2019/12/4,55,例 一正方形分成4 个格子, 用两种颜色对4 个格子着色, 问有多少种不同的着色方案？经旋转使之吻合的两种方案算同一方案. 解 如图所示标记4个格子, 置换群为 其循环指标为 所求染色方案数为,应用举例,2019/12/4,56,例 一个圆环, 按顺时针方向 位置上装一红或蓝的珠子, 问有多少种不同的方案? 刚体运动使之吻合的算一种方案. 解 如图将4颗珠子分别标记为 1, 2, 3, 4. 使圆环吻合的置换群为,应用举例,2019/12/4,57,其循环指标为 所求方案数为,应用举例,2019/12/4,58,例1 将等边三角形的三个顶点用红、蓝、绿三种颜色进行着色,问有多少种不同的着色方案? 如果 (1) 经旋转能重合的方案认为是相同的？ (2) 经旋转和翻转能重合的方案认为是相同的？ 解 (1) 如图所示, 等边三角形 的三个顶点分别标记为1,2,3. 1,2,3上的置换群为 G=e, (1 2 3), (1 3 2),应用举例,2019/12/4,59,其循环指标为 所求染色方案数为 (2) 只是将(1)中的置换群变成 G=e, (1 2 3), (1 3 2), (1)(2 3), (2)(1 3), (3)(1 2),应用举例,2019/12/4,60,其循环指标为 所求染色方案数为：,应用举例,2019/12/4,61,例2 由 三种颜色的5颗珠子镶成的圆环, 共有几种不同的方案? 又问由两个b色和三个r 色珠子镶成的圆环有多少个? 解 如图所示, 将5颗珠子分别 标记为为1,2,3,4,5. 使5颗珠子 重合的置换群G中有10个置换. 其中有5个旋转和5个反射:,应用举例,2019/12/4,62,G之循环指标为 所求方案数为 由两个b色和三个r 色珠子镶成的圆环的个数为,应用举例,2019/12/4,63,中项 的系数. 其为 注: 多项式 展开式中项 的系数为,应用举例,2019/12/4,64,例3 对正立方体的6个面用红、蓝、绿三种颜色进行着色, 问有多少种不同的着色方案? 又问3种颜色各出现两次的着色方案有多少种? 解 使正立方体重合的置换群 中有24个置换, 它们是: (1) 不动置换, 型为16, 有1个; (2) 相对两面中心轴旋转 的置换, 型为1241,有6个; 旋转 的置换, 型为1222, 有3个;,应用举例,2019/12/4,65,(3) 绕相对两顶点连线旋转 的置换, 型为32,有8个; (4) 绕相对两边中点连线旋转 的置换, 型为23, 有6个. 该置换群的轮换指标为 所求着色方案数为:,应用举例,2019/12/4,66,着色方案为 其中红、蓝、绿色各出现2次的方案数为上述展开式中r2b2g2的系数, 为,应用举例,2019/12/4,67,例4 用两种颜色对正立方体的8个顶点着色，问有多少种不同的着色方案？ 解 使正立方体重合的置换群中 有24个置换,它们是： (1) 不动置换, 型为18, 有1个; (2) 相对两面中心轴旋转 的置换, 型为42, 有6个; 旋转 的置换, 型为24, 有3个；,应用举例,2019/12/4,68,(3) 绕相对两顶点连线旋转 的置换, 型为1232, 有8个; (4) 绕相对两边中点连线旋转 的置换, 型为24, 有6个. 该置换群的循环指标为,应用举例,2019/12/4,69,故所求方案数为,应用举例,2019/12/4,70,例5 骰子的六个面分别有1,2,3,4,5,6个点, 问有多少种不同的骰子? 解 问题相当于用6种不同的颜色对正立方体的6个面进行着色, 并且每种颜色出现且仅出现一次. 由例3知, 使正立方体重合的置换群中有24个置换,其循环指标为,应用举例,2019/12/4,71,着色方案为 所求的不同的骰子数为,应用举例,2019/12/4,72,例6 用4颗红色的珠嵌在正六面体的四个角，问有多少种方案？ 解 问题相当于用两种颜色r,b对正立方体的8个顶点着色, 两种颜色相等的方案数. 由例4知置换群的循环指标为,应用举例,2019/12/4,73,具体方案可表示为 所求方案数为该展开式中b4r4的系数, 即为,应用举例,2019/12/4,74,问题: n个顶点简单图有多少个? n个顶点完全图Kn有 条边, 若对Kn的边进行2着色, 然后去掉一种颜色的全部边, 就构成了有n个顶点的简单图. 于是求n个顶点简单图的个数问题就变成求对n个顶点完全图的边进行2着色的方案数问题.,应用举例,2019/12/4,75,两个n顶点简单图是相同的当且仅当这两个图是同构的. 而两个图是同构的当且仅当存在V=1,2,n上的一个置换p, 使得当(i, j)为一个图中的边时, 为另一个图的边. 当n=3时, 顶点集V=1,2,3上的每一个置换p, 利用规则 都得到边集 上的一个置换。,应用举例,2019/12/4,76,例如 若 则p置换E中的边如下：,应用举例,2019/12/4,77,令G为这样得到的边集E上的置换的集合所构成的置换群, 那么K3中两个图是同构的当且仅当对这两个图的边的着色是等价的. 于是问题成为在置换群G下, 对E中边着色的不同等价类的个数问题. 由下表可得G中所有的置换,应用举例,2019/12/4,78,V=v1,v2,v3上的置换 E=e1, e2, e3上的置换 (v1)(v2)(v3) (e1)(e2)(e3) (v1v2v3) (e1e2e3) (v1v3v2) (e1e3e2) (v1)(v2 v3) (e2)(e1 e3) (v2)(v1 v3) (e3)(e1 e2) (v3)(v1 v2) (e1)(e2 e3),应用举例,2019/12/4,79,G的循环指标为 所有的染色方案为,应用举例,2019/12/4,80,若取红边为图中的边，则相应的四个图如下：,应用举例,正 n 面体只有 5 个：正 4 面体，正 6 面体，正 8 面体，正 12 面体，正 20 面体。没有其他的正多面体。 面 棱 顶点 4 6 4 6 12 8 8 12 6 12 30 20 20 30 12,2019/12/4,81,欧拉公式:v + f - e = 2 （v点，f面，棱） 正面体只有5种，即为：正4，6，8，12，20面体 正4面体有6条棱,4个点,4个面; 正6面体有12条棱,8个点6个面; 正8面体有12条棱,6个点8个面; 正12面体有30条棱,20个点12个面.,2019/12/4,82,