生成函数在求解递推关系中的应用研究

摘要生成函数在组合问题中的应用既灵活又非常广泛,利用生成函数来求解递推关系是一种有效而特别的方法。

中图分类号:0174文献标识码:A

很多组合计数问题往往归结为求某个数列{an}的通项公式,而直接求某些数列的通项公式比较难,但可以建立数列所满足的递推关系,生成函数是求解数列递推关系的一种重要而有效的方法,本文主要讨论生成函数在求解递推关系中的应用,进而求出数列递推关系的一般项的表示公式。

1 生成函数的概念及性质

1.1 定义

设a0,a1,a2,…,an,…, 是一个数列,做形式幂级数f (x) = a0 + a1x + a2x2 +…+ anxn +…然后通过研究函数f (x) = aixi导出数列a0,a1,a2,…,an,…,的性质,则称f (x) = aixi为数列a0,a1,a2,…,an,…,的生成函数。

例如:数列1,,,,,…,,…对应的生成函数是f (x) = ln= x + x2 + x3 + … +xn+…;数列1,2,3,4,5,…,n,…对应的生成函数是f (x) == 1+ 2x + 3x2 + … +nxn-1 +…。

可见数列和它的生成函数是一一对应的,求得了生成函数,数列的通项就可以知道了,因此,可以用生成函数来求解递推数列的通项。

1.2 下面给出生成函数的一些性质

设数列{an},{bn},{cn}的生成函数分别是A(x),B(x),C(x)。

性质1若bn = an,为常数,则B(x) =A(x)

性质2若cn = an + bn,则C(x) = A(x) + B(x)

性质3若bn = an+1,则B(x) =

性质4若bn = nan,为常数,则B(x) = A(x)

性质5若bn = nan, 则B(x) = xA"(x)

性质6若bn = ,则B(x) = ∫x0 A(x)dx

这些性质可以求某些递推数列的生成函数,在此就不证明,接下来主要讨论生成函数在求解递推关系的应用。

2 生成函数在求解递推关系中的应用

用生成函数不仅可以求解常系数线性齐次、非齐次递推关系,而且还可以求非线性递推关系和非常系数递推关系。

2.1 生成函数求解常系数线性齐次递推关系

例1、求没有两个0相邻的n位4元序列(即0,1,2,3,组成的序列)的个数。

解:设所求的个数为an,则对位4元序列的第一位数有如下两种选择方式:

(1)若n位序列的第一位不为0,则可为1,2,3中的任何一个,而剩下的n-1位序列无两个0相邻的个数为an-1,故由乘法原理,共有3an-2个。

(2)若n位序列的第一位为0,则第二位只能为1,2,3中的任何一个,而剩下的n-2位序列中两个相邻的个数为an-2,由乘法原理,共有3an-2个。因为(1)、(2)两种选择相互独立,则由加法原理,有:an = 3an-1 + 3an-2,又有a1 = 4,a2 = 15。

那么,可建立如下的带初值的递推关系:

用生成函数法求解这个递推关系,可得数列的通项。

设A(x) = a1 + a2x1 + a3x2 + a4x3 + …,

则有-3x·A(x) = -3a1x1 - 3a2x2 - 3a3x3 - 3a4x4 -…,

-3x2·A(x) = -3a1x2 - 3a2x3 - 3a3x4 - …,

将上面三式两边相加得

(1- 3x - 3x2)A(x) = a1 + (a2 - 3a1) x,代入初值a1 = 4,a2 = 15得A(x) =

由部分分式的方法设

A(x) ===+

即有

解得

所以

即有

2.2 生成函数求常系数线性非齐次递推关系

例2 求解递推关系

解:设f (x) = anxn为序列(a0,a1,a2,…,an,…)的生成函数

则

所以f (x) ==-= (2x)n - xn

则有an = 2n -1

2.3 生成函数求非线性递推关系

例3设有n个数b1,b2,…,bn的连乘积为b1·b2·b3·…·bn。试求不同的结合方式数(加括号的方式)

解:设不同的结合方式数为an,定义a1 = 1 ,显然有a2 = 1。

经分析,由题意可导出如下的递推关系式:

需求解(*)式:设A(x) = anxn,则递推关系(*)的右边正是A(x)A(x)中xn的系数,从而有anxn = A(x) -x = A(x)A(x),即A2 - A + x = 0由此得到A(x) = (1 €? )

因为A(0) = 0,开方应该取负号,故A(x) ==- (1-4x)。展开得:

则有A(x) = (1 -),

2.4生成函数求非常系数线性齐次递推关系

例4 求解递推关系式

解:设f (x) = nanxn =nanxn,则由原关系可得

nanxn = [2n -(n-1)an-1]xn = 2nxn - x(n-1)an-1xn-1

即f (x) =- xf (x) -1

则f (x) ==( - ) = [2nxn - (-1)nxn]

所以有nan =[2n - (-1)n]即有an = [2n - (-1)n]

2.5 生成函数求线性常系数递推关系组

例5 求解递推关系组

解:由题知a0 = 2,b0 = -1,则a1 = 1,b1 = 原递推关系可变为

设A(x) =anxn ,B(x) = bnxn,则原递推组可表示为

整理得

方程组的系数行列式

从而

所以有an = 4-2·()n,同理可求得bn = ()n -2

2.6 生成函数解高考数列递推关系试题

例6 设数列{an}:a1 = 4,an = an-1 + 3(n-1),(n≥2),求通项an。

解:设f (x) = anxn是序列(a1,a2,…,an,…)的生成函数,将题目的关系式代入f (x)中有

解得f (x) =+,由文[3]中1.4节二项式定理的推论7可得,

故有f (x) =+

所以有

参考文献

[1]李乔.组合数学基础[M].高等教育出版社,1993.

[2]屈婉玲.组合数学[M].北京大学出版社,1989.

[3]孙世新,张先迪.组合原理及其应用[M].国防工业出版社,2006.

[4]卢开澄,卢华明.组合数学[M].清华大学出版社,1997.

[5]张禾瑞.高等代数[M].高等教育出版社,1997

[6][GrKn]D.H.Greene and D.E.Knuth,Mathematics for the analysis of

Algorithms,Birkhauser,Boston,1981.

推荐访问:求解 函数 生成 关系 研究