资源描述
1,8.3二项式定理与组合恒等式,8.3.1二项式定理8.3.2组合恒等式8.3.3非降路径问题,2,二项式定理,定理8.5设n是正整数，对一切x和y证明方法:数学归纳法、组合分析法.证当乘积被展开时其中的项都是下述形式：xiyni,i=0,1,2,n.而构成形如xiyni的项，必须从n个和(x+y)中选i个提供x，其它的ni个提供y.因此，xiyni的系数是，定理得证.,3,二项式定理的应用,例1求在(2x3y)25的展开式中x12y13的系数.解由二项式定理令i=13得到展开式中x12y13的系数，即,4,组合恒等式递推式,证明方法：公式代入、组合分析应用：1式用于化简2式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并,5,组合恒等式变下项求和,证明公式4.方法：二项式定理或者组合分析.设S=1,2,n，下面计数S的所有子集.一种方法就是分类处理，n元集合的k子集个数是,根据加法法则，子集总数是,另一种方法是分步处理，为构成S的子集A，每个元素有2种选择，根据乘法法则，子集总数是2n.,6,恒等式求和变系数和,证明方法：二项式定理、级数求导其他组合恒等式代入,7,证明公式6(二项式定理+求导),8,证明公式7(已知恒等式代入),9,恒等式变上项求和,证明组合分析.令S=a1,a2,an+1为n+1元集合.等式右边是S的k+1子集数.考虑另一种分类计数的方法.将所有的k+1元子集分成如下n+1类：第1类：含a1,剩下k个元素取自a2,an+1,第2类：不含a1,含a2,剩下k个元素取自a3,an+1,不含a1,a2,an,含an+1,剩下k个元素取自空集,由加法法则公式得证,10,恒等式乘积转换式,证明方法：组合分析.n元集中选取r个元素，然后在这r个元素中再选k个元素.不同的r元子集可能选出相同的k子集，例如a,b,c,d,ea,b,c,db,c,db,c,d,eb,c,d重复度为：应用：将变下限r变成常数k，求和时提到和号外面.,11,恒等式积之和,关系,证明思路：考虑集合A=a1,a2,am，B=b1,b2,bn.等式右边计数了从这两个集合中选出r个元素的方法.将这些选法按照含有A中元素的个数k进行分类，k=0,1,r.然后使用加法法则.,12,组合恒等式解题方法小结,证明方法：已知恒等式带入二项式定理幂级数的求导、积分归纳法组合分析求和方法：Pascal公式级数求和观察和的结果，然后使用归纳法证明利用已知的公式,13,非降路径问题,基本计数模型限制条件下的非降路径数非降路径模型的应用证明恒等式单调函数计数栈的输出,14,基本计数模型,(0,0)到(m,n)的非降路径数：C(m+n,m)(a,b)到(m,n)的非降路径数：等于(0,0)到(ma,nb)的非降路径数(a,b)经过(c,d)到(m,n)的非降路径数：乘法法则,15,限制条件的非降路径数,从(0,0)到(n,n)不接触对角线的非降路径数NN1：从(0,0)到(n,n)下不接触对角线非降路径数N2：从(1,0)到(n,n1)下不接触对角线非降路径数N0:从(1,0)到(n,n1)的非降路径数N3:从(1,0)到(n,n1)接触对角线的非降路径数关系:N=2N1=2N2=2N0N3,16,一一对应,N3:从(1,0)到(n,n1)接触对角线的非降路径数N4:从(0,1)到(n,n1)无限制条件的非降路径数关系:N3=N4,17,应用证明恒等式,例2证明证：计数(0,0)到(m+nr,r)的非降路径数按照k分类，再分步.(0,0)到(mk,k)路径数，(mk,k)到(m+nr,r)的路径数,18,应用单调函数计数,例3A=1,2,m,B=1,2,n，N1:B上单调递增函数个数是(1,1)到(n+1,n)的非降路径数N:B上单调函数个数N=2N1N2:A到B单调递增函数个数是从(1,1)到(m+1,n)的非降路径数N:A到B的单调函数个数，N=2N2严格单调递增函数、递减函数个数都是C(n,m),19,函数计数小结,A=1,2,m,B=1,2,nf:AB,20,应用栈输出的计数,例4将1,2,n按照顺序输入栈,有多少个不同的输出序列？解：将进栈、出栈分别记作x,y,出栈序列是n个x，n个y的排列，排列中任何前缀的x个数不少于y的个数.等于从(0,0)到(n,n)的不穿过对角线的非降路径数.实例：n=5x,x,x,y,y,x,y,y,x,y进,进,进,出,出,进,出,出,进,出3,2,4,1,5,21,应用栈输出的计数(续),N:堆栈输出个数N:(0,0)到(n,n)不穿过对角线的非降路径数N0:(0,0)到(n,n)的非降路径总数N1:(0,0)到(n,n)的穿过对角线的非降路径数N2:(1,1)到(n,n)的非降路径数.关系：N=N=N0N1,N1=N2,22,8.4.1多项式定理8.4.2多项式系数,8.4多项式定理,23,多项式定理,.,24,推论,推论1多项式展开式中不同的项数为方程的非负整数解的个数C(n+t1,n)推论2,例1求(2x13x2+5x3)6中x13x2x32的系数.解由多项式定理得,25,多项式系数,组合意义多项式系数多重集S=n1a1,n2a2,ntat的全排列数n个不同的球放到t个不同的盒子使得第一个盒子含n1个球，第二个盒子含n2个球，第t个盒子含nt个球的方案数,26,多项式系数(续),恒等式,推论2,定理8.6,组合证明,
展开阅读全文