组合数学 第二章二章六节.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章 递推关系与母函数,2.1,递推关系,2.2,母函数,(,生成函数,),2.3 Fibonacci,数列,2.4,优选法与,Fibonacci,序列的应用,2.5,母函数的性质,2.6,线性常系数齐次递推关系,2.7,关于常系数非齐次递推关系,2.8,整数的拆分,2.9,ferrers,图像,2.10,拆分数估计,2.11,指数型母函数,2.12,广义二项式定理,2.13,应用举例,2.14,非线性递推关系举例,2.15,递推关系解法的补充,1,2.14,非线性递推关系举例,(,一,),多项式展开式的讨论,(,二,),第一类司特林,(,Stirling,),数的讨论,(,三,),第二类司特林,(,Stirling,),数的讨论,2,2.14,非线性递推关系举例,(1),多项式系数,(,x+y),n,展开式的通项,x,k,y,n-k,项的系数是,:,C(n,k,),相当于,2,个不同的球取,n,个作有重复的排列，其中,x,取,k,个，,y,取,n-k,个。,也相当于,n,个不同的球放入,2,个不同盒子，,x,盒子放,k,个，,y,盒子放,n-k,个。,指数型母函数是？,(,一,),多项式展开式的讨论,3,2.14,非线性递推关系举例,(,一,),多项式展开式的讨论,(2),多项式系数和,(,x+y),n,展开式的系数和是,:,2,n,这种情况对应着指数型母函数是？,展开式的过程相当于,两个,不同的元素取,n,个的有重复的排列。,也相当于把,n,个不同的球放进,两个,不同的盒子中。,4,2.14,非线性递推关系举例,(,一,),多项式展开式的讨论,(3),多项式的项数,(,x+y),n,展开式的项数是,n+1,相当于从两个不同元素中取,n,个的组合数，允许重复。,也相当于把,n,个相同的球放进两个不同的盒子中的方案数。,母函数是？,5,定理,2.14 (x,1,+x,2,+,x,m,),n,展开式通项,项数等于,C(m+n-1,n),2.14.1,司特林,(,Stirling,),数,*,系数之和等于,m,n,。,的系数是,:,6,定义,2.14.1,称,s(n,0),s(n,1),s(n,n,),为第一类司特林数。,2.14.1,司特林,(,Stirling,),数,7,其中,x,k,项的系数为,s(n-1,k-1)-(n-1)s(n-1,k),2.14.1,司特林,(,Stirling,),数,递推关系式,s(n,k,)=s(n-1,k-1)-(n-1)s(n-1,k),8,2.14.1,司特林,(,Stirling,),数,递推关系式,s(n,k,)=s(n-1,k-1)-(n-1)s(n-1,k),初始条件：,s(n,0)=0,当,kn,时，,s(n,k,)=0,s(n,n,)=1,*,9,定义,2.14.2 n,个有区别的球放到,m,个相同的盒子中，要求无一空盒，其不同的方案数用,S(n,m,),表示，称为第二类司特林数。,例如：红、黄、蓝,3,种颜色的球,3,个，放到两个无区别的盒子里，不允许空盒。其方案如下：,2.14.1,司特林,(,Stirling,),数,1,2,3,盒,r,y,b,盒,yb,rb,ry,讨论的是生活中的分堆现象,:,与拆分有什么区别？,10,定理,2.14,第二类司特林数,S(n,k,),有以下性质：,2.14.1,司特林,(,Stirling,),数,11,性质,1,的意思是把,n,个不同的球放进,0,个盒子中或把,0,个不同的球放进,n,个盒子的方案数都是,0,。,性质,2,的意思是把,n,个不同的球放进,k,个盒子中,当球等于或多于盒子时，至少有一种方案。,2.14.1,司特林,(,Stirling,),数,12,性质,3,的意思是把,n,个球放进,k,个盒子中,当盒子多于球数时，要想使盒子不空是不可能的。,性质,4,的意思是把,n,个球放进,1,个盒子中,放法只有一种。,性质,5,的意思是把,n,个不同的球放进,n,个相同的盒子中,不允许空盒，放法也只有一种。,2.14.1,司特林,(,Stirling,),数,13,意思是把,n,个不同的球放进,2,个相同的盒子中,当第一个球放进其中一个盒子后，其余,n-1,个有标志的球都有两种选择，一种是选择与第一个球同盒，第二种选择是与第一个球不同盒。共有,2,n-1,种可能，,要排除都放在同一个盒子的情况。因此共有,2,n-1,-1,种方案。,2.14.1,司特林,(,Stirling,),数,14,2.14.1,司特林,(,Stirling,),数,把,n,个有标志的球放进,n-1,个相同的盒子中，因为必须保证每个盒子中都有球，因此只有,1,个盒子中有,2,个球，问题就是求两个球的组合数，因此有,C(n,2),种方案。,15,(1),、剩余的两个球放进一个盒子中，这样的方案对应着从,n,中取,3,个的组合数，是,C(n,3),。,(2),、剩余的两个球放进二个盒子中，这样的方案对应着从,n,中取,4,个，然后再把,4,个球两两分成,2,组，将,4,个球分成两组的方案数是,C(4,2)/2,。,因此在这种情况下方案数是：,C(n,4)C(4,2)/2=3C(n,4),。,例如：,1,2,3,4,分成两两,2,组的方案。,(1,2),(3,4),(1,3),(2,4),(1,4),(2,3),2.14.1,司特林,(,Stirling,),数,16,定理,2.15,第二类司特林数满足下面的递推关系：,证明：设有,n,个有区别的球,b,1,b,2,b,n,对于其中的某一个球,b,i,根据,b,i,的情况分为两类：,1,、,b,i,独占一盒，其方案为,S(n-1,m-1),2,、,b,i,不独占一盒，这相当于先将剩下的,n-1,个球放到,m,个盒子，不允许空盒，共有,S(n-1,m),种不同方案，,2.14.1,司特林,(,Stirling,),数,然后将,b,i,球放进其中一盒，共有,m,种选择方式。,b,i,球不独占一盒的方案数为,mS(n-1,m),17,2.14.1,司特林,(,Stirling,),数,18,2,、,n,个有标志,的球放进,m,个有区别,的盒子，不允许空盒问题,2.14.1,司特林,(,Stirling,),数,1,、,n,个有标志,的球放进,m,个相同,的盒子，不允许空盒问题,n,个有标志的球,b,1,b,2,b,n,，放进有区别的,m,个盒子,c,1,c,2,c,m,中，无一空盒，其方案数为,m!S(n,m,),其中,1mn,19,2.14.1,司特林,(,Stirling,),数,20,n,个球放到,m,个盒子里，则球和盒子是否有区别？是否允许空盒？共有,2,3,=8,种状态，其方案情况如下：,1,、,n,个不同的球放到,m,个不同的盒子里，允许空盒？,2,、,n,个不同的球放到,m,个不同的盒子里，不允许空盒。,有,m,n,个方案。,有,m!S(n,m,),。,2.14.1,司特林,(,Stirling,),数,21,4,、,n,个不同的球放到,m,个相同的盒子里，允许空盒，方案数情况？,S(n,1)+S(n,2)+,S(n,m),nm,S(n,1)+S(n,2)+,S(n,n),nm,。,可分为空,m-1,盒，,m-2,盒，,，空,1,盒，都不空。,3,、,n,个不同的球放到,m,个相同的盒子里，不允许空盒，方案数情况？,有,S(n,m,),2.14.1,司特林,(,Stirling,),数,22,5,、,n,个相同的球放到,m,个不相同的盒子里，允许空盒，方案数情况？,有,C(m+n-1,n),。,6,、,n,个相同的球放到,m,个不相同的盒子里，不允许空盒，方案数情况？,先取,m,个球每盒一个，余下的,n-m,无区别的球放进,m,个不相同的盒子中。则有,C(m+(n-m)-1,n-m)=C(n-1,n-m)=C(n-1,m-1),2.14.1,司特林,(,Stirling,),数,23,7,、,n,个相同的球放到,m,个相同的盒子里，允许空盒，方案数为：,x,n,项系数，相当于,n,用,1,2,m,进行拆分的拆分数。,8,、,n,个相同的球放到,m,个相同的盒子里，不允许空盒，方案数为：,的,x,n,项系数。,2.14.1,司特林,(,Stirling,),数,*,24,2.13,应用举例,错排问题：,若一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排，也叫重排。,1,2,的错排是唯一的,即,21,1,2,3,的错排有,312,231,。,25,2.13,应用举例,对于,1,2,n,，,设,n,个数的错排数为,D,n,综合以上分析得到递推关系：,取,n,分别与其它的,n-1,个数之一互换，其余,n-2,个数进行错排，共得,(n-1)D,n-2,个错排。,1,、与,D,n-1,的关系：,n-1,个数进行错排，然后,n,与其中每一个数互换得到,(n-1)D,n-1,个错排。,2,、与,D,n-2,的关系：,26,2.13,应用举例,27,2.13,应用举例,28,2.13,应用举例,29,2.13,应用举例,例,2.13.1,数,1,2,3,9,的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。,实际上这是一个,13579,的错排问题。,30,2.13,应用举例,例,2.13.2,求在,8,个字母,A,B,C,D,E,F,G,H,的全排列中，只有,4,个元素不在原来位置上的排列数。,从,8,个字母中任取,4,个的组合数为,C(8,4),4,个字母的错排数为：,31,例,2.13.3,求,解：,2.13,应用举例,特解,:,32,2.13,应用举例,33,2.13,应用举例,例,2.13.4 10,个数字,(0,到,9),和,4,个四则运算符（,+,、,-,、,、,）组成的,14,个元素。求由其中的,n,个元素的排列构成一算术表达式的个数。,1,、与,a,n-1,的关系,解：设,n,个元素的算术表达式个数为,a,n,。,10,a,n-1,。,2,、与,a,n-2,的关系,40,a,n-2,。,34,2.13,应用举例,例,2.13.5 n,条直线将平面分成多少个域？假定无三线共点，且两两相交。,设,n,条直线将平面分成,D,n,个域，则第,n,条直线被其余的,n-1,条直线分割成,n,段。这,n,段正好是新增加的,n,个域的边界。,所以：,D,n,=D,n-1,+n,D,1,=2,D,0,=1,35,2.13,应用举例,例,2.13.6,设有,n,条椭圆曲线，两两相交于两点，任意,3,条椭圆曲线不相交于一点，试问这样的,n,个椭圆将平面分隔成多少部分？,一个椭圆将平面分隔成内、外两部分。,a,n,=,a,n-1,+2(n-1),a,1,=2,36,2.13,应用举例,例,2.13.7,一个圆域，依圆心等分成,n,个部分如图所示，用,k,种颜色对这,n,个域进行涂色，要求相邻的域不同色，试问有多少种涂色方案。,设,a,n,表示,n,个域的涂色方案数，分两种情况来讨论。,(1),与,a,n-1,的关系，,(k-2),a,n-1,。,(2),与,a,n-2,的关系，,(k-1),a,n-2,。,37,2.13.8,两名教师分别对,6,名学生进行面试（每位教师各负责一门课）每名学生面试时间固定，试问共有多少种面试的顺序？,解：第一位教师的面试顺序有,6!,种,第一位教师：,a,1,a,2,a,3,a,4,a,5,a,6,第二位教师：,a,2,a,1,a,4,a,3,a,6,a,5,3.3,容斥原理举例,共有,6!265,对第一位教师的任何一种面试顺序，,第二门课的顺序有：,*,38,第,3,章 容斥原理与鸽巢原理,3.1 De Morgan,定理,1,3.2,容斥原理,1,3.3,容斥原理举例,1,3.4,棋盘多项式与有限制的排列,2,3.5,有禁区的排列,2,3.6,广义的容斥原理,3,3.7,广义容斥原理的应用,3,2.8,第二类,Stirling,数的展开式,1,2.9,欧拉函数,(n)1,2.10 n,对夫妻问题,3,*2.11,Mobius,反演定理,2.12,鸽巢原理,4,2.13,鸽巢原理举例,4,2.14,鸽巢原理的推广,4,*2.15 Ramsey,数,39,