《离散数学--8.3-4二项式定理与组合恒等式》由会员分享，可在线阅读，更多相关《离散数学--8.3-4二项式定理与组合恒等式（26页珍藏版）》请在金锄头文库上搜索。
1、8.3二项式定理与组合恒等式 8.3.1 二项式定理 8.3.2 组合恒等式 8.3.3 非降路径问题1二项式定理定理8.5 设 n 是正整数，对一切 x 和 y证明方法: 数学归纳法、组合分析法. 证 当乘积被展开时其中的项都是下述形式：xi yni, i = 0, 1, 2, , n. 而构成形如 xiyni 的项，必须从n 个和 (x+y) 中选 i 个提供 x，其它的 ni 个提供 y. 因此， xiyni 的系数是 ，定理得证. 2二项式定理的应用例1 求在(2x3y)25的展开式中x12y13的系数. 解 由二项式定理令i =13 得到展开式中x12y13的系数，即3组合恒等式递推
2、式证明方法：公式代入、组合分析 应用： 1式用于化简 2式用于求和时消去变系数 3式用于求和时拆项（两项之和或者差），然后合并4组合恒等式变下项求和证证明公式4. 方法：二项项式定理或者组组合分析. 设设S=1,2,n，下面计计数S 的所有子集. 一种方法就是分类处类处 理，n元集合的 k子集个数是根据加法法则，子集总数是另一种方法是分步处理，为构成 S 的子集A，每个元素有 2 种选择，根据乘法法则，子集总数是2n. 5恒等式求和变系数和证明方法：二项式定理、级数求导其他组合恒等式代入6证明公式6 (二项式定理+求导)7证明公式7 (已知恒等式代入)8恒等式变上项求和证证明 组组合分析. 令
3、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个元素取自空集由加法法则公式得证 9恒等式乘积转换式证明方法：组合分析. n 元集中选取 r 个元素，然后在这 r 个元素中再选 k个 元素. 不同的 r 元子集可能选出相同的 k子集，例如 a, b, c, d, e a, b, c, d b, c, d b,
4、 c, d, e b, c, d 重复度为：应用：将变下限 r 变成常数 k，求和时提到和号外面. 10恒等式积之和关系证证明思路：考虑虑集合A=a1,a2,am，B=b1,b2,bn. 等 式右边计边计 数了从这这两个集合中选选出r个元素的方法. 将这这 些选选法按照含有A中元素的个数 k 进进行分类类，k=0,1,r. 然后使用加法法则则. 11组合恒等式解题方法小结证明方法：已知恒等式带入二项式定理幂级数的求导、积分归纳法组合分析求和方法：Pascal公式级数求和观察和的结果，然后使用归纳法证明利用已知的公式 12非降路径问题 基本计数模型 限制条件下的非降路径数 非降路径模型的应用 证
5、明恒等式 单调函数计数 栈的输出 13基本计数模型(0,0) 到 (m,n) 的非降路径数：C(m+n, m) (a,b) 到 (m,n)的非降路径数： 等于 (0,0) 到 (ma,nb) 的非降路径数 (a,b) 经过 (c,d) 到 (m,n) 的非降路径数：乘法法则14限制条件的非降路径数从(0,0)到(n,n)不接触对角线的非降路径数 N N1：从(0,0) 到 (n,n)下不接触对角线非降路径数 N2：从(1,0)到(n,n1)下不接触对角线非降路径数 N0: 从(1,0)到(n,n1)的非降路径数 N3: 从(1,0)到(n,n1)接触对角线的非降路径数 关系: N=2N1=2N
6、2=2N0 N3 15一一对应N3: 从(1,0)到(n,n1)接触对角线的非降路径数 N4: 从(0,1)到(n,n1)无限制条件的非降路径数 关系: N3=N416应用证明恒等式例2 证明 证： 计数(0,0)到(m+nr,r) 的非降路径数 按照 k分类，再分步. (0,0)到(mk,k)路径数， (mk,k)到(m+nr,r)的 路径数17应用单调函数计数例3 A=1,2,m, B=1,2,n， N1:B上单调递增函数个数是(1,1)到 (n+1,n)的非降路径数 N: B上单调函数个数N=2N1 N2: A到B单调递增函数个数是从(1,1)到 (m+1,n)的非降路径数 N: A到B
7、的单调函数个数，N =2N2严格单调递增函数、递减函数个数都是C(n,m) 18函数计数小结A = 1, 2, , m, B = 1, 2, , n f: AB19应用栈输出的计数例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, 520应用栈输出的计数(续)N: 堆栈输出个
8、数 N:(0,0)到(n,n)不穿过对角线的非降路径数 N0:(0,0)到(n,n)的非降路径总数 N1:(0,0)到(n,n)的穿过对角线的非降路径数 N2:(1,1)到(n,n)的非降路径数. 关系：N=N =N0N1, N1=N221 8.4.1 多项式定理 8.4.2 多项式系数8.4 多项式定理22多项式定理. 定理8.6 设n为正整数，xi为实数，i =1, 2, , t. 求和是对满足方程n1+n2+nt=n的一切非负整数解求在n个因式中选选n1个因式贡贡献x1,从剩下nn1个因式选选n2 个因式贡贡献x2, , 从剩下的nn1n2nt1个因式中选选nt个因式贡贡献 xt. 证明 展开式中的项是如下构成的:23推论推论1 多项式展开式中不同的项数为方程的非负整数解的个数 C(n+ t 1,n) 推论2 例1 求 (2x13x2+5x3)6 中 x13x2x32 的系数. 解 由多项式定理得24多项式系数组合意义 多项式系数 多重集 S=n1 a1, n2a2, , nt at 的全排列数 n个不同的球放到 t 个不同的盒子使得第一个盒子 含n1个球，第二个盒子含n2个球，第 t 个盒子 含 nt 个球的方案数25多项式系数(续)恒等式推论2定理8.6组合证明26
