递推关系与生成函数

1、递推关系与生成函数第1页，共51页，2022年，5月20日，19点38分，星期三1摘要线性齐次递推关系 生成函数 递归和生成函数一个几何的例子指数生成函数作业 第2页，共51页，2022年，5月20日，19点38分，星期三2线性齐次递推关系第3页，共51页，2022年，5月20日，19点38分，星期三3线性递推关系令 h0, h1, hn, 是一个数列，如果存在量 a1, a2, , ak, ak 0, 和量bn (每一个量 a1, a2, , ak, bn 可能依赖于 n) ，使得 hn = a1hn-1+a2hn-2+akhn-k+bn, (n k).则称该序列满足k阶线性递推关系.第4页

2、，共51页，2022年，5月20日，19点38分，星期三4例子 错位排列数列 D0, D1, D2, Dn 满足两个递推关系Dn = (n-1)Dn-1+(n-1)Dn-2, (n 2)Dn = nDn-1 + (-1)n, (n 1). 第一个递推关系的阶 是多少 且 a1 ，a2 ， bn等于多少。第二个递推关系的 .第5页，共51页，2022年，5月20日，19点38分，星期三5齐次的 如果bn = 0，则线性递推关系 hn = a1hn-1+a2hn-2+akhn-k+bn, (n k) 称为齐次的.如果a1, a2, , ak 是常数,则称线性递推关系式具有常系数.第6页，共51页，

3、2022年，5月20日，19点38分，星期三6令q 为一个非零数. 则 hn = qn 是常系数线性递推关系 hn a1hn-1 a2hn-2 akhn-k= 0, (ak 0, n k) (7.20) 的解，当且仅当q是多项式 xk a1xk-1 a2xk-2 ak = 0. (7.21)的一个根。如果多项式方程有k个不同的根 q1, q2, , qk, 则 hn = c1q1n + c2q2n + + ckqkn (7.22) 是下述意义下式 (7.20) 的一般解: 无论给定 h0, h1, , 什么初始值，都存在 常数c1, c2, , ck 使得式 (7.22) 是满足递推关系 (7

4、.20) 和初始条件的唯一的序列. 第7页，共51页，2022年，5月20日，19点38分，星期三7注解 多项式方程 (7.21) 叫做 递推关系 (7.20) 的特征方程 ，而它的 k 个根叫做 特征根. 如果特征根 互异, 那么式(7.22) 就是式(7.20) 的一般解.第8页，共51页，2022年，5月20日，19点38分，星期三8例题求解满足h0 = 1, h1 = 2 and h2 = 0的递推关系 hn = 2hn-1+hn-2 2hn-3, (n 3) . 提示: 这个递推关系的特征方程为 x3 2x2 x + 2 = 0 而它的三个根 1, -1 , 2. 根据定理7.2.1

5、, hn = c11n + c2(-1)n + c32n 是一般解. 第9页，共51页，2022年，5月20日，19点38分，星期三9例题（续）由三个字母a, b, c组成的长度为n的一些单词将在通信信道上传输，满足条件：传输中不得有两个a连续出现在任一个单词中。确定通信信道允许传输的单词个数。 第10页，共51页，2022年，5月20日，19点38分，星期三10提示 首先, 找到特征关系式 并且求出它的解.令 hn 表示允许传输的长度为 n的单词的个数. 我们有 h0 = 1 和 h1 = 3. 令 n 2. 如果第一个字母是 b 或者 c, 那么这个单词就可以有 hn-1种方法构成. 如果

6、第一个字母是 a , 那么第二个字母是 b 或者 c. 这样, hn = 2 hn-1 + 2hn-2, (n 2).bab第11页，共51页，2022年，5月20日，19点38分，星期三11练习 一个 1n 棋盘. 我们把每个方格都涂上红色或者蓝色. 令 hn 表示没有两个连续的方格被同时涂上红色的方法的个数. 找到并且证明这样的一个递推关系hn. 然后求得公式 hn.求解递推关系 hn = 4hn-1 4hn-2, (n 2) .第12页，共51页，2022年，5月20日，19点38分，星期三12注解 如果特征方程的根 q1, q2, , qk 不是互异的, 那么 hn = c1q1n+c

7、2q2n+ckqkn 就不是递推关系的一个一般解. 第13页，共51页，2022年，5月20日，19点38分，星期三13 令 q1, q2, , qt 为常系数线性齐次递推关系 (7.20) 的特征方程的互异的根. 此时，如果 qi是 si重根, 则该递推关系对qi的部分一般解为 Hn(i) = c1qin + c2nqin + + csinsi-1qin = (c1 +c2n+csinsi-1)qin 递推关系的一般解则是hn = Hn(1) + Hn (2) + + Hn(t).第14页，共51页，2022年，5月20日，19点38分，星期三14例题求递推关系 hn = 4hn-1 4hn

