《组合数学群论》由会员分享，可在线阅读，更多相关《组合数学群论（61页珍藏版）》请在金锄头文库上搜索。
1、黑板上的排列组合,用六种不同颜色涂一正方体，一面一色，且每面颜色不同，会有多少种涂法？,用六种不同颜色涂一正方体，一面一色，不同面可以同色，会有多少种涂法？,6*5*P(4,4)/4 / 6 = 30,2,第四章 Burnside引理和Plya定理,组合计数中遇到的困难 找出问题通解的表达式困难 引入母函数 区分讨论的问题类型困难,区分同类性,避免重复和遗漏 容斥原理避免重复计数 如何区分同类 举例 红蓝两种颜色给正方形的四个顶点着色,存在多少种不同的方案?24 若允许正方形转动,有多少种方案? 分类：按红色点分类 0个红点 1种 1个红点 1种 2个红点 2种 3个红点 1种 4个红点 1种
2、,共6种,3,群(group),5,伽罗华（Galois）,variste Galois(18111832) 引入群论新名词并奠定了群论基础 非常彻底地把全部代数方程可解性问题，转化或归结为置换群及其子群结构分析的问题,得出五次以上一般代数方程根式不可解，以及用圆规、直尺(无刻度的尺)三等分任意角和作倍立方体不可能等结论。 刘维尔在1846才领悟到其手稿中迸发出的天才思想，他花了几个月的时间试图解释它的意义 他被公认为数学史上两个最具浪漫主义色彩的人物之一 他的死使数学的发展被推迟了几十年 这个人是上帝派来的，在人世间匆匆转了一圈，仅仅21年，却一不小心，开启了数学的一个新时代 伽罗华在圣佩拉
3、吉监狱中写成的研究报告中写道：“把数学运算归类，学会按照难易程度，而不是按照它们的外部特征加以分类，这就是我所理解的未来数学家的任务，这就是我所要走的道路。”,http:/ 群的概念,(1)群(group) 定义 给定集合G和G上的二元运算 ，满足下列条件称为群。 (a)封闭性(Closure)： 若a,bG,则存在cG,使得ab=c. (b)结合律(Associativity)： 任意a,b,cG,有(ab)c=a(bc). 由于结合律成立，(ab)c=a(bc)可记做abc. (c)有单位元(Identity)： 存在eG,任意aG.ae=ea=a. (d)有逆元(Inverse)： 任意
4、aG,存在bG, ab=ba=e. 记为b=a-1.,7,4.1 群的概念,(2) 简单例子 例 G=1,-1在普通乘法下是群。 证：1)封闭性：11=1 (-1)(-1)=1 (-1)1=-1 1(-1)=-1 2)结合律：成立3)单位元：14)逆元素：1的逆元是1，-1的逆元是-1 例 G=0,1,2,n-1在mod n的加法下是群. 证：1)封闭性：除以n的余数只能是0,1,2,n-1，故封闭性成立2)结合律：成立3)单位元：04)逆元素：对任意元素a有(a+(n-a) mod n = 0 ,a的逆元a-1=n-a,8,4.1 群的概念,证：1)封闭性：2)结合律：成立(TT)T = T
5、(TT) = TTT 3)单位元：T0 = 4)逆元素：Ta的逆元即T-a,9,4.1 群的概念,前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，所以是无限群。 有限群G的元素个数叫做群的阶,记做|G|。 设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。 若群G的任意二元素a,b恒满足ab=ba。则称G为交换群，或Abel群。,10,4.1 群的概念,单位元唯一 e1e2=e2=e1 消去律成立 ab=ac b=c,ba=ca b=c 每个元的逆元唯一 aa-1=a-1a = e,ab-1 = ba-1 = e , aa-1 = ab-1 ,
6、 a-1=b (d)(ab.c)-1 = c-1 b-1a-1 . c-1 b-1a-1.abc = e,11,4.1 群的概念,(e) G有限，aG，则存在最小正整数r，使得ar = e.且a-1 = ar-1 . 证 设|G|=g,则a,a2 ,ag,ag+1G, 由鸽巢原理其中必有相同项。设am =al, 1mlg+1, e=al-m ,1l-mg， 令l-m=r.则有ar =ar-1a=e.即a-1=ar-1. 既然有正整数r使得ar = e,其中必有最小者，不妨仍设为r. r称为a的阶。易见 H=a,a2 ,ar-1 ,ar =e在原有运算下也是一个群。,12,着色问题的等价类,红蓝
7、两种颜色给正方形的四个顶点着色,存在多少种不同的方案?24 若允许正方形转动,有多少种方案? 转动的表示？,Rotate 90o (1234) (4123),1,2,4,3,4,1,3,2,13,4.2 置换群,置换群是最重要的有限群，所有的有限群都可以用之表示。,14,4.2 置换群,置换乘法 P1=( ),P2=( )P1P2=( )( )=( ) P2P1=( )( )=( ).P2P1P1P2. 置换不满足交换律 但是满足结合律,1 2 3 4 3 1 2 4,1 2 3 4 3 1 2 4,1 2 3 4 4 3 2 1,3 1 2 4 2 4 3 1,1 2 3 4 2 4 3 1
8、,1 2 3 4 4 3 2 1,4 3 2 1 4 2 1 3,1 2 3 4 4 2 1 3,15,4.2 置换群,(1)置换群(permutation group) 1,n上的由多个置换组成的集合在上面的乘法定义下构成一个群,则称为置换群。 (a)封闭性 ( )( )=( ) (b)可结合性 ( )( ) ( ) =( )=( )( ) ( ) (c) 有单位元 e=( ) (d) ( )-1 =( ),1 2 n a1 a2 an,a1 a2 an b1 b2 bn,1 2 n b1 b2 bn,1 2 n a1 a2 an,a1 a2 an b1 b2 bn,1 2 n a1 a2
9、an,a1 a2 an b1 b2 bn,1 2 n c1 c2 cn,b1 b2 bn c1 c2 cn,b1 b2 bn c1 c2 cn,1 2 n 1 2 n,1 2 n a1 a2 an,a1 a2 an 1 2 n,16,4.2 置换群,例 等边三角形的转动群。 不动绕中心转动120o绕对称轴翻转。,2,3,17,4.2 置换群,1,n上的所有置换(共n!个)构成一个群，称为n阶对称群(Symmetric group)，记做Sn. 集合1，2，3的三个元素置换群组成S3注意：一般说1,n上的一个置换群，不一定是指Sn.但一定是Sn的某一个子群。,18,4.3循环、奇循环与偶循环,(
10、a1a2am)称为m阶循环；(a1a2am)=(a2a3ama1)=(ama1am-1)有m种表示方法。 若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。 如(132)(45)= (45)(132). 若p=(a1a2an),则pn =(1)(2)(n)=e. 如p=(123) p2=(321) p3=(1)(2)(3),Rotate 90o (1234) (4123) （1-4-3-2-1),1,2,4,3,4,1,3,2,19,4.3循环、奇循环与偶循环,定理 任一置换可表成若干不相交循环的乘积。 证 对给定的任一置换p=( )，从1开始搜索 1ai1ai2aik1得一循环(1
11、 ai1 ai2aik), 若(1 ai1 aik)包含了1,n的所有文字，则命题成立。 否则在余下的文字中选一个，继续搜索,又得一循环。直到所有文字都属于某一循环为止。 因不相交循环可交换，故除了各个循环的顺序外，任一置换都有唯一的循环表示。,1 2 n a1 a2an,20,4.3循环、奇循环与偶循环,共轭类 一般可以把Sn中任意一个置换p分解为若干不相交的循环乘积。 P=(a1 a2ak1)(b1 b2bk2).(h1 h2hkl) 其中k1+k2+kl = n，设k阶循环出现的次数为 ck,用(k)ck表示，则Sn中置换的格式为(1)c1(2)c2(n)cn 例：(1)(2 3)(4
12、5 6 7)的格式是(1)1(2)1(4)1 Sn中有相同格式的置换全体构成一个共轭类。,21,4.3循环、奇循环与偶循环,定理1 Sn中属(1)c1(2)c2 (n)cn共轭类的元素的个数为,证 (1)C1(2)C2(n)Cn 即,()()()() ()(),_ / ,1个,_ / ,2个,_ / ,n个,_ _/,C1个,_ _/,C2个,_ _/,Cn个,(1)一个长度为k的循环有k种表示, (a1a2ak)=(a2a3aka1)=(aka1ak-1) Ck个长度为k的循环重复了kCk次； (2)互不相交的Ck个循环进行全排列有Ck!种表示. 1,2,n的全排列共有n!个，给定一个排列，
13、装入格式得一置换，除以前面的重复度得 n!/(C1!C2!Cn!1C12C2 nCn )个不同的置换.,22,4.3循环、奇循环与偶循环,S4=(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),(123),(124),(132),(134),(142),(143),(234),(243), (1234), (1243), (1324), (1342), (1423),(1432),(12)(34),(13)(24),(14)(23).,例4 S4中 (2)2 共轭类有4!/(2!22 )=3(12)(34),(13)(24),(14)(23). (1)1 (
14、3)1 共轭类有4!/(C1!C3!1131)=8 (123),(124),(132),(134),(142),(143),(234),(243), (1)2 (2)1 共轭类有4!/(2!1!12 21)=6 (12),(13),(14),(23),(24),(34),23,4.3循环、奇循环与偶循环,例 一副扑克牌，一分为二，交错互相插入(洗牌)，这样操作一次相当于一个置换p。,51.5 3 1,52.6 4 2,先放1,再放27,放2,放28,1,27,2,28,3,29,26,52,p = (1) (2 27 14 33 17 9 5 3)(4 28 40 46 49 25 13 7)(6 29 15 8 30 41 21 11)(10 31 16 34 43 22 37 19)(12 32 42 47 24 38 45 23)(18 35)(20 36 44 48 50 51 26 39) (52) 如此操作多少轮，所有的牌又恢复原顺序？ p8 = e,
