组合数学7

1组合数学Combinatorics7群7-1可以转的世界清华大学马昱春黑板上的排列组合用六种不同颜色涂一正方体，一面一色，且每面颜色不同，会有多少种涂法？用六种不同颜色涂一正方体，一面一色，不同面可以同色，会有多少种涂法？6*5*P(4,4)/4/6=30计数法则•组合计数中遇到的困难–找出问题通解的表达式困难•引入母函数–区分讨论的问题类型困难,区分同类性,避免重复和遗漏•容斥原理避免重复计数•如何区分同类可以转的世界？？4可以转的世界•举例–红蓝两种颜色给正方形的四个顶点着色,存在多少种不同的方案?24Quiz–若允许正方形转动,有多少种方案?•分类：按红色点分类•0个红点1种•1个红点1种•2个红点2种•3个红点1种•4个红点1种共6种•1832年的某个清晨……•革命中的法国见证了又一次决斗……•在某个瞬间，某位青年被对手的枪射中腹部，随后去世……•整个世界又失去了一个伟大的头脑。•这位21岁的青年姓伽罗华……群(group)6伽罗华（Galois）•ÉvaristeGalois(1811~1832)•引入群论新名词并奠定了群论基础•非常彻底地把全部代数方程可解性问题，转化或归结为置换群及其子群结构分析的问题,得出五次以上一般代数方程根式不可解，以及用圆规、直尺(无刻度的尺)三等分任意角和作倍立方体不可能等结论。•刘维尔在1846才领悟到其手稿中迸发出的天才思想，他花了几个月的时间试图解释它的意义•他被公认为数学史上两个最具浪漫主义色彩的人物之一•他的死使数学的发展被推迟了几十年•这个人是上帝派来的，在人世间匆匆转了一圈，仅仅21年，却一不小心，开启了数学的一个新时代……..伽罗华在圣佩拉吉监狱中写成的研究报告中写道：“把数学运算归类，学会按照难易程度，而不是按照它们的外部特征加以分类，这就是我所理解的未来数学家的任务，这就是我所要走的道路。”8群的概念群(group)定义给定集合G和G上的二元运算·，满足下列条件称为群。(a)封闭性(Closure)：若a,b∈G,则存在c∈G,使得a·b=c.(b)结合律(Associativity)：任意a,b,c∈G,有(a·b)·c=a·(b·c).由于结合律成立，(a·b)·c=a·(b·c)可记做a·b·c.(c)有单位元(Identity)：存在e∈G,任意a∈G.a·e=e·a=a.(d)有逆元(Inverse)：任意a∈G,存在b∈G,a·b=b·a=e.记为b=a-1.9群的概念例1*1=?G={1}在普通乘法下是群例G={1,-1}在普通乘法下是群。证：1)封闭性：1×1=1(-1)×(-1)=1(-1)×1=-11×(-1)=-12)结合律：成立3)单位元：14)逆元素：1的逆元是1，-1的逆元是-1例G={0,1,2,…,n-1}在modn的加法下是群.证：1)封闭性：除以n的余数只能是{0,1,2,…,n-1}，故封闭性成立2)结合律：成立3)单位元：04)逆元素：对任意元素a有(a+(n-a))modn=0,a的逆元a-1=n-a11群的概念证：1)封闭性：TbTa=cosbsinbcosasina-sinbcosb-sinacosa=cosacosb-sinasinbsinacosb+cosasinb-sinacosb-cosasinbcosacosb-sinasinb=cos(a+b)sin(a+b)=T(b+a)-sin(a+b)cos(a+b)例二维欧氏空间所有刚体旋转T={Ta}构成群。其中Ta=cosasina-sinacosa1)封闭性：2)结合律：成立(TαTβ)Tγ=Tα(TβTγ)=TαTβTγ3)单位元：T0=4)逆元素：Ta的逆元即T-a100113群的概念•群元素的个数是有限的，是有限群；•群元素的个数是无限的，是无限群。•有限群G的元素个数叫做群的阶,记做|G|。•设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。•若群G的任意二元素a,b恒满足ab=ba。则称G为交换群，或Abel群。14群的概念(a)单位元唯一e1e2=e2=e1(b)消去律成立ab=ac→b=c,ba=ca→b=c(c)每个元的逆元唯一aa-1=a-1a=e,ab-1=ba-1=e,aa-1=ab-1,a-1=b(d)(ab….c)-1=c-1…b-1a-1.c-1…b-1a-1.ab…c=e15群的概念(e)G有限，a∈G，则存在最小正整数r，使得ar=e.且a-1=ar-1.证设|G|=g,则a,a2,…,ag,ag+1∈G,由鸽巢原理其中必有相同项。设am=al,1≤m＜l≤g+1,e=al-m,1≤l-m≤g，令l-m=r.则有ar=ar-1a=e.即a-1=ar-1.既然有正整数r使得ar=e,其中必有最小者，不妨仍设为r.r称为a的阶。易见H={a,a2,…ar-1,ar=e}在原有运算下也是一个群。16组合数学Combinatorics7群7-2置换群清华大学马昱春17着色问题的等价类–红蓝两种颜色给正方形的四个顶点着色,存在多少种不同的方案?24–若允许正方形转动,有多少种方案?–转动的表示？Rotate90o(1234)→(4123)12434132如何表示？18置换群•置换群是最重要的有限群，所有的有限群都可以用之表示。12…na1a2…an•置换：[1,n]到自身的1-1映射称为n阶置换。[1,n]目标集上的置换表示为(),a1a2…an是[1,n]中元的一个排列。1234312431422341•n阶置换共有n!个，同一置换用这样的表示可有n!个表示法。例如p1=()=()，n阶置换又可看作[1,n]上的一元运算，一元函数。置换群:置换集合和二元运算19置换群•置换乘法P1=(),P2=()P1P2=()()=()P2P1=()()=().•P2P1≠P1P2.•置换不满足交换律•但是满足结合律123431241234312412344321312424311234243112344321432142131234421320置换群•(1)置换群(permutationgroup)[1,n]上的由多个置换组成的集合在上面的乘法定义下构成一个群,则称为置换群。•(a)封闭性()()=()•(b)可结合性•(()())()=()=()(()())•(c)有单位元e=()•(d)逆元()-1=()12…na1a2…ana1a2…anb1b2…bn12…nb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…na1a2…ana1a2…anb1b2…bn12…nc1c2…cnb1b2…bnc1c2…cnb1b2…bnc1c2…cn12…n12…n12…na1a2…ana1a2…an12…n21置换群•例等边三角形的转动群。•不动•绕中心转动±120o•绕对称轴翻转。123123P1=(),123312P3=(),P2=(),123231123132P4=(),123321P5=(),123213P6=(),1231231232322置换群•[1,n]上的所有置换(共n!个)构成一个群，称为n阶对称群(Symmetricgroup)，记做Sn.•集合{1，2，3}的三个元素置换群组成S3•注意：一般说[1,n]上的一个置换群，不一定是指Sn,但一定是Sn的某一个子群。P1=()P2=()P3=()123123123123231312P4=()P5=()P6=()12312312313232121323循环、奇循环与偶循环•(a1a2…am)称为m阶循环；(a1a2…am)=(a2a3…ama1)=…=(ama1…am-1)有m种表示方法。•若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。•如(132)(45)=(45)(132).•若p=(a1a2…an),则pn=(1)(2)…(n)=e.–如p=(123)p2=(321)p3=(1)(2)(3)123454315212345312541234552314•于是()=(14523)()=(132)(45),()=(154)(2)(3).a1a2…am-1ama2a3…ama1(a1a2…am)=()称为置换的循环表示。Rotate90o（1-4-3-2-1)124341321234412324循环、奇循环与偶循环•定理任一置换可表示成若干不相交循环的乘积。•证对给定的任一置换p=()，从1开始搜索•1→ai1→ai2→…→aik→1得一循环(1ai1ai2…aik),•若(1ai1…aik)包含了[1,n]的所有文字，则命题成立。•否则在余下的文字中选一个，继续搜索,又得一循环。直到所有文字都属于某一循环为止。因不相交循环可交换，故除了各个循环的顺序外，任一置换都有唯一的循环表示。12…na1a2…anppppp25循环、奇循环与偶循环•共轭类一般可以把Sn中任意一个置换p分解为若干不相交的循环乘积。P=(a1a2…ak1)(b1b2…bk2)….(h1h2…hkl)其中k1+k2+…+kl=n，设k阶循环出现的次数为ck,用(k)ck表示，则Sn中置换的格式为(1)c1(2)c2…(n)cn∑k*ck=nnk=126循环、奇循环与偶循环•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)}.例：(1)(23)(4567)的格式是(1)1(2)1(4)1•Sn中有相同格式的置换全体构成一个共轭类。••例S4中(2)2共轭类有3个(12)(34),(13)(24),(14)(23).(1)1(3)1共轭类有8个(123),(124),(132),(134),(142),(143),(234),(243),27循环、奇循环与偶循环例一副扑克牌，一分为二，交错互相插入(洗牌)，这样操作一次相当于一个置换p。i=p(i+1)/2,i=1,3,5,…,51.i/2+26,i=2,4,6,…,52.p=(),第i个位置被i号牌占据.iipp51...53152...642先放1,再放27,放2,放28………1272283292652如此操作多少轮，所有的牌又恢复原顺序？p=(1)(227143317953)(42840464925137)(62915830412111)(1031163443223719)(1232424724384523)(1835)(2036444850512639)(52)p8=e1阶循环2个2阶循环1个8阶循环6个28循环、奇循环与偶循环•2阶循环叫做对换•定理任一循环都可以表示为对换的积。•(12…n)=(12)(13)…(1n)•证明：设（12…n-1)=(12)(13)…(1n-1)•(123…n-1)(1n)•每个置换的分解形式不是唯一的•(12…n)=(23)(24)…(2n)(21)•(123)=(12)(13)=(12)(13)(31)(13)123…n-1123…n-1n234…..1n23…n-11=()()123…n-1n23…n-11n234…..1n23…n-1n1=()()123…n-1n234…..n1=()=(123….n)123231=123213123321=(12)(13)29循环、奇循环与偶循环•任一置换表示成对换的个数的奇偶性是唯一•证明：设f的表达式为设l,k(lk)为正整数常数，则有其中A为不含有xk和xl项的部分若将l和k换位，(lk)f=-f每次对换都改变f的符号，则对应的分解的奇偶性是唯一的。f=∏(xi-xj)ijf=(xl-xk)A∏(xi-xl)(xi-xk)i≠l,k30循环、奇循环与偶循环置换