组合数学1省公开课一等奖全国示范课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基本组合数学,第1页,组合数学介绍,组合数学起源于古老数学娱乐和游戏。而在当今社会中一样发挥着主要作用。,组合数学研究一个集合物体进行满足一些规则排列。详细说，组合数学研究是这些排列存在性、计数和分类。,在ACM/ICPC中用到组合数学知识有：,一一对应原理、加法乘法原理、多重集排列和组合、排列生成、递推关系、母函数、鸽巢原理、容斥原理、群和置换群、贝恩塞特引理和波利亚定理,第2页,一一对应原理,“一一对应”概念是一个在计数中极为基本概念。一一对应既是单射又是满射。,如我们说,A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应关系。,在组累计数时往往借助于一一对应实现模型转换。,比如要对A集累计数，但直接计数有困难，于是可设法结构一易于计数B，使得A与B一一对应。,第3页,例 在100名选手之间进行淘汰赛(即一场比赛结果，失败者退出比赛),最终产生一名冠军，问要举行几场比赛？,一一对应,例 含有n个元素集合全部子集个数为2,n,解 一个常见思绪是按轮计场，费事。,另一个思绪是,淘汰选手,与,比赛(按场计),集,一一对应,。99场比赛。,第4页,一一对应,例：求集合1,2,n不含相邻整数,k元子集个数。,分析：每个满足条件k元子集都和一个01,有序串对应，且这个有序串没有两1相邻。这么串含有k个1，每个1前面0个数,是不一样，又与0,1,n-k中选k个不一样,元素对应。所以结果=,c(n-k+1,k),第5页,某机要部门安装了电子锁。M(M8)工作人员每人发一张磁卡，卡上有开锁密码特征。为了确保安全，要求最少要有N(N=0),一个非负整数解对应。,x,1,+x,2,+x,k,=r,一个非负整数解r,1,(k-1)*,一个排列对应。,第14页,例 令S是含有4种元素a,b,c,d多重集,10a,10b,10c,10d,求S使得4种元素,每一个都最少出现一次,10-组合,数目是多少？,多重集组合,分析：相当于求从多重集6-组合，即,数目=C(6+4-1,4),第15页,例 求方程,x,1,+x,2,+x,3,+x,4,=20,整数解个数？,其中x,1,=3,x,2,=1,x,3,=0,x,4,=5,例 某餐厅有7种不一样菜，为了招待朋友，一个用户需要买14个菜，问有多少,种买法？,第16页,r个无区分球，放进n个有标志盒子，,每个盒子中可多于一个，则共有,C(n+r-1,r),种方案。,注：,盒子,i,中放进几个球，,i,就被重复了几次。,比如：试问(x+y+z),4,有多少项？,分析：（x+y+z)(x+y+z)(x+y+z)(x+y+z),相当于,4个无区分球放进3个盒子里,比如：,(x,1,+x,2,+x,r,),n,有多少项？,x,y,z,多重集组合应用,第17页,全排列生成算法,就是对于给定字符集，用有效方法将全部可能全排列,无重复无遗漏,地枚举出来。,全排列生成算法,这里介绍全排列算法三种：,(,A)字典序法,(B)序数法,(C)邻位对换法,第18页,先学习一个整数表示法。,n!=(n-1)(n-1)!+(n-1)!,(n-1)!=(n-2)(n-2)!+(n-2)!,.,3!=2*2!+2!,所以,n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+2*2!+2,2.9.2 序数法,第19页,0到n!-1之间任一整数m可唯一表示成,m=a,n-1,(n-1)!+a,n-2,(n-2)!+a,1,1!,m与序列a,n-1,a,n-2,a,1,)一一对应,n个元素全排列与0,n!-1一一对应,n个元素全排列与(a,n-1,a,n-2,a,1,)一一对应,2.9.2 序数法,第20页,怎样求与m对应序列(a,n-1,a,n-2,a,1,)？,m除以2余数为a,1,商为b,1,b,1,除以3余数为a,2,商为b,2,b,2,除以4余数为a,3,商为b,3,b,n-2,除以n余数为a,n-1,.,n个元素全排列与(a,n-1,a,n-2,a,1,)一一对应,2.9.2 序数法,第21页,怎样求与序列(a,n-1,a,n-2,a,1,)对应全排列？,a,i,表示,i+1,所在位置,右边比i+1小,数个数,所以,0=a,i,i全部i,a,i,=0,改变a,j+1,。,组合生成算法,（全部）,第26页,1,2,nr-组合第一个是,1,2,r,，,最终一个是,n-r+1,n-r+2,n.,只要一个组合c,1,c,2,c,r,中存在,c,j,n)for(i=0;i=n;i+),c1i=0;c2i=0;,for(i=0;i=n;i+)c1i=1;,for(i=2;i=n;i+)for(j=0;j=n;j+)for(k=0;k+j=n;k+=i)c2j+k+=c1j;for(j=0;j=n;j+)c1j=c2j;c2j=0;coutc1nn&n!=0),for(i=0;i=n;i+),c1i=1;c2i=0for(i=2;i=17;i+),for(j=0;j=n;j+),for(k=0;k+j=n;k+=i*i),c2j+k+=c1j;,for(j=0;j=n;j+),c1j=c2j;c2j=0;,coutc1nn&n!=0),for(i=0;i=n;i+),c1i=1;c2i=0;,for(,i=2;i=17;,i+),for(j=0;j=n;j+),for(k=0;k+j=n;,k+=elemi-1,),c2j+k+=c1j;,for(j=0;j=n;j+),c1j=c2j;c2j=0;,coutc1n,r1,则,m,1,m,n,最少有一个,大于,r,m,1,+m,n,n,第55页,鸽巢原理一个例子,定理,若序列,S=a,1,a,2,a,nn+1,中各,数是不等n,是正整数，则 S有一长,度为n+1严格增子序列或长度为n+1减,子序列,第56页,容斥原理两个基本公式,第57页,容斥原理指就是以上,两个基本,公式。,4.2 容斥原理两个基本公式,第58页,例3,从(0,0)到(10,5)点路径中不通,过AB,CD,EF,GH中任一条路径路径数,4.3 应用举,例,(0,0),(10,5),A,B,C,D,E,F,G,H,第59页,某人写了n封信和n个信封，假如全部信都装错了信封。求全部信都装错信封,共有多少种不一样情况。,1465 不轻易系列之一,第60页,小于n且与n互素数有多少个？,第61页,如图是一个国际象棋棋盘。两个象互不攻击当且仅当它们不处于同一条斜线上。在一个n*n(n=30)棋盘上放k个互不攻击象有多少种方法？,第62页,棋盘多项式,第63页,我们把棋盘形状推广到任意形状：,布子要求称为无对攻规则，任意两棋子不放在同行同列上。,令,r,k,（C）表示,k个棋子布到棋盘C上,方案数。如：,第64页,r,1,()=1，,r,1,()=2，,r,1,()=2，,r,2,()=0，,r,2,()=1。,为了形象化起见，（）中图象便是棋盘,形状。,第65页,定义,设,C为一棋盘，称R(C)=r,k,(C)x,k,为C,棋盘多项式。,要求,r,0,(C)=1,，包含,C=时。,设C,i,是棋盘,C某一指定格子所在行与,列都去掉后所得棋盘；C,e,是仅去掉该,格子后棋盘。,在上面定义下，显然有,r,k,(C)=r,k1,(C,i,)r,k,(C,e,)，,k=0,第66页,第67页,比如：,R()=1+x；,R()=xR()+R()=x+(1+x)=1+2x；,R()=x R()+R(),=x(1+x)+1+x,=1+2x+x,2,第68页,假如,C由相互分离C,1,，C,2,组成，即,C,1,任一格子所在行和列中都没有C,2,格,子。则有：,r,k,(C)=r,i,(C,1,)r,ki,(C,2,),i=0,k,故,R(C)=(r,i,(C,1,)r,ki,(C,2,)x,k,=(r,i,(C,1,)x,i,)(r,j,(C,2,)x,j,),j=0,n,n,k,n,i=0,i=0,k=0,R(C)=R(C,1,)R(C,2,),第69页,利用前述R(C)两式，能够把一个比较,复杂棋盘逐步分解成相对比较简单棋,盘，从而得到其棋盘多项式。,例,R()=xR()+R(),=x(1+x),2,+(1+2x),2,=1+5x+6x,2,+x,3,*,R()=xR()+R(),=1+6x+10 x,2,+4x,3,*,第70页,其中有红色格子表示,禁区。,R()=1+6x+10 x,2,+4x,3,方案数=4!6(41)!+10(42)!4(43)!0(44)!=4,第71页,群概念,定义：给定,(G,),，若满足以下4个条件：,（1）封闭性,若a,bG,则abG,（2）结合律,（3）存在单位元素,（4）存在逆元素,就叫,群,。,群元素个数叫,有限群,，有限群元素个数,叫,群阶,。满足交换律群叫,阿贝尔群,。,例（R,+）是群。（R-0,）是群。,第72页,置换群,置换可视为集合1,2,n到其本身一个,一对一函数.,置换,复合,运算定义为,则,第73页,循环、换位,置换 可表示为,叫做n阶循环。比如，,第74页,比如，,1,4,5,6,9,2,3,7,8,循环只与元素相邻情况相关，而与哪个元素,为首无关。,定理：,任何一个置换都能够表示成,若干循环乘积。,第75页,定义：2阶循环(ij)叫作i和j,换位,。,定理：任何一个循环都可表示成若干,换位之积。,如(123n)=(12)(13)(1n),可用数学归纳法证实此定理。,1,2,3,4,5,6,7,8,2,1,3,4,5,6,7,8,第76页,置换群应用举例,佳佳最喜欢与老师和小搭档们一起玩传球游戏。游戏开始时全部儿童分成两组，每组n人，围成一个圈。每个儿童都有一个编号(1n)这个编号在其所在组是唯一。游戏开始之前，每个儿童都有一个球，球上有编号(1.n)，而且一个组中球不会有两个相同编号。然后，全部儿童必须闭上研究，游戏开始。伴随老师口中哨子发出节奏，每个儿童都用一只手把球传到右边，而用另一只手接左边来球。,突然，老师哨子停了，关键时刻到了。儿童马上睁开眼睛，开始与同组儿童进行传球，争取以最短时间把球传到位。传到位是指一个组中每一个儿童手上球编号与他自己编号相同。最终获胜就是那个最先把球传到位组,第77页,这个游戏非常有趣，儿童们玩了许屡次。聪明佳佳总结出一条经验：总是两个人之间对传。,现在需要你写一个程序，帮助儿童们确定传球方法。,问题：最少需要几次对传才能将球传到位,问题：最少需要多少时间才能将球传到位。每一个时间单位一个儿童能够不做任何动作，也能够与另一个儿童之间进行对传,第78页,你弟弟有一项家庭作业需要你帮助完成。老师给了他一列数，需要他半这些数按升序排列。你能够每次交换两个数位置，而一次交换代价被定义成交换两个数和。写一个程序，用最小交换代价和来帮助弟弟完成这项无聊排序工作,置换群应用举例,第79页,贝恩塞特引理,设 是X=1,2,n上置换群，,G对X所划分不一样等价类个数为,其中,c,1,(g,k,)为置换g,k,中1阶循环个数，即在g,k,作用下保持不变元素个数。,如,G=e,(12),(34),(12)(34)，则等价类个数为,(4+2+2+0)/4=2。,第80页,贝恩塞特引理应用举例,例1 有一图案有三个花瓣和一个中心圆组成，用,两种颜色对这4部分进行着色，问能得到多少种不一样,图象？注意：经旋转重合方案为同一个方案。,第81页,c,1,c,2,c,3,c,4,c,5,c,6,c,7,c,8,c,9,c,10,c,11,c,12,c,13,c,14,c,15,c,16,第82页,分析：每个图都绕中心轴逆时针方向旋转0,120,240度，可得16种方案3种置换,（1）旋转0度,p,1,=(c,1,)(c,2,)(c,3,)(c,4,)(c,5,)(c,6,)(c,7,)(c,8,)(c,9,)(c,10,)(c,11,),(c,12,)(c,13,)(c,14,)(c,15,)(c,16,),（2）旋转120度,p,2,=(c,1,)(c,2,)(c,3,c,4,c,5,)(c,6,)(c,7,c,8,c,9,)(c,10,c,11,c,12,),(c,13,c,14,c,15,)(c,16,),（3）旋转240度,p,3,=(c,1,)(c,2,)(c,3,c,5,c,4,)(c,6,)(c,7,c,9,c,8,)(c,10,c,12,c,11,),(c,13,c,15,c,14,)(c,16,),不一样等价类个数=(16+4+4)/3=8,第83页,波利亚定理,定理：,设G=g,1,g,2,g,n,是X一个置换，C是,X一个m-着色集而且使得G中任意f与C中任,意c，f*c属于C，则C中不等价着色数为,其中c(g,i,)表示置换g,i,循环个数。,第84页,例：圆圈上有3个珠子，组成等边三角形，对,3个珠子用红色、兰色和绿色着色，问有多少,种不一样方案？,分析：绕圆心旋转0、120、240度可形成3个置,换；沿过3个顶点中线翻转又可形成3个置换,故不一样方案数为(27+3+3+9+9+9)/6,第85页,例：用5个,和4个,对3*3格子进行布子，,试问有多少种不一样布局，旋转翻转使之重,合作为一个方案。,1,2,3,4,5,6,7,8,9,解：旋转翻转形成置换群为,(1)(2)(3)(4)(5)(6)(7)(8)(9),(4)(5)(6)(17)(28)(39),(2)(5)(8)(13)(46)(79),(1)(5)(9)(24)(37)(68),(3)(5)(7)(26)(19)(48),(5)(1793)(2486),(5)(1397)(2684),(5)(19)(37)(28)(46),第86页,波利亚定理应用,镶嵌着灿烂宝石手镯是珠宝厂生产特殊产品。伴随珠宝生产商业化，相同手镯越来越廉价，但个性化手镯越来越值钱。所以厂商尽可能依据客户需求生产镶嵌不一样宝石手镯。一天，珠宝厂经理问自己：“用相同方式能生产多少不一样类手镯呢？”也就是说，假如手镯有n个位置可用来嵌入宝石，有m种宝石可用来嵌入，能生产出多少不一样类手镯？,第87页,