8、-2, (n 2) .提示: 特征方程是 x2-4x+4 = 0. 这样 2 是重特征根. 特征关系的一般解为 hn = c12n + c2n2n.第15页，共51页，2022年，5月20日，19点38分，星期三15练习 求特征关系 hn = -hn-1 +3hn-2+5hn-3 +2hn-4, (n 4).第16页，共51页，2022年，5月20日，19点38分，星期三16生成函数 第17页，共51页，2022年，5月20日，19点38分，星期三17生成函数的方法利用代数的方法计算一个问题可能性的次数生成函数是无穷次可微函数的泰勒级数如果你可以找到一个函数和它的泰勒级数, 那么泰勒级数的系数

9、则给出这个问题的解.第18页，共51页，2022年，5月20日，19点38分，星期三18生成函数的定义令 h0, h1, , hn, 是一个无穷的数列. 它的 生成函数 被定义为无穷级数 g(x) = h0 + h1x + h2x2 + hnxn +在 g(x)中，xn 的系数是这个序列的第n项 hn, 从而， xn 作为hn的“位置持有者”。 第19页，共51页，2022年，5月20日，19点38分，星期三19例题1. 无限序列的生成函数 1, 1, 1, , 1, , 它的每一项都等于1 g(x) = 1 +x+x2+xn+ = 1/(1-x)2. M是一个正整数. 二项式序列 c(m,0

10、), c(m,1) c(m, 2),., c(m,m) 的生成函数是 gm(x)=c(m,0)+c(m,1)x+c(m,2)x2+c(m,m)xm = (1+x)m (二项式定理).第20页，共51页，2022年，5月20日，19点38分，星期三20练习 令a为一个实数. 根据牛顿二项式定理, 二项式系数 c(a, 0), c(a, 1) ,c(a, n),的无穷生成函数是什么？令 k 是一个整数， 并令序列 h0, h1, h2, hn, 使得hn等于 e1+e2+ek=n的非负整数的个数. 这个序列的生成函数是什么?第21页，共51页，2022年，5月20日，19点38分，星期三21复习

11、令a是一个实数 . 那么对于所有的 x 和 y （0 |x| |y|）, 第22页，共51页，2022年，5月20日，19点38分，星期三22又因为 |y|11)第24页，共51页，2022年，5月20日，19点38分，星期三24例题（续）确定苹果、香蕉、橘子和梨的n-组合的个数, 其中在每个n-组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在0和4之间，而且至少要有一个梨提示: 该问题等价于找出 e1 + e2 + e3 + e4 = n.的非负整数解的个数第25页，共51页，2022年，5月20日，19点38分，星期三25 其中 e1 是偶数 (e1 为苹果数), e2 是奇数, 0

12、 e34, 而 e4 1. 我们为每种类型的水果建立一个因子， 其中的指数为那种类型水果的n- 组合中所允许的数: g(x) = (1 + x2 + x4 +)(x + x3 + x5 +)(1 + x + x2 + x3 + x4) (x + x2 + x3 + x4 +) 第26页，共51页，2022年，5月20日，19点38分，星期三26练习 令hn代表好几袋子苹果、香蕉、橘子和梨的总个数, 并且每个袋子中苹果的个数是偶数, 香蕉的隔数是 5的倍数, 橘子的个数至多为 4 并且梨的个数为 0 或者 1. 提示: 计算这个问题的生成函数的xn的系数. 第27页，共51页，2022年，5月2

13、0日，19点38分，星期三27练习（续）确定方程 e1 + e2 + + ek = n非负整数解e1, e2, , ek 的个数hn的生成函数。提示: k (x+x3+x5+x7+).第28页，共51页，2022年，5月20日，19点38分，星期三28练习 (续)令 hn 表示方程 3e1 + 4e2 + 2e3 + 5e4 = n非负整数解的个数. 找到h0, h1, h2, , hn,.的生成函数 g(x)提示: 令 f1 = 3e1, f2 = 4e2, f3 = 2e3 并且 f4 =5e4. 于是hn 也等于 f1 + f2 + f3 + f4 = n 的非负整数解的个数，其中 f1

