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

10.2 生成函数及其应用生成函数及其应用•10.2.1牛顿二项式定理与牛顿二项式系数牛顿二项式定理与牛顿二项式系数•10.2.2 生成函数的定义及其性质生成函数的定义及其性质•10.2.3 生成函数的应用生成函数的应用1离散数学-生成函数及其应用牛顿二项式系数牛顿二项式系数定定义10.5 设 r 为实数，数，n为整数，引入形式符号整数，引入形式符号称称为牛牛顿二二项式系数式系数. . 例如例如2离散数学-生成函数及其应用牛顿二项式定理牛顿二项式定理定理定理10.6 （牛（牛顿二二项式定理）式定理）设 为实数，数，则对一切一切实数数x, y，，|x/y|<1，有，有若若 =  m，其中，其中m为正整数，那么正整数，那么3离散数学-生成函数及其应用重要展开式重要展开式令令x=z，，y=1，那么牛，那么牛顿二二项式定理就式定理就变成成 在上面式子中用在上面式子中用 z代替代替 z ，，则有有 4离散数学-生成函数及其应用生成函数的定义生成函数的定义定定义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 + … = 5离散数学-生成函数及其应用生成函数的性质生成函数的性质1. bn= an,  为常数，常数，则B(x)=  A(x)2. cn=an+bn, 则C(x)=A(x)+B(x) 5．．bn= an+l , 则 6离散数学-生成函数及其应用生成函数的性质生成函数的性质(续续)8．．bn=  nan,  为常数，为常数，则B(x)=A( x)9．．bn= nan, 则B(x)=xA (x)7离散数学-生成函数及其应用证明证明证证8离散数学-生成函数及其应用有关级数的结果有关级数的结果 9离散数学-生成函数及其应用由序列求生成函数由序列求生成函数例例1 求序列求序列{an}的生成函数的生成函数 (1) an = 7· 3n (2) an = n(n+1)解解10离散数学-生成函数及其应用由生成函数求序列通项由生成函数求序列通项例例2 已知已知 {an} 的生成函数的生成函数为求求an解解 . 11离散数学-生成函数及其应用生成函数的应用生成函数的应用•求解递推方程求解递推方程•计数多重集的计数多重集的r组合数组合数•不定方程的解不定方程的解•整数拆分整数拆分 12离散数学-生成函数及其应用求解递推方程求解递推方程例例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 13离散数学-生成函数及其应用求解递推方程求解递推方程(续续)例例2 解：解：设 { hn} 的生成函数的生成函数为 14离散数学-生成函数及其应用求解递推方程求解递推方程(续续)15离散数学-生成函数及其应用多重集的多重集的r-组合数组合数S = { n1 a1, n2 a2, …, nk ak} 的的 r 组合数就是不定方程合数就是不定方程 x1 + x2 + …+ xk = r xi   ni i = 1,2,…,k的非的非负整数解的个数整数解的个数 的展开式中的展开式中 yr 的系数的系数 生成函数生成函数16离散数学-生成函数及其应用多重集的多重集的r-组合数组合数(续续) 例例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 } 17离散数学-生成函数及其应用不定方程解的个数不定方程解的个数 基本的不定方程基本的不定方程 x1 + x2 + …+ xk = r ，， xi为自然数自然数 18离散数学-生成函数及其应用不定方程解的个数不定方程解的个数(续续)带限制条件的不定方程带限制条件的不定方程 x1 + x2 + … + xk = r，，li   xi   ni带系数的不定方程带系数的不定方程 p1x1 + p2x2 + … + pkxk = r，，xi N生成函数生成函数生成函数生成函数19离散数学-生成函数及其应用重量重量012345678910 11 12方案方案1121212121211实例实例例例4 4 1克砝码克砝码2个，个，2克砝码克砝码1个，个，4克砝码克砝码2个，问能称出个，问能称出哪些重量，方案有多少？哪些重量，方案有多少？解：解： x1 + 2 x2 + 4 x3 = r 0   x1   2, 0   x2   1, 0   x3   2 G(y) = (1+y+y2)(1+y2)(1+y4+y8) = 1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y1220离散数学-生成函数及其应用有序有序无序无序不重复不重复 4 = 4 4 = 1+3 4 = 3+1 4 = 4 4 = 1+3重复重复 4 = 4 4 = 1+3 4 = 3+1 4 = 2+2 4 = 2+1+1 4 = 1+2+1 4 = 1+1+2 4 = 1+1+1+1 4 = 4 4 = 1+3 4 = 2+2 4 = 2+1+1 4 = 1+1+1+1正整数拆分正整数拆分拆分拆分的定义：将给定正整数的定义：将给定正整数N表示成若干个正整数之和表示成若干个正整数之和. 拆分的分类拆分的分类21离散数学-生成函数及其应用无序拆分无序拆分基本模型：将基本模型：将N无序拆分成正整数无序拆分成正整数 a1, a2, …, an a1x1 + a2x2 + … + anxn = N 不允许重复不允许重复 允许重复允许重复22离散数学-生成函数及其应用实例实例例例5 证明任何正整数都可以唯一表示成明任何正整数都可以唯一表示成 2 进制数制数.对应于将任何正整数于将任何正整数N拆分成拆分成 2 的的幂，， 20, 21, 22, 23, …, 且不允且不允许重复重复. 生成函数生成函数 对于所有的于所有的 n, 系数是系数是1，，这就就证明唯一的表法明唯一的表法.23离散数学-生成函数及其应用无序拆分无序拆分——个数限制个数限制 例例6 给定定r,求求N允允许重复无序拆分成重复无序拆分成 k个数个数 (k r)的方法数的方法数解解 N允允许重复无序拆分成重复无序拆分成 k个数（个数（k r）的方案）的方案 N允允许重复无序拆分成正整数重复无序拆分成正整数 k（（k r）的方案）的方案做下述做下述 Ferrers图 将将图以以 y =x对角角线翻翻转180度，度，得到得到 共共轭的的Ferrers图. 16 = 6+5+3+2 （（k   4））对应每个数不超每个数不超过4的拆分的拆分: 16 = 4+4+3+2+2+1 这种拆分数的生成函数种拆分数的生成函数为 24离散数学-生成函数及其应用有序拆分有序拆分定理定理10.7 将将N允允许重复地有序拆分成重复地有序拆分成 r 个部分的方案数个部分的方案数为 C(N 1,r 1). 证 设 N= a1+a2+…+ar 是是满足条件的拆分，足条件的拆分，则令令 r 1个个Si 取取值为1,2,…,N 1，方法数，方法数为 C(N 1,r 1).推推论 对N 做任意重复的有序拆分，方案数做任意重复的有序拆分，方案数为不允不允许重复有序拆分：不允重复有序拆分：不允许重复无序拆分重复无序拆分 + 全排列全排列25离散数学-生成函数及其应用。