离散数学生成函数及其应用.ppt

10.2 生成函数及其应用 10.2.1牛顿二项式定理与牛顿二项式系数 10.2.2 生成函数的定义及其性质 10.2.3 生成函数的应用 牛顿二项式系数 牛顿二项式定理 重要展开式 生成函数的定义 生成函数的性质 生成函数的性质(续) 证明 有关级数的结果 由序列求生成函数 由生成函数求序列通项 生成函数的应用 求解递推方程 计数多重集的r组合数 不定方程的解 整数拆分 求解递推方程 求解递推方程(续) 求解递推方程(续) 多重集的r-组合数 多重集的r-组合数(续) 不定方程解的个数 不定方程解的个数(续) 实例 正整数拆分 无序拆分 实例 无序拆分——个数限制 有序拆分 * 定义10.5 设 r 为实数，n为整数，引入形式符号 称为牛顿二项式系数. 例如 定理10.6 （牛顿二项式定理） 设?为实数，则对一切实数x, y，|x/y|1，有 若?= ?m，其中m为正整数，那么 令x=z，y=1，那么牛顿二项式定理就变成 在上面式子中用?z代替 z ，则有 定义10.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 + … = 1. bn=?an, ?为常数，则B(x)= ?A(x) 2. cn=an+bn, 则C(x)=A(x)+B(x) 5．bn= an+l , 则 8．bn= ?nan, ?为常数，则B(x)=A(?x) 9．bn= nan, 则B(x)=xA?(x) 证 例1 求序列{an}的生成函数 (1) an = 7· 3n (2) an = n(n+1) 解 例2 已知 {an} 的生成函数为 求an 解 . 例1 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 例2 解：设 { hn} 的生成函数为 S = { n1?a1, n2?a2, …, nk?ak} 的 r 组合数就是不定方程 x1 + x2 + …+ xk = r xi ? ni i = 1,2,…,k 的非负整数解的个数 的展开式中 yr 的系数 生成函数 例3 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 生成函数 生成函数 1 1 2 1 2 1 2 1 2 1 2 1 1 方案 12 11 10 9 8 7 6 5 4 3 2 1 0 重量 例4 1克砝码2个，2克砝码1个，4克砝码2个，问能称出 哪些重量，方案有多少？ 解： x1 + 2 x2 + 4 x3 = r 0 ? x1 ? 2, 0 ? x2 ? 1, 0 ? x3 ? 2