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

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 7．用三个1、两个2、五个3可以组成多少个不同的四位数？如果这个四位数是偶数，那么又有多少个？ 练习7 其中x4的系数为 因此 a4=71. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 分治算法的时间分析 T(n)为算法对规模为n的输入的时间复杂度, a为子问题个数，n/b为子问题规模, d(n)为划分和综合过程的工作量 * 当d(n)=c时，代入上式得到 当d(n)=cn时，代入上式得到 * 分治算法的时间分析（续） * 13.4 生成函数及其应用 牛顿二项式系数与牛顿二项式定理 生成函数的定义 生成函数的应用 * 牛顿二项式系数 定义13.5 设 r 为实数，n为整数，引入形式符号 称为牛顿二项式系数. 实例 * 牛顿二项式定理 定理13.6 （牛顿二项式定理） 设?为实数，则对一切实数x, y，|x/y|1，有 若?= ?m，其中m为正整数，那么 * 重要展开式 令x=z，y=1，那么牛顿二项式定理就变成 在上面式子中用?z代替 z ，则有 * 生成函数定义 定义13.6 设序列{an}，构造形式幂级数 G(x) = a0 + a1x + a2x2 +… + an xn + … 称G(x)为序列{an}的生成函数. 例如， { C(m,n) }的生成函数为 (1+x)m 给定正整数k, { kn }的生成函数为 G(x) =1+ kx + k2x2 + k3x3 + … = * 例14 求序列{an}的生成函数 (1) an = 7· 3n (2) an = n(n+1) 解 由序列求生成函数 * 由生成函数求序列通项 例15 已知 {an} 的生成函数为 求an . 解 * 生成函数的应用 求解递推方程 计数多重集的 r 组合数 不定方程的解 整数拆分 * 求解递推方程 例16 an– 5an?1 + 6an?2 = 0，a0 = 1, a1 = ? 2 G(x) = a0 + a1x + a2x2 + a3x3 + … ?5x G(x) = ?5a0x ?5a1x2 ? 5a2x3 - … 6x2 G(x) = +6a0x2 +6a1x3 + … (1?5x+6x2)G(x) = a0 + (a1?5a0)x * 例17 解：设 { hn} 的生成函数为 求解递推方程 * 求解递推方程 * 多重集的 r 组合数 S = { n1?a1, n2?a2, …, nk?ak} 的 r 组合数就是不定方程 x1 + x2 + …+ xk = r xi ? ni i = 1,2,…,k 的非负整数解的个数 的展开式中 yr 的系数 生成函数 * 实例 例18 S ={ 3?a, 4?b, 5?c } 的10 组合数 解：生成函数G(y) = (1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5) = (1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5) = (1 + … +3y10+2y10+y10 + …) N = 6 组合方案 { a, a, a, b, b, b, b, c, c, c }, { a, a, a, b, b, b, c, c, c, c }, { a, a, a, b, b, c, c, c, c, c }, { a, a, b, b, b, b, c, c, c, c }, { a, a, b, b, b, c, c, c, c, c }, { a, b, b, b, b, c, c, c, c, c } * 不定方程解的个数 基本的不定方程 x1 + x2 + …+ xk = r ， xi 为自然数 * 推广的不定方程 带限制条件的不定方程 x1 + x2 + … + xk = r，li ? xi ? ni 带系数的不定方程 p1x1 + p2x2 + … + pkxk = r，xi?N 生成函数 生成函数 * 指数生成函数的定义与实例 指数生成函数的应用 13.5 指数生成函数及其应用 * 例19 给定正整数m,