组合数学第四章.ppt

《组合数学第四章.ppt》由会员分享，可在线阅读，更多相关《组合数学第四章.ppt（53页珍藏版）》请在金锄头文库上搜索。

1、第四章 Burnside引理与Polya定理 第一节 群的概念 群G 运算 封闭 结合率 单位元 逆元 交换群 有限群G的阶 G 子群 第二节 置换群 n个元素的置换群的元素p 其中a1 a2 an是1 2 n的某个排列 交换两列看作同一元素 置换群 乘法 设P1 P2 P1P2 P2P1 P1P2 P2P1 因此置换群不是交换群 置换群 逆元素 p p 1 例1 例1 等边三角形三个顶点记为1 2 3 绕中心逆时针旋转120度 240度 沿三条中线翻转180度 三角形仍与自身重合 但顶点换了位置 这些变换分别记为P1 P2 P3 P4 P5 P6 P1 P2 P3 P4 P5 P6 构成一个

2、群 例如P2P4 P6 第三节 循环 奇循环与偶循环 记 a1a2 am 称为m阶循环 例如 132 132 45 154 2 3 154 不相交的循环 两循环无公共元 如 132 和 45 不相交的循环乘积可交换 如 132 45 45 132 定理1 定理1 任一置换可表示成若干不相交的循环之积 并且若不记次序 表示法唯一 证明 对任一置换从1开始搜索1 a1 a2 ak 1 得到一个循环 1a1a2 ak 若它包含1到n的全部文字 则搜索停止 否则在余下的文字中任取一开始搜索 如此下去 直到包含全部文字为止 2阶循环 i j 称为对换或换位 定理2 定理2 任一循环可表示成若干对换之积

3、证明 a1a2 am a1a2 a1a3 a1am 注 以上表示法不唯一 如 132 13 12 13 12 13 31 但其奇偶性唯一 若一个置换可分解成奇数个对换的乘积 则称为奇置换 否则称为偶置换 例1 例1 以下两表格不可能用相邻位置的与0对换互相转化 证明 两个表格的转化相当于对换的乘积 115 214 313 412 511 610 79 8 0 这是一个奇置换 但相邻位置的置换把0换回到原来位置必然经过偶数次对换 定理3 定理3 Sn的全体偶置换构成一个n 2阶子群 记为An 称为交代群 证明 偶置换一一对应于奇置换 并且满足群的条件 第四节 Burnside引理 讨论对称图形的

4、着色问题 一 共轭类 Sn中任意置换p可分解为不相交的循环乘积p a1a2 ak1 b1b2 bk2 h1h2 hkl 其中k1 k2 kl n 设其中k阶循环出现的次数为ck Sn中的置换可按格式 1 c 1 2 c 2 n c n的不同而分类 如 1 23 4567 的格式为 1 1 2 1 3 0 4 1 5 0 6 0 7 0 1234 5 67 有相同的格式 显然 k 1nkck n Sn中有相同格式的置换全体称为与该格式相应的共轭类 定理1 定理1 Sn中属于 1 c 1 2 c 2 n c n共轭类的元素个数为 证明 1 c 1 2 c 2 n c n的格式为 一个置换可与一个排

5、列对应 但有一定的重复度 二 k不动置换类 设G是1 2 n的置换群 即G是Sn的子群 记G中使k不动的置换全体为Zk 则Zk是G的子群 例如G e 12 34 12 34 则Z1 Z2 e 34 Z3 Z4 e 12 A4 e 123 124 132 134 142 143 234 243 12 34 13 24 14 23 Z1 e 234 243 Z2 e 134 143 Z3 e 124 142 Z4 e 123 132 三 等价类 k在G下的轨道构成一个等价类 两个数在同一类中当且仅当它们两个相差G中元素的作用 记这个轨道中的全体数的集合为Ek 例如G e 12 34 12 34 则

