离散数学第十二章-基本的组合计数公式省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,组合数学研究内容,组合存在性,组累计数,组合枚举,组合优化,本书内容,基本组累计数公式,递推方程与生成函数,第四部分 组合数学,1/59,1,第十二章 基本组累计数公式,主要内容,加法法则与乘法法则,排列与组合,二项式定理与组合恒等式,多项式定理,2/59,2,12.1,加法法则与乘法法则,加法法则,乘法法则,分类处理与分步处理,3/59,3,加法法则,加法法则,：事件,A,有,m,种产生方式，事件,B,有,n,种产生方式，则“事件,A,或,B,”有,m+n,种产生方式.,使用条件：事件,A,与,B,产生方式不重合,适用问题：分类选取,推广：事件,A,1,有,p,1,种产生方式，事件,A,2,有,p,2,种产生方式，,事件,A,k,有,p,k,种产生方式，则“事件,A,1,或,A,2,或,A,k,”有,p,1,+,p,2,+,p,k,种产生方式.,4/59,4,乘法法则,乘法法则,：事件,A,有,m,种产生方式，事件,B,有,n,种产生方式，则“事件,A,与,B,”有,m n,种产生方式.,使用条件：事件,A,与,B,产生方式彼此独立,适用问题：分步选取,推广：事件,A,1,有,p,1,种产生方式，事件,A,2,有,p,2,种产生方式，,事件,A,k,有,p,k,种产生方式则“事件,A,1,与,A,2,与,A,k,”有,p,1,p,2,p,k,种产生方式.,5/59,5,分类处理与分步处理,分类处理：对产生方式集合进行划分，分别计数，然后使用加法法则,分步处理：一个产生方式分解为若干独立步骤，对每步分别进行计数，然后使用乘法法则,分类与分步结合使用,先分类，每类内部分步,先分步，每步又分类,6/59,6,实例,例1,设A，使个城市，从到有条道路，从到有条道路，从直接到有条道路，问从到有多少种不一样方式？,解：,7/59,7,实例：关系计数,例,设,A,为,n,元集，问,(1),A,上自反关系有多少个？,(2),A,上对称关系有多少个？,(3),A,上反对称关系有多少个？,(4),A,上函数有多少个？其中双射函数有多少个？,.,(2),考虑对称关系矩阵.,i,行,j,列(,i,j,)元素,r,ij,=r,ji,.能够独立,选择0或1位置有(,n,2,n,)/2个.加上主对角线,n,个位置，总计,(,n,2,+,n,)/2个位置，每个位置2种选择，依据乘法法则，组成矩,阵方法数是,(1)在自反关系矩阵中，主对角线元素都是1，其它位置元,素能够是1，也能够是0，有2种选择.这种位置有,n,2,n,个，根,据乘法法则，自反关系个数,8/59,8,解答,(3)非主对角线位置分成(,n,2,n,)/2组，每组包含元素,r,ij,和,r,ji,.根,据反对称性质r,ij,与,r,ji,取值有以下3种可能：,r,ij,=1,r,ji,=0；,r,ij,=0,r,ji,=1；,r,ij,=,r,ji,=0.,全部这些位置元素选择方法数为 .再考虑到主对角,线元素选取，由乘法法则总方法数为,(4)设,A,=,x,1,x,2,x,n,，任何,A,上函数,f,:,A,A,含有下述形式：,f,=,其中每个,y,i,（,i,=1,2,n,）有,n,种可能选择，依据乘法法则，,有,n,n,个不一样函数.若,f,是双射，那么,y,1,确定以后，,y,2,只有,n,1种可能取值,y,n,只有1种取值.组成双射函数方法数,是,n,(,n,1)(,n,2)1=,n,!.9/59,9,A,0,netid (7位),hostid (24位),B,1,0,netid(14位),hostid,(,16位),C,1,1,0,netid(21位),hostid,(,8,位),D,1,1,1,0,(28位),E,1,1,1,1,0,(27位),例：Ipv4网址计数,32位地址 网络标识+主机标识,(1)A类：最大网络；B类：中等网络；C：小网络；,D：多路广播；E：备用,(2)限制条件：,1111111在A类中netid部分无效,hostid部分不允许全0或全1,10/59,10,netid hostid,A类：0+7位，24位,B类：10+14位，16位,C类：11021位，8位,限制条件：1111111在A类中netid部分无效,hostid部分不允许全0或全1,A类：netid 2,7,1,hosted 2,24,2，,N,A,127,167772142130706178,B类：netid 2,14,hosted 2,16,2，,N,B,16384,655341073709056,C类：netid 2,21,hosted 2,8,2,N,C,2097152,254532676608,N,N,A,+,N,B,+,N,C,3737091842,解答,11/59,11,选取问题：设,n,元集合,S,，从,S,中选取,r,个元素.,依据是否有序,是否允许重复将该问题分为四个子类型,不重复选取,重复选取,有序选取,集合排列,多重集排列,无序选取,集合组合,多重集组合,12.2,排列与组合,12/59,12,定义12.1,设,S,为,n,元集，,(1)从,S,中有序选取,r,个元素称为,S,一个,r,排列,，,S,不一样,r,排列总数记作,P,(,n,r,),r,=,n,排列是,S,全排列.,(2)从,S,中无序选取,r,个元素称为,S,一个,r,组合，,S,不一样,r,组合总数记作,C,(,n,r,),集合排列,定理1.1,设,n,r,为自然数，要求0!=1，则,13/59,13,下面考虑,n,r,情况.,(1)排列第一个元素有,n,种选择方式.排列第二个元素有,n,1种选法,第,r,个元素方式数,n,r,+1.依据乘法法则，总选法数为,n,(,n,1)(,n,2)(,n,r,+1)=,(2)分两步组成,r,排列.首先无序地选出,r,个元素，然后再结构这,r,个元素全排列.无序选择,r,个元素方法数是,C,(,n,r,)；针对每种选法，能结构,r,!个不一样全排列.依据乘法法则，不一样,r,排列数满足,P,(,n,r,)=,C,(,n,r,),r,!,组合数,C,(,n,r,)也称为,二项式系数,，记作,证实,14/59,14,推论,设,n,r,为正整数，则,(,1),C,(,n,r,)=,(2),C,(,n,r,)=,C,(,n,nr,),(3),C,(,n,r,)=,C,(,n,1,r,1)+,C,(,n,1,r,),推论,例3,证实,C,(,n,r,)=,C,(,n,n,r,),证 设,S,=1,2,n,是,n,元集合，对于,S,任意,r,组合,A,=,a,1,a,2,a,r,，都存在一个,S,n,r,组合,S,A,与之对应.显然不一样,r,组合对应了不一样,n,r,组合，反之也对，所以,S,r,组合数恰好与,S,n,r,组合数相等.,公式(3),称为,Pascal公式,，也对应了,杨辉三角形,证实方法：公式代入并化简，组合证实,15/59,15,杨辉三角,1,1,1,1,2,1,1,3,3,1,1,4,6,4,15,10,10,1,1,6,15,20,5,15,6,1,1,n,=0,n,=1,n,=2,n,=3,n,=4,n,=5,n,=6,r,=0,r,=1,r,=2,r,=3,r,=4,r,=5,r,=6,16/59,16,多重集排列与组合,定义12.2,多重集,S,=,n,1,a,1,n,2,a,2,n,k,a,k,，,n,=,n,1,+,n,2,+,n,k,表,示,S,中元素总数.,(1)从,S,中有序选取,r,个元素称为多重集,S,一个,r,排列,.,r,=,n,排列称为,S,全排列,(2)从,S,中无序选取,r,个元素称作多重集,S,一个,r,组合,注意：,多重集中元素重复度，0,n,i当,n,i,+，表示,a,i,重复选取次数没有限制,S,子集,X,=,x,1,a,1,x,2,a,2,x,k,a,k,其中0,x,i,+,17/59,17,多重集排列计数,定理12.2,设,S,=,n,1,a,1,n,2,a,2,n,k,a,k,为多重集，,(1),S,全排列数是,(2)若,r,n,i,，,i,=1,2,k,，那么,S,r,排列数是,k,r,证实 (1)有,C,(,n,n,1,)种方法放,a,1,，有,C,(,n,n,1,n,2,)种方法放,a,2,最终有,C,(,n,n,1,n,2,n,k,1,n,k,)方法放,a,k,.依据乘法法则,(2),r,个位置中每个位置都有,k,种选法，由乘法法则得,k,r,18/59,18,多重集组合,定理12.3,多重集,S,=,n,1,a,1,n,2,a,2,n,k,a,k,，0,n,i,+,当,r,n,i,Sr,组合数为,N,=,C,(,k+r,1,r,),证实 一个,r,组合为,x,1,a,1,x,2,a,2,x,k,a,k,，,其中,x,1,+,x,2,+,x,k,=,r,x,i,为非负整数.这个不定方程非负整数解对应于下述排列,11 0 11 0 11 0 0 11,x,1,个,x,2,个,x,3,个,x,k,个,r,个1，,k,1个 0 全排列数为,19/59,19,公式小结,()多重集,n,1,a,1,n,2,a2,n,k,a,k,全排列数是,(4)多重集,S,=,n,1,a,1,n,2,a,2,n,k,a,k,，0,n,i,+,当,r,n,i,Sr,组合数为,N,=,C,(,k+r,1,r,),20/59,20,例3,排列26个字母，使得,a,与,b,之间恰有7个字母，求方法数.,解 固定,a,和,b,中间选7个字母，有2,P,(24,7)种方法，,将它看作大字母与其余17个字母全排列有18！种，共,N,=2,P,(24,7)18!,组累计数应用,解 相当于2,n,不一样球放到,n,个相同盒子，每个盒子2个，放法为,例4,把 2,n,个人分成,n,组，每组2人，有多少分法？,21/59,21,解 使用一一对应思想求解这个问题.,a,1,a,2,a,k,：,k,个不相邻数,属于集合1,2,n,b,1,b,2,b,k,：,k,个允许相邻数,属于集合,1,n,(,k,1),对应规则是,b,i,=,a,i,(,i,1).,i,=1,2,k,所以,N=C,(,n,k+,1,k,),例5,从,S,=1,2,n,中选择,k,个不相邻数，有多少种方法？,一一对应技巧,22/59,22,主要内容,二项式定理,组合恒等式,非降路径问题,12.3,二项式定理与组合恒等式,23/59,23,二项式定理,定理,12.4,设,n,是正整数，对一切,x,和,y,证实方法:数学归纳法、组合分析法.,证 当乘积被展开时其中项都是下述形式：,x,i,y,n,i,i,=0,1,2,n,.而组成形如,x,i,y,n,i,项，必须从,n,个,和(,x,+,y,)中选,i,个提供,x,，其它,n,i,个提供,y,.所以，,x,i,y,n,i,系数是 ，定理得证.,24/59,24,二项式定理应用,解 由二项式定理,令,i,=13 得到展开式中,x,12,y,13,系数，即,例6,求在(2,x,3,y,),25,展开式中,x,12,y,13,系数.,25/59,25,组合恒等式：递推式,证实方法：公式代入、组合分析,应用：,1式用于化简,2式用于求和时消去变系数,3式用于求和时拆项（两项之和或者差），然后合并,26/59,26,组合恒等式：基本求和式,证实公式4.方法：二项式定理或者组合分析.,设,S,=1,2,n,，下面计数,S,全部子集.,一个方法就是分类处理，,n,元集合,k,子集个数是,依据加法法则，子集总数是,另一个方法是分步处理，为组成,S,子集,A,，每个元素有 2 种选择，依据乘法法则，子集总数是2,n,.,27/59,27,恒等式求和:变系数和,证实方法：,二项式定理、级数求导,其它组合恒等式代入,28/59,28,证实公式,6,29/59,29,证实公式7,30/59,30,恒等式:变上项求和,证实,组合分析.令,S,=,a,1,a,2,a,n,+1,为,n,+1元集合.,等式右边是,Sk,+1子集数.考虑另一个分类计数方,法.将全部,k,+1元子集分成以下,n,+1类：,第1类：含,a,1,剩下,k,个元素取自,a,2,a,n,+1,第2类：不含,a,1,含,a,2,剩下,k,个元素取自,a,3,a,n,+1,不含,a,1,a,2,a,n,含,a,n,+1,剩下,k,个元素取自空集,由加法法则公式得证,31/59,31,恒等式:乘积转换式,证实方法：组合分析.,n,元集中选取,r,个元素，然后在这,r,个元素中再选,k,个,元素.不一样,r,元子集可能选出相同,k,子集，比如,a,b,c,d,e,a,b,c,d,b,c,d,b,c,d,e,b,c,d,重复度为：,应用：将变下限,r,变成常数,k,，求和时提到和号外面.,32/59,32,恒等式:积之和,关系,证,明思绪：考虑集合,A,=,a,1,a,2,a,m,，,B,=,b,1,b,2,b,n,.等,式右边计数了从这两个集合中选出,r,个元素方法.将这,些选法按照含有,A,中元素个数,k,进行分类，,k,=0,1,r,.,然后使用加法法则.,33/59,33,组合恒等式解题方法小结,证实方法：,已知恒等式带入,二项式定理,幂级数求导、积分,归纳法,组合分析,求和方法：,Pascal公式,级数求和,观察和结果，然后使用归纳法证实,利用已知公式,34/59,34,非降路径计数,(0,0)到(,m,n,)非降路径数：,C,(,m+n,m,),(,a,b,)到(,m,n,)非降路径数：,等于(0,0)到(,m,a,n,b,)非降路径数,(,a,b,)经过(,c,d,)到(,m,n,)非降路径数：乘法法则,(,m,n,),(0,0),35/59,35,从,(0,0),到(,n,n,),不接触对角线非降路径数,N,N,1：,从(0,0)到(,n,n,),下不接触对角,线非降路径数,N,2：,从(1,0)到(,n,n,1),下不接触对角,线非降路径数,N,0,:从(1,0)到(,n,n,1),非降路径数,N,3,:从(1,0)到(,n,n,1),接触对角线,非降路径数,关系:,N,=2,N,1,=2,N,2,2,N,0,N,3,(0,0),(1,0),(,n,n,-1),(,n,n,),限制条件非降路径数,36/59,36,N,3,:从(1,0)到(,n,n,1),接触对角线,非降路径数,N,4,:从(0,1)到(,n,n,1),无限制条件,非降路径数,关系:,N,3,=,N,4,一一对应,(1,0),(0,1),(,n,n,-1),(0,0),(,n,n,),37/59,37,例7,A,=1,2,m,B,=1,2,n,，,N,1,:,B,上单调递增函数个,数是(1,1)到(,n,+1,n,),非降路径数,N,:,B,上单调函数个数,N,=2,N,1,N,2,:,A,到,B,单调递增函数个,数是从(1,1)到(,m,+1,n,),非降路径数,N,:,A,到,B,单调函数数，,N,=2,N,2,严格单调递增函数、递减函数个数都是,C,(,n,m,),(1,f,(1),(2,f,(2),(,n,f,(,n,),(,n+,1,n,),(1,1),应用:单调函数计数,38/59,38,栈输出计数,例8,将1,2,n,按照次序输入栈，有多少个不一样输,出序列？,分析：将进栈、出栈分别记作,x,y,出栈序列是,n,个,x,，,n,个,y,排列，,排列中任何前缀,x,个数不少于,y,个数，,等于从(0,0)到(,n,n,)不穿过对角线非降路径数,39/59,39,输入：,1,2,3,4,5,输出,3,2,4,1,5,进,进,进,出,出,进,出,出,进,出,x,x,x,y,y,x,y,y,x,y,1,2,5,3,4,栈输出计数,40/59,40,栈输出计数,从(0,0)到(,n,n,)穿,过对角线非降路径,从,(-1,1)到(,n,n,),非降路径,从(0,0)到(,n,n,)非降,路径总数为 C(2,n,n,)条，,从(-1,1)到(,n,n,)非降,路径数为 C(2,n,n,-1)条，,(,n,n,),(,0,0,),(-1,0,),(-1,1,),41/59,41,A,=1,2,m,B,=1,2,n,f,:,A,B,函数计数小结,42/59,42,.,定理12.6,设,n,为正整数，,x,i,为实数，,i,=1,2,t,.,求和是对满足方程,n,1,+,n,2,+,n,t,=,n,一切非负整数解求,在,n,个因式中选,n,1,个因式贡献,x,1,从剩下,n,n,1,个因式选,n,2,个因式贡献,x,2,从剩下,n,n,1,n,2,n,t,1,个因式中选,n,t,个因式贡献,x,t,.,证实 展开式中项,是以下组成:,12.4 多项式,定理,43/59,43,推论,推论1,多项式展开式中不一样项数为方程,非负整数解个数,C,(,n+t,1,n,),推论2,例9,求(2,x,1,3,x,2,+5,x,3,),6,中,x,1,3,x,2,x,3,2,系数.,解 由多项式定理得,44/59,44,多项式系数,组合意义,多项式系数,多重集,S,=,n,1,a,1,n,2,a,2,n,t,a,t,全排列数,n,个不一样球放到,t,个不一样盒子使得第一个盒子含,n,1,个球，第二个盒子含,n,2,个球，第,t,个盒子含,n,t,个球方案数,符号,45/59,45,第十二章 习题课,主要内容,基本计数,计数法则：加法法则、乘法法则,计数模型：选取问题、非降路径问题、方程非负整数,解问题,处理方法：分类处理、分步处理、一一对应思想,计数符号,组合数或二项式系数,C,(,m,n,),：组合恒等式,排列数,P,(,m,n,),多项式系数,二项式定理与多项式定理,46/59,46,基本要求,能够熟练使用加法法则与乘法法则,熟悉和应用基本组累计数模型：,选取问题,不等方程解,非降路径,熟悉二项式定理与多项式定理,能证实组合恒等式并对二项式系数进行求和,了解多项式系数及其相关公式,47/59,47,练习,1,：,基本组累计数,1.求1400不一样正因子个数.,解,1400,素因子分解式是,1400=2,3,5,2,7,1400,任何正因子都含有下述形式：,2,i,5,j,7,k,，其中,0,i,3,0,j,2,0,k,1.,依据乘法法则，,1400,正因子数是,i,j,k,选法数,N,=(1+3)(1+2)(1+1)=24.,48/59,48,练习,2,：基本组累计数,2把10个不一样球放到6个不一样盒子里，允许空盒，且前,2个盒子球总数至多是4，问有多少种方法？,解 依据前两个盒子含球数,k,对放法分类，其中,k,=0,1,2,3,4.,对于给定,k,，再分步处理计算放球方法数：,从10个球中选放入前两个盒子,k,个球，有,C,(10,k,)选法；,把选好,k,个球分到2个盒子里，每个球能够有2种选择，,有2,k,种分法；,剩下,n,k,个球分到其它4个盒子里有4,n,k,种分法.,依据乘法法则，使得前两个盒子含,k,个球放法数是,C,(10,k,)2,k,4,n,k,最终使用加法法则对,k,求和，就得到所求方法数是,49/59,49,3由,m,个,A,和n,个,B,组成序列，其中,m,n,为正整数，,m,n,.如,果要求每个,A,后面最少紧跟着1个,B,问有多少个不一样序列？,3.方法一.先放,n,个,B,，只有1种方法.然后，在每个,B,之间,n,个位置中选择,m,个位置放,A,有,C,(,n,m,)种方法.,练习,3,：基本组累计数,方法二.先放,m,个,AB,，只有1 种方法.把每个,AB,看作格板，,m,个格板组成,m,+1个空格，在空格中放入,n,m,个,B,.这相当,于方程,x,1,+,x,2,+,x,m,+1,=,n,m,非负整数解个数，所以,N,=,C,(,n,m,+,m,+1,1,n,m,)=,C,(,n,n,m,)=,Cn,m,),50/59,50,练习,4,方法一.令|,A,|=,k,，按照,k,=0,1,n,将有序对分类.,给定,k,，选,A,方法数是,C,(,n,k,)；,选,B,中剩下,n,k,个元素,每个元素有2 种选法，有2,n,k,个,不一样,B,集合.由乘法法则，这么有,C,(,n,k,)2,n,k,个，,再使用加法法则和二项式定理，从而得到,4.设,S,是,n,元集，,N,表示满足,A,B,S,有序对 个数，用二项式定理证实,N,=3,n,方法二.,S,中每个元素能够有3种选法：同时加入,A,和,B,，不,加入,A,但加入,B,，,A,和,B,都不加入；所以，,n,个元素总共,3,n,种选法.,51/59,51,练习,5,5.,证实,方法一.利用已知等式,将上述两式相加得,52/59,52,练习,5,方法二 利用积分,53/59,53,练习,6,6.求和,54/59,54,主要内容,递推方程定义及实例,递推方程公式解法,递推方程其它解法,生成函数及其应用,指数生成函数及其应用,Catalan数与Stirling数,第十三章 递推方程与生成函数,55/59,55,13.1,递推方程定义及实例,定义13.1,设序列,a,0,a,1,a,n,简记为,a,n,.一个把,a,n,与,一些个,a,i,(,i,n,)联络起来等式叫做关于序列,a,n,递推方,程,.当给定递推方程和适当初值就唯一确定了序列.,Fibonacci数列,：,1，1，2，3，5，8，记作,f,n,.,递推方程,f,n,=,f,n,1,+,f,n,2,初值,f,0,=1，,f,1,=1,阶乘计算数列：1，2，6，24，5！，,记作,F,(,n,),递推方程,F,(,n,)=,nF,(,n,1),初值,F,(1)=1,56/59,56,例1,从,A,柱将这些圆盘移到,C,柱上去.假如把一个圆盘从,一个柱子移到另一个柱子称作一次移动，在移动和放置,时允许使用,B,柱，但不允许大圆盘放到小圆盘上面.问,把全部圆盘从,A,移到,C,总计需要多少次移动？,初值是,T,(1)=1,可证实解是,T,(,n,)=2,n1,移,动,n,个盘子总次数为,T,(,n,).,所以得到递推方程,T,(,n,)=2,T,(,n,1)+1.,递推方程实例:,Hanoi,塔,57/59,57,两个排序算法,归并算法 Mergesort(,A,p,r,)/对,A,下标,p,到,r,之间数排序,1.if,p,0 and,A,i,key,5.do,A,i,+1,A,i,;,i,i,1,7.,A,i,+1,key,58/59,58,递推方程实例:算法分析,例2,哪种排序算法在最坏情况下复杂度比较低？,插入排序，归并排序,插入排序,W,(,n,)=,W,(,n,1)+,n,1,W,(1)=0,解得,W,(,n,)=,O,(,n,2,).,归并排序，不妨设,n,=2,k,.,W,(,n,)=2,W,(,n,/2)+,n,1,W,(1)=0,解得,W,(,n,)=,O,(,n,log,n,),59/59,59,