14、 是 3的倍数, f2 是 4的倍数, f3 是偶数 并且 f4 是 5的倍数. 第29页，共51页，2022年，5月20日，19点38分，星期三29递归生成函数第30页，共51页，2022年，5月20日，19点38分，星期三30内容利用生成函数来求解常系数的线性齐次递推关系. 牛顿二项定理的应用.第31页，共51页，2022年，5月20日，19点38分，星期三31复习: 牛顿二项定理如果 n是一个正整数 并且 r 是一个非零整数, 那么第32页，共51页，2022年，5月20日，19点38分，星期三32例题确定平方项的序列 0, 1, 4, , n2,.的生成函数解答: 把 n =2 、 r

15、 =1带入上面的牛顿二项式, (1-x)-2 = 1+2x+3x2+nxn-1+. 因此 x/(1-x)2=x+2x2 + 3x3+nxn +. 微分, 我们得到 （1+x)/(1-x)3=1+22x+32x2+n2xn-1+. 乘 x, 得到 x(1+x)/(1-x)3.第33页，共51页，2022年，5月20日，19点38分，星期三33例题 (续)求解满足初始值 h0 = 1 和 h1 = -2的递推关系 hn = 5hn-1 6 hn-2, (n2).提示: 令 g(x) = h0+h1x+h2x2+hnxn+. 为 h0, h1, h2, , hn 的生成函数。此时，我们有下列方程 第

16、34页，共51页，2022年，5月20日，19点38分，星期三34g(x) = h0+h1x+h2x2+hnxn+.-5xg(x) = -5h0 x -5h1x2 - 5h2x3 - 5hn-1 xn -. 6x2 g(x) = 6h0 x2 +6h1x3 +6h2x4 +6hn-2xn +. 将三个方程相加, 得到(1-5x+6x2)g(x) = h0+(h1-5h0)x+(h2-5h1+6h0)x2+(hn-5hn-1+6hn-2)xn+. = h0+(h1-5h0)x = 1-7x因此, g(x) = (1-7x)/(1-5x+6x2) = 5/(1-2x) 4/(1-3x)第35页，共

17、51页，2022年，5月20日，19点38分，星期三35通过牛顿二项定理(1-2x)-1 = 1+2x+22x2+2nxn.(1-3x)-1 = 1+3x+32x2+3nxn.于是, g(x) = 1 + (-2)x + (-15)x2 + (52n 43n)xn+可以得到 hn = 52n 43n (n = 0, 1, 2, ).第36页，共51页，2022年，5月20日，19点38分，星期三36练习 满足h0 = 0, h1 = 1 ，h2 = -1的递推关系 hn + hn-1 16 hn-2+20hn-3 = 0 (n3)求hn的一般公式。第37页，共51页，2022年，5月20日，1

18、9点38分，星期三37一个几何的例子第38页，共51页，2022年，5月20日，19点38分，星期三38划分凸多边形的方法通过画出在区域内部不相交的对角线将具有n+1 条边的凸多边形区域分成三角形区域，令hn 表示分成三角形区域的方法数。定义h1 =1. 则 hn 满足递推关系 hn = h1hn-1+h2hn-2+hn-1h1, (n2). 该递推关系的解为 hn = n-1C(2n-2, n-1), (n=1, 2 , 3, ).第39页，共51页，2022年，5月20日，19点38分，星期三39指数生成函数第40页，共51页，2022年，5月20日，19点38分，星期三40复习: ex的

19、泰勒级数第41页，共51页，2022年，5月20日，19点38分，星期三41指数生成函数的定义 序列 h0, h1, h2, , hn, 的指数生成函数 第42页，共51页，2022年，5月20日，19点38分，星期三42例子 令n为一正整数.确定数列P(n, 0), P(n, 1), P(n, 2), , P(n, n),的指数生成函数,其中 P(n, k) 表示n-元素集的k-排列的个数,对于k = 0, 1, , n 其值为n!/(n-k)! .指数生成函数为第43页，共51页，2022年，5月20日，19点38分，星期三43因此, (1+x)n 既是序列P(n, 0), P(n, 1), P(n, 2), , P(n, n) 的指数生成函数又是序列C(n, 0), C(n, 1), C(n, 2), , C(n, n)的常规生成函数.第44页，共51页，2022年，5月20日，19点38分，星期三44练习 (续)序列1, 1, 1, , 1, . 的指数生成函数是更一般的,如果a是一个实数,那么序列a0 = 1, a, a2, , an, . 的指数生成函数是第45页，共51页，2022年，5月20日，19点38分，星期三45定理令S为多重集 n1.a1, n2.a2, nk.ak ,其中 n1, n2, , nk 均为非负整数.令hn 是S的n-排列数. 则序列h