清华离散数学(第2版)：(1)ppt课件

1、18.3二项式定理与组合恒等式二项式定理与组合恒等式 8.3.1 二项式定理二项式定理 8.3.2 组合恒等式组合恒等式 8.3.3 非降路径问题非降路径问题2二项式定理二项式定理定理定理8.5 设设 n 是正整数，对一切是正整数，对一切 x 和和 y 证明方法证明方法: 数学归纳法、组合分析法数学归纳法、组合分析法. 证证 当乘积被展开时其中的项都是下述形式：当乘积被展开时其中的项都是下述形式：xi yn i, i = 0, 1, 2, , n. 而构成形如而构成形如 xiyn i 的项，必须从的项，必须从n 个个和和 (x+y) 中选中选 i 个提供个提供 x，其它的，其它的 n i 个提

2、供个提供 y. 因此，因此， xiyn i 的系数是的系数是 ，定理得证，定理得证. nkknknyxknyx0)( in3二项式定理的应用二项式定理的应用例例1 求在求在(2x3y)25的展开式中的展开式中x12y13的系数的系数. 解解 由二项式定理由二项式定理令令i =13 得到展开式中得到展开式中x12y13的系数，即的系数，即 2502525)3()2(25)3(2(iiiyxiyx1312131232!12!13!25)3(21325 4组合恒等式组合恒等式递推式递推式 111. 311. 2. 1knknknknknknknnkn证明方法：公式代入、组合分析证明方法：公式代入、组

3、合分析应用：应用：1式用于化简式用于化简2式用于求和时消去变系数式用于求和时消去变系数3式用于求和时拆项（两项之和或者差），然后合并式用于求和时拆项（两项之和或者差），然后合并5组合恒等式组合恒等式变下项求和变下项求和NnknNnknnkknnk 0)1(. 5,2. 400证明公式证明公式4. 方法：二项式定理或者组合分析方法：二项式定理或者组合分析.设设S=1,2,n，下面计数，下面计数S 的所有子集的所有子集. 一种方法就是分类处理，一种方法就是分类处理，n元集合的元集合的 k子集个数是子集个数是 kn nkkn0根据加法法则，子集总数是根据加法法则，子集总数是另一种方法是分步处理，为构

4、成另一种方法是分步处理，为构成 S 的子集的子集A，每个元素有，每个元素有 2 种选择，根据乘法法则，子集总数是种选择，根据乘法法则，子集总数是2n. 6恒等式求和恒等式求和变系数和变系数和202102)1(. 72. 6 nnknnknnknknknk证明方法：证明方法： 二项式定理、级数求导二项式定理、级数求导 其他组合恒等式代入其他组合恒等式代入7证明公式证明公式6 (二项式定理二项式定理+求导求导)8证明公式证明公式7 (已知恒等式代入已知恒等式代入)9恒等式恒等式变上项求和变上项求和Nknknklnl ,11. 80证明证明 组合分析组合分析. 令令S=a1, a2, , an+1为

5、为n+1元集合元集合. 等式右边是等式右边是 S 的的 k+1子集数子集数. 考虑另一种分类计数的方考虑另一种分类计数的方法法. 将所有的将所有的k+1元子集分成如下元子集分成如下n+1类：类：第第1类：含类：含a1, 剩下剩下 k个元素取自个元素取自a2,an+1 kn kn1 第第2类：不含类：不含a1,含含a2, 剩下剩下k个元素取自个元素取自 a3, , an+1 k0 不含不含a1, a2, , an, 含含an+1,剩下剩下k个元素取自空集个元素取自空集由加法法则公式得证由加法法则公式得证10恒等式恒等式乘积转换式乘积转换式 krknknkrrn. 9证明方法：组合分析证明方法：组

6、合分析. 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，求和时提到和号外面，求和时提到和号外面. krkn11恒等式恒等式积之和积之和NnmmnmknkmnmrNrnmrnmkrnkmnkrk ,.11),min(,.1000 mnmknkmnnmknnkmnknk00

7、关系关系证明思路：考虑集合证明思路：考虑集合A=a1,a2,am，B=b1,b2,bn. 等等式右边计数了从这两个集合中选出式右边计数了从这两个集合中选出r个元素的方法个元素的方法. 将这将这些选法按照含有些选法按照含有A中元素的个数中元素的个数 k 进行分类，进行分类，k=0,1,r. 然后使用加法法则然后使用加法法则. 12组合恒等式解题方法小结组合恒等式解题方法小结证明方法：证明方法： 已知恒等式带入已知恒等式带入 二项式定理二项式定理 幂级数的求导、积分幂级数的求导、积分 归纳法归纳法 组合分析组合分析 求和方法：求和方法： Pascal公式公式 级数求和级数求和 观察和的结果，然后使

8、用归纳法证明观察和的结果，然后使用归纳法证明 利用已知的公式利用已知的公式13非降路径问题非降路径问题 基本计数模型基本计数模型 限制条件下的非降路径数限制条件下的非降路径数 非降路径模型的应用非降路径模型的应用 证明恒等式证明恒等式 单调函数计数单调函数计数 栈的输出栈的输出 14基本计数模型基本计数模型(0,0) 到到 (m,n) 的非降路径数：的非降路径数：C(m+n, m)(a,b) 到到 (m,n)的非降路径数：的非降路径数：等于等于 (0,0) 到到 (m a,n b) 的非降路径数的非降路径数(a,b) 经过经过 (c,d) 到到 (m,n) 的非降路径数：乘法法则的非降路径数：

9、乘法法则15限制条件的非降路径数限制条件的非降路径数从从(0,0)到到( (n,n)不接触对角线的非降路径数不接触对角线的非降路径数 NN1：从从(0,0) 到到 (n,n) 下不接触对角下不接触对角 线非降路径数线非降路径数N2：从从(1,0)到到(n,n 1) 下不接触对角下不接触对角 线非降路径数线非降路径数N0: 从从(1,0)到到(n,n 1) 的非降路径数的非降路径数N3: 从从(1,0)到到(n,n 1) 接触对角线的接触对角线的 非降路径数非降路径数关系关系: N=2N1=2N2=2N0 N3 16 122222122 2 24030nnnnnnnNNNNN一一对应一一对应N3

10、: 从从(1,0)到到(n,n 1) 接触对角线的接触对角线的 非降路径数非降路径数N4: 从从(0,1)到到(n,n 1) 无限制条件的无限制条件的 非降路径数非降路径数关系关系: N3=N4 17应用应用证明恒等式证明恒等式例例2 证明证明 证：证：计数计数(0,0)到到(m+n r,r) )的非降路径数的非降路径数按照按照 k分类，再分步分类，再分步. (0,0)到到(m k,k)路径数，路径数，(m k,k)到到(m+n r,r)的的路径数路径数 rnmkrnkmrk 018应用应用单调函数计数单调函数计数例例3 A=1,2,m, B=1,2,n，N1:B上单调递增函数个上单调递增函数

11、个 数是数是(1,1)到到 (n+1,n) 的非降路径数的非降路径数N: B上单调函数个数上单调函数个数 N=2N1N2: A到到B单调递增函数个单调递增函数个 数是从数是从(1,1)到到 (m+1,n) 的非降路径数的非降路径数 N : A到到B的单调函数个数，的单调函数个数，N =2N2 严格单调递增函数、递减函数个数都是严格单调递增函数、递减函数个数都是C(n,m) nnN122 mnmN1219函数计数小结函数计数小结A = 1, 2, , m, B = 1, 2, , nf: AB20应用应用栈输出的计数栈输出的计数例例4 将将1,2,n按照顺序输入栈按照顺序输入栈,有多少个不同的输

12、出序列？有多少个不同的输出序列？解：将进栈、出栈分别记作解：将进栈、出栈分别记作 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, 521应用应用栈输出的计数栈输出的计数(续续)N: 堆栈输出个数堆栈输出个数N :(0,0)到到(n,n)不不 穿过

13、对角线的穿过对角线的 非降路径数非降路径数N0:(0,0)到到(n,n)的的 非降路径总数非降路径总数N1:(0,0)到到(n,n)的的 穿过对角线的穿过对角线的 非降路径数非降路径数N2:( 1,1)到到(n,n) 的非降路径数的非降路径数. 关系：关系：N=N =N0 N1, N1=N2 nnnnnnnnnnnnnN211)!1()!1()!2(!)!2(12222 8.4.1 多项式定理多项式定理 8.4.2 多项式系数多项式系数8.4 多项式定理多项式定理23多项式定理多项式定理. 定理定理8.6 设设n为正整数，为正整数，xi为实数，为实数，i =1, 2, , t. tntnntn

14、txxxnnnnxxx.21212121求和是对满足方程求和是对满足方程n1+n2+nt=n的一切非负整数解求的一切非负整数解求 ttttnnnnnnnnnnnnnnnnn.!.!.212111211在在n个因式中选个因式中选n1个因式贡献个因式贡献x1,从剩下从剩下n n1个因式选个因式选n2个因式贡献个因式贡献x2, , 从剩下的从剩下的n n1 n2 nt 1个因式中选个因式中选 nt个因式贡献个因式贡献 xt. tntnnx.xx2121证明证明 展开式中的项展开式中的项是如下构成的是如下构成的:24推论推论推论推论1 多项式展开式中不同的项数为方程多项式展开式中不同的项数为方程 的非负整数解的个数的非负整数解的个数 C(n+ t 1,n) 推论推论2 nttnnnn .21nnnnt .21例例1 求求 (2x1 3x2+5x3)6 中中 x13x2x32 的系数的系数. 解解 由多项式定理得由多项式定理得3600025)3(8! 2! 1! 3! 65)3(2213623 25多项式系数多项式系数组合意义组合意义 多项式系数多项式系数 多重集多重集 S=n1 a1, n2 a2, , nt at 的全排列数的全排列数