6、E1 E2 1 2 E3 E4 3 4 定理2 定理2 Ek Zk G k 1 2 n 证明 设G g1 gl 则 G l g1 k gl k 但g1 k gl k 中有相同的元素 记其中不同的为 g1 k gm k m l 从而Ek g1 k gm k Ek m 设gp k 的重复度是jp 1 p m j1 jm l gp k gq k 当且仅当gp 1gq在Zk中 所以与gp k 重复的数一一对应于Zk的元素 即jp Zk 对所有p 故 Ek Zk G 四 Burnside引理 设G g1 gl 把gp分解为不相交的循环乘积 记c1 gp 为gp中1阶循环的个数 即gp N N的不动点个数

7、 例如G e 12 34 12 34 c1 e 4 c1 12 2 c1 34 2 c1 12 34 0 Burnside引理 Burnside引理 设G是N 1 2 n 的置换群 G在N上的不同等价类的个数为m c1 g1 c1 g2 c1 gl G Burnside引理 证明 对上面的G作如下表格 Burnside引理 若元素gi作用在整数j上使j不动 则在第i行第j列格子中填1 否则填0 这样第i行数字之和是c1 gi 第j列数字之和是 Zj 对所有格子中的数sij求和可以得到 i jsij j 1n i 1l sij j 1n Zj i 1l j 1nsij i 1lc1 gi Bur

8、nside引理 若把N 1 2 n 分解成m个不同的等价类 比如N E1E2 Em 两个数j和k属于同一等价类意味着Ej Ek 从而由定理2 Zj Zk 故 i 1lc1 gi i 1l j 1nsij j 1n Zj k 1m j Ek Zj k 1m Ek Zk m G 例1 例1 一个正方形分成4个小正方形格子 用两种颜色着色 如果经旋转能重合的方案算同一种 问能得到多少种不同的方案 例1 解 每格有两种颜色 共有16种方案 如P321图 这16种方案分别记为c1 c2 c16 当绕中心逆时针转动90度 180度 270度时得到另外一种排列 可以看成是16种图像的置换 故群G有以下4个元

9、素 例1 1 不动置换p1 c1 c2 c16 2 逆时针转动90度p2 c1 c2 c3c4c5c6 c7c8c9c10 c11c12 c13c14c15c16 3 逆时针转动180度p3 c1 c2 c3c5 c4c6 c7c9 c8c10 c11 c12 c13c15 c14c16 4 逆时针转动270度p4 c1 c2 c6c5c4c3 c10c9c8c7 c11c12 c16c15c14c13 所以c1 p1 16 c1 p2 2 c1 p3 4 c1 p4 2 不同的等价类个数m c1 p1 c1 p2 c1 p3 c1 g4 G 6 共有6种不同的图像 第五节 Polya定理 主

10、要用于研究m种颜色的不同着色方案的计数 设有n个对象 G 是这n个对象上的置换群 现用m种颜色着色 每个对象涂一种颜色 问有多少种染色方案 一种方案在G 的作用下变成另一种 则这两种方案作为同一种看待 定理 Polya 定理 Polya 设G 是n个对象上的置换群 用m种颜色着色 不同的着色方案数为 其中G a1 ag c a k 表示置换ak 的循环节数 定理 Polya 在上一节的例1中 G 作用于着色前的4个对象上 4个小方格 G 的元素p1 1 2 3 4 不动元 p2 1234 旋转90度 p3 13 24 旋转180度 p4 1432 旋转270度 若用两种颜色着色 由Polya定

11、理 方案数l 24 21 22 21 4 6 与用Burnside引理的结果相同 但Burnside引理的G作用于着色后的16个对象上 定理 Polya Polya定理的证明 设n个对象用m种颜色着色所得的方案集合为S 则 S mn G 中的元素ak 在n个对象上的置换对应了S中mn个着色方案的一个置换ak 把ak构成的群记为G 则 G G 定理 Polya 设a 是G 中的置换并且写成c a 个不相交的循环乘积a 若每个循环中的元素均涂以同样颜色 则在S中这种着色方案在a G 与a 对应 的作用下不变 即它属于a的不动点 定理 Polya 另一方面 若a 的某个循环中有不同颜色 则必然有两个

