《离散数学-8.3-4二项式定理与组合恒等式.ppt》由会员分享，可在线阅读，更多相关《离散数学-8.3-4二项式定理与组合恒等式.ppt（26页珍藏版）》请在三一办公上搜索。
1、1,8.3二项式定理与组合恒等式,8.3.1 二项式定理8.3.2 组合恒等式8.3.3 非降路径问题,2,二项式定理,定理8.5 设 n 是正整数，对一切 x 和 y 证明方法:数学归纳法、组合分析法.证 当乘积被展开时其中的项都是下述形式：xi yni,i=0,1,2,n.而构成形如 xiyni 的项，必须从n 个和(x+y)中选 i 个提供 x，其它的 ni 个提供 y.因此，xiyni 的系数是，定理得证.,3,二项式定理的应用,例1 求在(2x3y)25的展开式中x12y13的系数.解 由二项式定理令i=13 得到展开式中x12y13的系数，即,4,组合恒等式递推式,证明方法：公式代
2、入、组合分析应用：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
3、+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,e a,b,c,d b,c,d b,c,d,e b,c,d 重复度为：应用：将变下限 r 变成常数 k，求和时提到和号外面.,11
4、,恒等式积之和,关系,证明思路：考虑集合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)到(
5、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=2N0 N3,16,一一对应,N3:从(1,0)到(n,n1)接触对角线的 非降路径数N4:从(0,1)到(n,n1)无限制条件的 非降路径数关系:N3=N
6、4,17,应用证明恒等式,例2 证明 证：计数(0,0)到(m+nr,r)的非降路径数按照 k分类，再分步.(0,0)到(mk,k)路径数，(mk,k)到(m+nr,r)的路径数,18,应用单调函数计数,例3 A=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
7、,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,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+t 1,n)推论2,例1 求(2x13x2+5x3)6 中 x13x2x32 的系数.解 由多项式定理得,25,多项式系数,组合意义 多项式系数 多重集 S=n1 a1,n2a2,nt at 的全排列数 n个不同的球放到 t 个不同的盒子使得第一个盒子 含n1个球，第二个盒子含n2个球，第 t 个盒子 含 nt 个球的方案数,26,多项式系数(续),恒等式,推论2,定理8.6,组合证明,
