离散数学及其应用-屈婉玲-第十二章.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 组合恒等式解题方法小结 证明方法： 已知恒等式带入 二项式定理 幂级数的求导、积分 归纳法 组合分析 求和方法： Pascal公式 级数求和 观察和的结果，然后使用归纳法证明 利用已知的公式 * 非降路径的计数 (0,0) 到 (m,n) 的非降路径数：C(m+n, m) (a,b) 到 (m,n)的非降路径数： 等于 (0,0) 到 (m?a,n?b) 的非降路径数 (a,b) 经过 (c,d) 到 (m,n) 的非降路径数：乘法法则 (m,n) (0,0) * 从(0,0)到(n,n)不接触对角线的非降路径数 N N1：从(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=2[N0 ? N3] (0,0) (1,0) (n,n-1) (n,n) 限制条件的非降路径数 * N3: 从(1,0)到(n,n?1) 接触对角线的 非降路径数 N4: 从(0,1)到(n,n?1) 无限制条件的 非降路径数 关系: N3=N4 一一对应 (1,0) (0,1) (n,n-1) (0,0) (n,n) * 例7 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单调函数数，N? =2N2 严格单调递增函数、递减函数个数都是C(n,m) (1,f(1)) (2,f(2)) (n,f(n)) (n+1,n) (1,1) 应用:单调函数计数 * 栈输出的计数 例8 将1, 2, … , n 按照顺序输入栈，有多少个不同的输 出序列？ 分析：将进栈、出栈分别记作 x, y, 出栈序列是 n个x，n个y 的排列， 排列中任何前缀的 x 个数不少于y 的个数， 等于从(0,0)到 (n,n) 的不穿过对角线的非降路径数 * 输入： 1, 2, 3, 4, 5, 输出 ：3, 2, 4, 1, 5 进,进,进,出,出,进,出,出,进,出 ? x,x,x,y,y,x,y,y,x,y 1 2 5 3 4 栈输出的计数 * 栈输出的计数 从 (0,0)到 (n,n) 的穿 过对角线的非降路径 ?从 (-1,1) 到 (n,n) 的 非降路径 从 (0,0)到 (n,n) 的非降 路径总数为 C(2n,n) 条， 从(-1,1) 到 (n,n) 的非降 路径数为 C(2n,n-1) 条， (n,n) (0,0) (-1,0) (-1,1) * . 定理12.5 设n为正整数，xi为实数，i =1, 2, … , t. 求和是对满足方程n1+n2+…+nt=n的一切非负整数解求 在n个因式中选n1个因式贡献x1,从剩下n?n1个因式选n2 个因式贡献x2, …, 从剩下的n?n1?n2?…?nt?1个因式中选 nt个因式贡献 xt. 证明 展开式中的项 是如下构成的: 12.4 多项式定理 * 推论 推论1 多项式展开式中不同的项数为方程 的非负整数解的个数 C(n+ t ?1,n) 推论2 例9 求 (2x1?3x2+5x3)6 中 x13x2x32 的系数. 解 由多项式定理得 * 多项式系数 组合意义 多项式系数 多重集 S={n1? a1, n2?a2, …, nt ?at } 的全排列数 n个不同的球放到 t 个不同的盒子使得第一个盒子含n1个球，第二个盒子含n2个球，…，第 t 个盒子含 nt 个球的方案数 符号 * 第十二章 习题课 主要内容 基本计数 计数法则：加法法则、乘法法则 计数模型：选取问题、非降路径问题、方程的非负整数 解问题 处理方法：分类处理、分步处理、一一对应思想 计数符号 组合数或二项式系数 C(m,n)：组合恒等式 排列数 P(m,n) 多项式系数 二项式定理与多项式定理 * 基本要求 能够熟练使