离散数学及其应用-第2版 课件 第7章高级计数技术

第7章

高级计数技术第7章高级计数技术7.1递推方程7.2生成函数7.1递推方程定义7.1.1设序列

简记为

。序列

的递推方程是一个把

an用序列中在an

前面的一项或多项

ai(i<n)来表示的等式称作关于序列{an}的递推方程。例题例7.2.113世纪意大利数学家斐波那契（Fibonacci）提出了一个有趣的兔子繁殖问题：在一个岛上放了一对刚出生的兔子，其中一只公兔，一只母兔。经过两个月长成，长成后即可生育，假定每对兔子每个月都可以生出一对小兔，且新生的小兔也是一只公兔和一只母兔。如果兔子不会死去，也不会被运走，问12个月时岛上有多少对兔子?例题（续）解用

表示第

个月初的兔子对数，n是正整数。那么

f1=1（最初的兔子对数，第1个月的兔子对数）

f2=1（第2个月的兔子对数）f3=1+1=2（最初的一对加上它们的后代）

f4=2+1=3（第3个月的2对加上最初的一对的后代）f5=3+2=5（第4个月的3对加上第3个月2对的后代）

f6=5+3=8（第5个月的5对加上第4个月3对的后代）

f12=89+55=144（第11个月的89对加上第10个月55对的后代）12个月时岛上共有兔子144对。一般的，斐波那契数列满足下列递推方程数列

称作斐波那契数列，其中的每一个数也称作斐波那契数。例题在股票投资中，复合利息的作用是强大的。“股神”沃伦·巴菲特(Warren

Buffett)据说就是以年平均30%的复利战胜市场，从而成为举世瞩目的价值投资大师。假设他的初始投资为10000美元，年投资收益的复利是30%，那么在30年后账上的总资产有多少钱？解

令Pn表示n年后的总资产钱数。因为n年后账上的资产总额等于n-1年账上的资产加上第n年的投资收益，容易知道序列{Pn}满足递推关系例题（续）初始条件是P0=10000，我们可以知道代入初始条件，得将n=30代入，

26199956.44美元。常系数线性齐次递推方程的求解定义7.2.1设递推方程满足其中

为常数,,这个方程称为k阶常系数线性递推方程。

为k个初值。当

时，即称这个递推方程为齐次方程。

常系数线性齐次递推方程的求解定义7.2.2给定常系数线性齐次递推方程如下：（7.2）,求解该方程的基本方法是找到形如G(n)=rn的解，其中r是常数，即

等式两边同时除以rn-k，得

因此我们将形如方程

称为该递推方程的特征方程，特征方程的根r称为递推方程的特征根。定理定理7.2.1设g1(n)和g2(n)是递推方程(7.2)的两个解，c1,c2为任意常数，则c1g1(n)+c2

g2(n)也是这个递推方程的解。证明

将

g1(n)和g2(n)代入到方程(7.2)得，因此c1g1(n)+c2

g2(n)也是这个递推方程的解。

推论

若

是递推方程(7.2)的特征根，则

也是该递推方程的解，其中

是任意常数。以上推论说明

是递推方程的解。那么，除了这种形式的解以外，是否存在其他形式的解?为了解决这个问题，先定义通解。定义7.2.3能够表示递推方程（7.2）的每个解

的表达式称为该递推方程的通解。定理定理7.2.2设

是递推方程(7.2)不等的特征根，则

为该递推方程的通解，其中

是任意常数。证明

此定理是推广了定理7.2.1，证明类似。例题例7.2.1求下面递推方程的解：其中

，

。解递推方程的特征方程是

，它的根是2和-1。因此，递推方程的通解为c1,c2是常数。将初值

代入得解得,从而得到递推方程的解为，

定理定理7.2.3设

是递推方程（7.2）的不相等的特征根，且

ri的重数为ei，其中

那么该递推方程的通解是其中

为常数。

例题例7.2.4求解以下递推方程解

特征方程

为即

特征根是2，其重数是3，根据定理7.2.3

通解为代入初始条件，则有以下方程组解得

原方程的解为例题（续）解得

原方程的解为常系数线性非齐次递推方程的求解常系数线性非齐次递推方程的标准形是

（7.3）其中

f(n)是只依赖于n的函数。将

称作相伴的线性齐次递推方程。定理7.2.4设

是对应的相伴的线性齐次递推方程的通解，

是方程（7.3）的一个特解，则是递推方程（7.3）的通解。例题例7.2.5找出下述递推方程的通解：解

该方程对应相伴的线性齐次递推方程是

它的通解是c3n，其中c是常数。设特解

，其中c1,c2

是常数。代入递推方程得例题（续）整理得从而得线性方程组解得

因此

是一个特解，根据定理7.2.4，原方程的通解为初始条件

带入通解得,因此得原方程的通解为7.2生成函数生成函数是研究组合计数中的一个重要工具，其基本思想是把要计数或研究的离散数列同多项式或幂级数的系数一一对应起来，从而可以用数学分析的方法去研究这一数列，给出数列的一个显示解或渐近解。牛顿二项式系数与牛顿二项式定理定义7.3.1设r为实数，n为整数，引入形式符号称为牛顿二项式系数．定理定理7.3.1牛顿二项式定理．

设r为实数，则对一切实数

，有其中

生成函数的定义及其性质定义7.3.2设序列

，构造形式幂级数

称f(x)为序列

的生成函数。

定义7.3.2给出的生成函数有时叫做

的普通生成函数，以和这个序列的其他类型的生成函数相区别，序列

叫做f(x)的生成序列。例题例7.3.1设m是正整数，令ak=C(m,k)k=0,1,…m，

。那么序列{ak}的生成函数是什么？解这个序列的生成函数是由二项式定理可得

生成函数的性质设

是已知序列，它们的生成函数分别为若

为常数，则

若

，则

若

，则

若

生成函数的性质(续）(5)若

，则

(6)若

，则(7)若

，且

收敛，则

(8)若

为常数，则

(9)若

，则

，其中

为A(x)的导数。(10)若

，则

例题生成函数与序列是一一对应的。例7.3.2求序列{an}的生成函数

解

例题已知{an}的生成函数为

，求an.

解

因此我们可以得到

生成函数的应用例7.3.4求解递推方程

且初始条件

解

设序列

的生成函数为首先注意到例题（续）因为n>=1时有

且

所以有即得所以

指数型生成函数定义7.3.3

设{an}为序列，构造形式幂级数称

为{an}的指数型生成函数。例题设{an}是序列，求下列数列的指数生成函数

。（1）

，m为正整数；（2）an=1；（3）an=bn

；解（1）

（2）

（3）定理定理7.3.2

设

为多重集，则S的r-排列数由指数生成函数的展开式中

的系数给出。例题例7.3.10由1，2，3，4组成的5位数中，要求1出现不超过2次，但不能不出现，2出现不超过1次，3出现至多2次，4出现偶数次，求这样的5位数个数。解展开后

的

的系数为185，所以这样的5位数有185个。