递推关系和生成函数
2011-05-01 22:48阅读：
递推关系和生成函数
7.1 某些数列
（1）等差数列（算术数列）
h0,
h0+q, h0+2q, …, h0+nq,…
递推关系：hn= hn-1+q
一般项：
hn= h0+nq
前n+1项和：sn=
(n+1)h0+q(n)(n+1)/2
（2）等比数列（几何数列）
h0,
qh0, q2h0, …,
qnh0,…
递推关系：hn= qhn-1
一般项：
hn= qnh0
前n+1项和：sn=
h0(1-qn+1)/(1-q)
例1：
确定平面一般位置上的n个互相交叠的圆所形成的区域数。（互相交叠是指每两个圆相交在不同的两个点上；一般位置是指没有同心圆）
例2：
年初把性别相反的一对新生兔子放进围栏，从第二个月开始每月生出一对性别相反的兔子，每对新兔也从第二个月开始每月生出一对性别相反的兔子，问一年后围栏内共有多少对兔子。
定义1：
设f0=0, f1=1, 那么满足递推关系fn=
fn-1+ fn-2,
的序列叫斐波那契（Fibonacci）序列。
结论：Fibonacci序列的部分和为sn= f0+
f1+…+ fn= fn+2-1.
定理7.1.1：
Fibonacci序列的一般项公式为：
fn= （
）n - （ ）n
定理7.1.2
沿Pascal三角形左边向上对角线上的二项式系数和是Fibonacci数,即
fn= + +…+ , 其中:k=ë û.
7.2 线性齐次递推关系
定义1:
令h0, h1, h2,…,
hn,…是一个数列,若存在量a1,
a2,
…,ak和bn(ak≠0,每个量是常数或依赖于n的数)使得:
hn= a1hn-1+
a2hn-2+…+
akhn-k+bn
(n≥k)
则称序列满足k阶线性递推关系.
若bn=0,称齐次的;若a1,
a2, …,ak取常数,称常系数的.
定理7.2.1
令q为一个非零数,则hn=qn是常系数线性齐次递推关系
hn= a1hn-1+
a2hn-2+…+ akhn-k
(ak≠0,n≥k)
(1)
的解,当且仅当q是多项式方程
xk-a1xk-1-
a2xk-2-…- ak=0
(2)
的一个根.若多项式方程有k个不同的根q1, q2,…,
qk,则
hn=c1q1n+
c2q2n+…+
ckqkn
(3)
是下述意义下(1)的一般解: 无论给定h0, h1,
…,hk-1什么初始值,都存在c1,
c2,…,
ck使得(3)式是满足(1)式和初始条件的唯一的序列.
例1:
求满足初始值h0=1,
h1=2和h2=0的递推关系:
hn=
2hn-1+ hn-2- 2hn-3
定理7.2.2
令q1, q2,…,
qt为常系数线性齐次递推关系:
hn=
a1hn-1+ a2hn-2+…+
akhn-k (n≥k)
的特征方程的互异的根,此时,如果qi是si的重根,则该递推关系对qi的部分一般解为:
Hn(i) =
c1qin+
c2nqin+…+
csinsi-1qin
递推关系的一般解为:
hn= Hn(1) +
Hn(2) +…+
Hn(t)
例2:
求解递推关系
hn=
-hn-1+ 3hn-2+…+ 5hn-3+
2hn-4 (n≥4)
满足初始条件h0=1, h1=0,
h2=1和h3=2的解.
7.3 非齐次递推关系
一般方法总结:
(1) 求齐次关系的一般解
(2) 求非齐次关系的一个特解
(3)
将一般解和特解结合,通过初始条件确定一般解中出现的常系数值.
根据非齐次项bn 来尝试某些类型的特解:
(1) 若bn
=d(常数), 尝试hn =r(常数);
(2) 若bn
=dn+c(d,c是常数), 尝试hn
=rn+s(r,s是常数);
(3) 若bn
=fn2+dn+c(f,d,c是常数), 尝试hn
=rn+sn+t(r,s,t是常数);
(4) 若bn
=dn(d是常数), 尝试hn
=pdn(p是常数);
例1:
解
hn= 3hn-1- 4n (n≥1),
初始值 h0=2.
例2:
解
hn= 3hn-1+ 3n
(n≥1), 初始值
h0=2.
7.4 生成函数
定义1:
令序列h0, h1,…,
hn…为一无穷序列,其生成函数定义为:
g(x)= h0+ h1x+
h2x2+… hnxn+…
例1:
设m是正整数,求序列 , , ,…, 的生成函数.
例2:
设
是实数,求序列 , , ,…, ,…的生成函数.
例3:
设k是正整数,求序列h0, h1,…,
hn…的生成函数,其中一般项hn等于方程e1
+ e1+ …+ek =n的非负整数解个数.
解:
hn相当于具有无限重复次数的k 个不同元素的n组合个数,
hn= ,
其生成函数g(x)= xn=
反向思考该问题:
若已知生成函数g(x)= ,那么
= . …. =(1+x+x2+…) (1+x+x2+…)
…(1+x+x2+…)= . …
其展开项xn= xe1. xe2.
..xek = xe1+e2+..ek,
它的系数hn相当于方程e1 + e1+
…+ek =n的非负整数解个数, hn= ,
相当于根据生成函数求解出具有无限重复次数的k
个不同元素的n组合个数hn. 若e1 ,
e1,…,ek 有不同的约束, 表现为不同的生成函数,
若我们能求出该生成函数对应的序列一般项hn.那么就相当于在某种约束下求解出k
个不同元素的n组合个数hn.
例4:
确定苹果,香蕉,橘子和梨的n组合个数,其中每个n组合中,苹果的个数是偶数,香蕉的个数是奇数,橘子的个数在0~4之间,而且至少有一个梨.
例5:
确定苹果,香蕉,橘子和梨的袋装水果的袋数hn(即n组合数),其中每袋中苹果的个数是偶数,香蕉的个数是5的倍数,橘子的个数最多4个,梨子的个数是0或1.
7.5 递归和生成函数
利用生成函数求解n阶常系数线性齐次递推关系:
例1:
求解初始值h0=1和h1=-2的递推关系
hn=
5hn-1-6hn-2 (n≥2)
定理7.5.1
令h0, h1, h2,…,
hn,…为满足k阶常系数线性齐次递推关系:
hn= c1hn-1+
c2hn-2+…+ ckhn-k
(ck≠0,n≥k)
(1)
的数列,则它的生成函数g(x)形如:
g(x)=
(2)
其中:q(x)是具有非零常数次的k 次多项式,p(x)是小于k
次的多项式.反之, 给定这样的多项式p(x)和q(x),
则存在序列h0, h1, h2,…,
hn,…满足(1)式的k阶常系数线性齐次递推关系,
其生成函数由(2)式给出.
关于解方程的已知结论:
(1)对于4次以及4次以下的方程,目前已有代数解法.(在复数域内求解)
(2)阿贝尔定理:
5次以及更高次的代数方程没有一般的代数解法.
7.6 一个几何的例子
定义1:
设有平面或空间中的点集k,
若k中任意两点p和q的连线pq上的所有点都在k内,称k是凸的.
定理7.6.1
通过画出在区域内不相交的对角线,令hn表示具有n+1条边的凸多边形区域分成三角形区域的方法数,定义h1=1,则hn满足如下递推关系:
hn=h1hn-1+
h2hn-2+…+ h1hn-1+
hn-1h1=
(n≥2)
该递推关系的解为:
hn=
7.7 指数生成函数
定义1:
设序列h0, h1, h2,…,
hn,…, 定义其指数生成函数为:
g(e)(x)= =
h0+ h1 + h2 +…+ hn
…
定理7.7.1
令S={n1.a1, n2.a2,…,
nk.ak }为一多重集,其中: n1,
n2,…, nk
均为非负整数,令hn表示S的n排列数,则序列h0,
h1, h2,…,
hn,…的指数生成函数g(e)(x)由:
g(e)(x)=fn1(x). fn2(x)…
fnk(x)
(1)
给定,其中,对于I=1,2,…k, fni(x)= 1+ + +…+
.
例1:
如果把棋盘上偶数个方格涂成红色,试确定用红色,白色和蓝色对1行n列棋盘上的方格涂色方法数.
