生成函數在求解遞推關系中的應用研究

摘要生成函數在組合問題中的應用既靈活又非常廣泛，利用生成函數來求解遞推關系是一種有效而特別的方法。

中圖分類號: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.