资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,8.3,二项式定理与组合恒等式,8.3.1,二项式定理,8.3.2,组合恒等式,8.3.3,非降路径问题,1,二项式定理,定理,8.5,设,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,的系数是 ，定理得证,.,2,二项式定理的应用,例,1,求在,(2,x,3,y,),25,的展开式中,x,12,y,13,的系数,.,解 由二项式定理,令,i,=13,得到展开式中,x,12,y,13,的系数，即,3,组合恒等式,递推式,证明方法：公式代入、组合分析,应用：,1,式用于化简,2,式用于求和时消去变系数,3,式用于求和时拆项（两项之和或者差），然后合并,4,组合恒等式,变下项求和,证明公式,4.,方法：二项式定理或者组合分析,.,设,S,=1,2,n,，下面计数,S,的所有子集,.,一种方法就是分类处理，,n,元集合的,k,子集个数是,根据加法法则，子集总数是,另一种方法是分步处理，为构成,S,的子集,A,，每个元素有,2,种选择，根据乘法法则，子集总数是,2,n,.,5,恒等式求和,变系数和,证明方法：,二项式定理、级数求导,其他组合恒等式代入,6,证明公式,6 (,二项式定理,+,求导,),7,证明公式,7 (,已知恒等式代入,),8,恒等式,变上项求和,证明,组合分析,.,令,S,=,a,1,a,2, ,a,n,+1,为,n,+1,元集合,.,等式右边是,S,的,k,+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,个元素取自空集,由加法法则公式得证,9,恒等式,乘积转换式,证明方法：组合分析,.,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,，求和时提到和号外面,.,10,恒等式,积之和,关系,证,明思路：考虑集合,A,=,a,1,a,2,a,m,，,B,=,b,1,b,2,b,n,.,等,式右边计数了从这两个集合中选出,r,个元素的方法,.,将这,些选法按照含有,A,中元素的个数,k,进行分类，,k,=0,1,r,.,然后使用加法法则,.,11,组合恒等式解题方法小结,证明方法：,已知恒等式带入,二项式定理,幂级数的求导、积分,归纳法,组合分析,求和方法：,Pascal,公式,级数求和,观察和的结果，然后使用归纳法证明,利用已知的公式,12,非降路径问题,基本计数模型,限制条件下的非降路径数,非降路径模型的应用,证明恒等式,单调函数计数,栈的输出,13,基本计数模型,(0,0),到,(,m,n,),的非降路径数：,C,(,m+n,m,),(,a,b,),到,(,m,n,),的非降路径数：,等于,(0,0),到,(,m,a,n,b,),的非降路径数,(,a,b,),经过,(,c,d,),到,(,m,n,),的非降路径数：乘法法则,14,限制条件的非降路径数,从,(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,15,一一对应,N,3,:,从,(1,0),到,(,n,n,1),接触对角线的,非降路径数,N,4,:,从,(0,1),到,(,n,n,1),无限制条件的,非降路径数,关系,:,N,3,=,N,4,16,应用,证明恒等式,例,2,证明,证：,计数,(0,0),到,(,m+n,r,r,),的非降路径数,按照,k,分类，再分步,.,(0,0),到,(,m,k,k,),路径数，,(,m,k,k,),到,(,m,+,n,r,r,),的路径数,17,应用,单调函数计数,例,3,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,),18,函数计数小结,A,= 1, 2, ,m,B,= 1, 2, ,n,f,:,A,B,19,应用,栈输出的计数,例,4,将,1,2,n,按照顺序输入栈,有多少个不同的输出序列？,解：将进栈、出栈分别记作,x,y,出栈序列是,n,个,x,，,n,个,y,的排列，排列中任何前缀的,x,个数不少于,y,的个数,.,等于从,(0,0),到,(,n,n,),的不穿过对角线的非降路径数,.,实例：,n,=5,x, x, x ,y, y, x, y, y, x, y,进,进,进,出,出,进,出,出,进,出,3, 2, 4, 1, 5,20,应用,栈输出的计数,(,续,),N,:,堆栈输出个数,N,:(,0,0),到,(,n,n,),不,穿过对角线的,非降路径数,N,0,:(0,0),到,(,n,n,),的,非降路径总数,N,1,:(0,0),到,(,n,n,),的,穿过对角线的,非降路径数,N,2,:,(,1,1),到,(,n,n,),的非降路径数,.,关系：,N,=,N,=,N,0,N,1,N,1,=,N,2,21,8.4.1,多项式定理,8.4.2,多项式系数,8.4,多项式定理,22,多项式定理,.,定理,8.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,.,证明 展开式中的项,是如下构成的,:,23,推论,推论,1,多项式展开式中不同的项数为方程,的非负整数解的个数,C,(,n,+ t,1,n,),推论,2,例,1,求,(2,x,1,3,x,2,+5,x,3,),6,中,x,1,3,x,2,x,3,2,的系数,.,解 由多项式定理得,24,多项式系数,组合意义,多项式系数,多重集,S,=,n,1,a,1,n,2,a,2, ,n,t,a,t,的全排列数,n,个不同的球放到,t,个不同的盒子使得第一个盒子,含,n,1,个球，第二个盒子含,n,2,个球，,，第,t,个盒子,含,n,t,个球的方案数,25,多项式系数,(,续,),恒等式,推论,2,定理,8.6,组合证明,26,
展开阅读全文