1、1摘要摘要 线性齐次递推关系线性齐次递推关系 生成函数生成函数 递归和生成函数递归和生成函数 一个几何的例子一个几何的例子 指数生成函数指数生成函数 作业作业 2线性齐次递推关系线性齐次递推关系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、错位排列数列 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齐次的齐次的 如果如果bn = 0，则线性递推关系，则线性递推关系 hn = a1hn-1+a2hn-2+akhn-k+bn, (n k) 称为称为齐次的齐次的. 如果如果a1, a2, , ak 是常数是常数,则称线性递推关则称线性递推关系式具有系式具有常系数常
3、系数.6定理定理 7.2.1 令令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) 的一般解的一般解: 无论给定无论给定
4、h0, h1, , 什么初什么初始值，都存在始值，都存在 常数常数c1, c2, , ck 使得式使得式 (7.22) 是满足递推关是满足递推关系系 (7.20) 和初始条件的唯一的序列和初始条件的唯一的序列. 7注解注解 多项式方程多项式方程 (7.21) 叫做叫做 递推关系递推关系 (7.20) 的的特征方程特征方程 ，而它的，而它的 k 个根叫做个根叫做 特征根特征根. 如果特征根如果特征根 互异互异, 那么式那么式(7.22) 就是式就是式(7.20) 的的一般解一般解.8例题例题 求解满足求解满足h0 = 1, h1 = 2 and h2 = 0的递推的递推关系关系 hn = 2hn
5、-1+hn-2 2hn-3, (n 3) . 提示提示: 这个递推关系的特征方程为这个递推关系的特征方程为 x3 2x2 x + 2 = 0 而它的三个根而它的三个根 1, -1 , 2. 根据定理根据定理7.2.1, hn = c11n + c2(-1)n + c32n 是一般解是一般解. 9例题（续）例题（续） 由三个字母由三个字母a, b, c组成的长度为组成的长度为n的一些的一些单词将在通信信道上传输，满足条件：单词将在通信信道上传输，满足条件：传输中不得有两个传输中不得有两个a连续出现在任一个单连续出现在任一个单词中。确定通信信道允许传输的单词个词中。确定通信信道允许传输的单词个数。
6、数。 10提示 首先首先, 找到特征关系式找到特征关系式 并且求出它的解并且求出它的解. 令令 hn 表示允许传输的长度为表示允许传输的长度为 n的单词的个数的单词的个数. 我我们有们有 h0 = 1 和和 h1 = 3. 令令 n 2. 如果第一个字母如果第一个字母是是 b 或者或者 c, 那么这个单词就可以有那么这个单词就可以有 hn-1种方法种方法构成构成. 如果第一个字母是如果第一个字母是 a , 那么第二个字母是那么第二个字母是 b 或者或者 c. 这样这样, hn = 2 hn-1 + 2hn-2, (n 2).ba b11练习练习 一个一个 1n 棋盘棋盘. 我们把每个方格都涂上
7、我们把每个方格都涂上红色或者蓝色红色或者蓝色. 令令 hn 表示没有两个连续表示没有两个连续的方格被同时涂上红色的方法的个数的方格被同时涂上红色的方法的个数. 找找到并且证明这样的一个递推关系到并且证明这样的一个递推关系hn. 然后然后求得公式求得公式 hn. 求解递推关系求解递推关系 hn = 4hn-1 4hn-2, (n 2) .12注解注解 如果特征方程的根如果特征方程的根 q1, q2, , qk 不是互异不是互异的的, 那么那么 hn = c1q1n+c2q2n+ckqkn 就不是就不是递推关系的一个一般解递推关系的一个一般解. 13定理定理 7.2.2 令令 q1, q2, ,
8、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例题例题 求递推关系求递推关系 hn = 4hn-1 4hn-2, (n 2) .提示提示: 特征方程是特征方程是 x2-4x+4 = 0. 这样
9、这样 2 是是重特征根重特征根. 特征关系的一般解为特征关系的一般解为 hn = c12n + c2n2n.15练习练习 求特征关系求特征关系 hn = -hn-1 +3hn-2+5hn-3 +2hn-4, (n 4).16生成函数生成函数 17生成函数的方法生成函数的方法利用代数的方法计算一个问题可能性的利用代数的方法计算一个问题可能性的次数次数生成函数是无穷次可微函数的泰勒级数生成函数是无穷次可微函数的泰勒级数如果你可以找到一个函数和它的泰勒级如果你可以找到一个函数和它的泰勒级数数, 那么泰勒级数的系数则给出这个问那么泰勒级数的系数则给出这个问题的解题的解.18生成函数的定义生成函数的定义
10、令令 h0, h1, , hn, 是一个无穷的数列是一个无穷的数列. 它的它的 生成函数生成函数 被定义为无穷级数被定义为无穷级数 g(x) = h0 + h1x + h2x2 + hnxn +在在 g(x)中，中，xn 的系数是这个序列的第的系数是这个序列的第n项项 hn, 从而，从而， xn 作为作为hn的的“位置持有者位置持有者”。 19例题例题1. 无限序列的生成函数无限序列的生成函数 1, 1, 1, , 1, , 它的每一它的每一项都等于项都等于1 g(x) = 1 +x+x2+xn+ = 1/(1-x)2. M是一个正整数是一个正整数. 二项式序列二项式序列 c(m,0), c(
11、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练习练习 令令a为一个实数为一个实数. 根据牛顿二项式定理根据牛顿二项式定理, 二项二项式系数式系数 c(a, 0), c(a, 1) ,c(a, n),的无穷的无穷生成函数是什么？生成函数是什么？令令 k 是一个整数，是一个整数， 并令序列并令序列 h0, h1, h2, hn, 使得使得hn等于等于 e1+e2+ek=n的非负整的非负整数的个数数的个数. 这个序列的生成函数是什么这个序列的生成函
12、数是什么?21复习 令令a是一个实数是一个实数 . 那么对于所有的那么对于所有的 x 和和 y （0 |x| |y|）, 0)(kkkaayxkayx!121kkaaaaka22又因为又因为 |y|11)24例题（续）例题（续）确定苹果、香蕉、橘子和梨的确定苹果、香蕉、橘子和梨的n-组合的个数组合的个数, 其中其中在每个在每个n-组合中苹果的个数是偶数，香蕉的个数组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在是奇数，橘子的个数在0和和4之间，而且至少要有之间，而且至少要有一个梨一个梨提示提示: 该问题等价于找出该问题等价于找出 e1 + e2 + e3 + e4 = n.的非负整数解的
13、个数的非负整数解的个数25 其中其中 e1 是偶数是偶数 (e1 为苹果数为苹果数), e2 是奇数是奇数, 0 e34, 而而 e4 1. 我们为每种类型的水果建我们为每种类型的水果建立一个因子，立一个因子， 其中的指数为那种类型水果其中的指数为那种类型水果的的n- 组合中所允许的数组合中所允许的数: g(x) = (1 + x2 + x4 +)(x + x3 + x5 +)(1 + x + x2 + x3 + x4) (x + x2 + x3 + x4 +) 22252522)1 ()1 ()1 (111111xxxxxxxxxxx26练习练习 令令hn代表好几袋子苹果、香蕉、橘子和梨代表
14、好几袋子苹果、香蕉、橘子和梨的总个数的总个数, 并且每个袋子中苹果的个数是并且每个袋子中苹果的个数是偶数偶数, 香蕉的隔数是香蕉的隔数是 5的倍数的倍数, 橘子的个数橘子的个数至多为至多为 4 并且梨的个数为并且梨的个数为 0 或者或者 1. 提示提示: 计算这个问题的生成函数的计算这个问题的生成函数的xn的系数的系数. 27练习（续）练习（续）确定方程确定方程 e1 + e2 + + ek = n非负整数解非负整数解e1, e2, , ek 的个数的个数hn的生成函数。的生成函数。提示提示: k (x+x3+x5+x7+).28练习练习 (续续)令令 hn 表示方程表示方程 3e1 + 4e
15、2 + 2e3 + 5e4 = n非负非负整数解的个数整数解的个数. 找到找到h0, h1, h2, , hn,.的的生成函数生成函数 g(x)提示提示: 令令 f1 = 3e1, f2 = 4e2, f3 = 2e3 并且并且 f4 =5e4. 于是于是hn 也等于也等于 f1 + f2 + f3 + f4 = n 的非负整的非负整数解的个数，其中数解的个数，其中 f1 是是 3的倍数的倍数, f2 是是 4的的倍数倍数, f3 是偶数是偶数 并且并且 f4 是是 5的倍数的倍数. 29递归生成函数递归生成函数30内容内容 利用生成函数来求解常系数的线性齐次利用生成函数来求解常系数的线性齐次
16、递推关系递推关系. 牛顿二项定理的应用牛顿二项定理的应用.31复习复习: 牛顿二项定理牛顿二项定理如果 n是一个正整数 并且 r 是一个非零整数, 那么)|(|,1)1()()1(1000 rxxrkknxrknrxknrxkkkkkkkkkn32例题例题确定平方项的序列确定平方项的序列 0, 1, 4, , n2,.的生成函数的生成函数解答解答: 把把 n =2 、 r =1带入上面的牛顿二项式带入上面的牛顿二项式, (1-x)-2 = 1+2x+3x2+nxn-1+. 因此因此 x/(1-x)2=x+2x2 + 3x3+nxn +. 微分微分, 我们得到我们得到 （1+x)/(1-x)3=
17、1+22x+32x2+n2xn-1+. 乘乘 x, 得到得到 x(1+x)/(1-x)3.33例题例题 (续续) 求解满足初始值求解满足初始值 h0 = 1 和和 h1 = -2的递推的递推关系关系 hn = 5hn-1 6 hn-2, (n2).提示提示: 令令 g(x) = h0+h1x+h2x2+hnxn+. 为为 h0, h1, h2, , hn 的生成函数。此时，的生成函数。此时，我们有下列方程我们有下列方程 34g(x) = h0+h1x+h2x2+hnxn+.-5xg(x) = -5h0 x -5h1x2 - 5h2x3 - 5hn-1 xn -. 6x2 g(x) = 6h0
18、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通过牛顿二项定理通过牛顿二项定理(1-2x)-1 = 1+2x+22x2+2nxn.(1-3x)-1 = 1+3x+32x2+3nxn.于是于是, g(x) = 1 + (-2)x + (-15)x2 + (52n 43n)
19、xn+可以得到可以得到 hn = 52n 43n (n = 0, 1, 2, ).36练习 满足满足h0 = 0, h1 = 1 ，h2 = -1的递推关系的递推关系 hn + hn-1 16 hn-2+20hn-3 = 0 (n3)求求hn的一般公式。的一般公式。37一个几何的例子一个几何的例子38划分凸多边形的方法划分凸多边形的方法通过画出在区域内部不相交的对角线将具通过画出在区域内部不相交的对角线将具有有n+1 条边的凸多边形区域分成三角形区域，令条边的凸多边形区域分成三角形区域，令hn 表示分成三角形区域的方法数。定义表示分成三角形区域的方法数。定义h1 =1. 则则 hn 满足递推关
20、系满足递推关系 hn = h1hn-1+h2hn-2+hn-1h1, (n2). 该递推关系的解为该递推关系的解为 hn = n-1C(2n-2, n-1), (n=1, 2 , 3, ).39指数生成函数指数生成函数40复习复习: ex的泰勒级数的泰勒级数! 21!20nxxxnxennnx41指数生成函数的定义指数生成函数的定义 序列序列 h0, h1, h2, , hn, 的指数生成函数的指数生成函数 !2!)(22100)(nxhxhxhhnxhxgnnnnne42例子例子 令令n为一正整数为一正整数.确定数列确定数列P(n, 0), P(n, 1), P(n, 2), , P(n,
21、n),的指数生成函数的指数生成函数,其中其中 P(n, k) 表示表示n-元素集的元素集的k-排列的个数排列的个数,对对于于k = 0, 1, , n 其值为其值为n!/(n-k)! .指数生指数生成函数为成函数为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)的常规生成函数的常规生成函数.nnnexxnnxnnnxnxnnPxnPxnPnPxg)1 (! 0 !)!2( ! 2!1!),(! 2)2 ,()
22、 1 ,()0 ,()(22)(44练习练习 (续续) 序列序列1, 1, 1, , 1, . 的指数生成函数是的指数生成函数是 更一般的更一般的,如果如果a是一个实数是一个实数,那么序列那么序列a0 = 1, a, a2, , an, . 的指数生成函数是的指数生成函数是xnneenxxg 0)(!)(.!)(!)(00)(axnnnnneenaxnxaxg45定理定理 令令S为多重集为多重集 n1.a1, n2.a2, nk.ak ,其中其中 n1, n2, , nk 均为非负整数均为非负整数.令令hn 是是S的的n-排列数排列数. 则序列则序列h0, h1, h2,hn, 的指数的指数生
23、成函数生成函数g(e)(x)由由 g(e)(x)= fn1(x) fn2(x) . fnk(x) 给定给定 其中其中,对于对于 i=1, 2, , k, fni(x) = 1 +x+x2/2!+xni/ni!.46例题例题如果把一个如果把一个1*n的棋盘上的偶数个方格染成红的棋盘上的偶数个方格染成红,白白,蓝三种颜色蓝三种颜色,共有多少种染色方案共有多少种染色方案?线索线索: 令令 hn表示这样的染色方案数表示这样的染色方案数,定义定义h0 =1. 此此时时hn 等于三种颜色的多重集的等于三种颜色的多重集的n-排列数排列数,其中其中每一种颜色都有无穷重复数每一种颜色都有无穷重复数,且红色出现偶
24、数且红色出现偶数次次.因此因此, h0, h1, h2,hn , 的指数生成函数是的指数生成函数是红红,白白,蓝因子的乘积蓝因子的乘积:47因此因此, hn = (3n+1)/2.!) 13(21)!3(21)(21)(21)! 2! 11)(! 2! 11)(! 4! 21 (00032242)(nxnxnxeeeeeexxxxxxgnnnnnnnnxxxxxxe48练习练习 确定每个数字都是奇数的确定每个数字都是奇数的n位数的个数位数的个数,其中要求其中要求1和和3出现偶数次出现偶数次. 线索线索: 令令 h0 =1. hn 等于多重集等于多重集S = 1, 3, 5, 7, 9的的n-排列的个数排列的个数,其中要求其中要求1和和3出现偶数次出现偶数次. 49练习练习 (续续) 用红用红,白白,蓝三种颜色给一个蓝三种颜色给一个1*n的棋盘染的棋盘染色色,如果有偶数方格必须染成红色如果有偶数方格必须染成红色,并且至并且至少有一个蓝色的少有一个蓝色的,求一共有多少种染色方求一共有多少种染色方案案?