12、相邻元素着色不同 从而在a的作用下必然得到不同的着色方案 因此我们证明了a的作用下不变的着色方案数 或a的不动点数 c1 a 应等于对a 的每个循环涂以同样颜色的方案数mc a 带入Burnside引理即可 第六节 例子 例1 等边三角形用红蓝绿对顶点着色 有几种方案 绕中心旋转及沿中线翻转重合的算同一种方案 解 G v1 v2 v3 v1v2v3 v1v3v2 v1 v2v3 v2 v1v3 v3 v1v2 v1方案数 33 2 3 3 32 6 10 V2v3 例2 例2 甲烷CH4 若4个H键用H Cl CH3 C2H3取代 H问有几种不同化学结构 HCHH 例2 解 相当于用4种颜色对

13、正四面体4个顶点着色 求方案数 使正4面体重合的刚体运动有3类 沿过顶点的中垂线旋转正负120度 共8个 沿对棱的中点连线翻转180度 共3个 不动变换 V1V2V3V4 例2 所以G v1 v2 v3 v4 v1 v2v3v4 v1 v2v4v3 v2 v1v3v4 v2 v1v4v3 v3 v1v2v4 v3 v1v4v2 v4 v1v2v3 v4 v1v3v2 v1v4 v2v3 v1v3 v2v4 v1v2 v3v4 所以 44 11 42 12 36 例3 例3 正六面体6个用红 蓝着色 有多少种方案 旋转重合的算同一种方案 解 使正六面体重合的刚体运动有5类 绕对面中心连线旋转正负

14、90度 共3 2种 旋转180度 共3种 绕对棱中点连线旋转180度 共6种 绕对角线旋转正负120度 共4 2种 不动变换 例3 以1 2 3 4 5 6分别记正六面体的上 下 左 右 前 后六个面 则G 1 2 3 4 5 6 1 2 3546 类似的有6个 1 2 34 56 类似的有3个 12 35 46 类似的有6个 253 164 类似的有8个 所以 26 6 23 3 24 6 23 8 22 24 10 例4 例4 用红 蓝两种颜色着色正六面体8个顶点 有多少种方案 旋转重合的算同一种方案 14235867 例4 解 旋转运动同上 关于顶点的运动群为G 1 2 3 4 5 6

15、7 8 1234 5678 类似的有6个 13 24 57 68 类似的有3个 15 26 37 48 类似的有6个 183 257 4 6 类似的有8个 所以 28 6 22 17 24 24 23 例5 例5 骰子的六个面有1至6个点 有多少种不同方案 解 方法一 用Burnside引理 问题相当于对六个面用6种颜色着色 每个面颜色不同 这样的方案共6 种 记为s1 s6 六面体的变换群中 除单位元外 任何一个变换都没有不动点 即把某si变成si 所以c1 e 6 c1 a 0 若a e 由Burnside引理 不同的方案数l c1 g1 c1 g2 c1 g24 G 30 例5 方法二

16、用Polya定理 容斥原理用m种颜色对六个面着色 不同的方案数记为nm 则nm m6 3m4 12m3 8m2 24 n1 1 n2 10 n3 57 n4 240 n5 800 n6 2226 令li为用i种颜色对六个面着色 所得到的不少于i种颜色的方案数 则l1 n1 1 l2 n2 C 2 1 l1 10 2 8 l3 n3 C 3 2 l2 C 3 1 l1 30 l6 n6 C 6 5 l5 C 6 4 l4 C 6 1 l1 30 例6 例6 在正六面体的每个面上作任意一条对角线 有多少种方案 解 每个面有2种做法 六个面共26种方案 记为s1 s2 6 例6 在六面体群的作用下 单位元有26个不动点 绕对面中心连线旋转正负90度无不动点 旋转180度有3 24个不动点 3对对面 上 下面各2种方案 前后方案相同 左右方案也相同 各有2种方案 由乘法原理 绕对棱中点连线旋转180度有6 23个不动点 共6对对棱 上下 前左 后右重合各2种 绕对角线旋转正负120度各有4 22个不动点 共4条对角线 下前左面重合 上后右面重合 各有2种方案 由Burnside引理 方案数l