生成函數(shù)在遞推關(guān)系問(wèn)題上的應(yīng)用

■崔龍飛 劉浩東

武警警官學(xué)院

1 生成函數(shù)的相關(guān)知識(shí)

1.1 生成函數(shù)的定義

母函數(shù)又叫生成函數(shù)，作為離散數(shù)學(xué)的一個(gè)重要部分的生成函數(shù)方法，其將離散數(shù)學(xué)串聯(lián)溝通起連續(xù)數(shù)學(xué)，在對(duì)組合數(shù)學(xué)問(wèn)題進(jìn)行分析時(shí)，在組合計(jì)數(shù)方面生成函數(shù)具有天生的優(yōu)越性，是對(duì)組合計(jì)數(shù)問(wèn)題解決的工具。

將需要研究的數(shù)列運(yùn)用冪級(jí)數(shù)或多項(xiàng)式合成一個(gè)整體，通過(guò)對(duì)多項(xiàng)式或冪級(jí)數(shù)的性質(zhì)和對(duì)合并同類項(xiàng)的方法這個(gè)方法的使用進(jìn)行研究，最終得到相關(guān)的結(jié)論，這就是生成函數(shù)的中心思想。

1.2 生成函數(shù)的基本性質(zhì)

假設(shè)，序列（ak），（bk）的生成函數(shù)的分別是：

P(x)=a0+a1x1+a2x2+…Q(x)=b0+b1x1+b2x2…

生成函數(shù)和數(shù)列之間是一一對(duì)應(yīng)的，因此要對(duì)兩個(gè)數(shù)列之間的關(guān)系進(jìn)行研究可以轉(zhuǎn)化為研究它們的生成函數(shù)的關(guān)系，從而就方便解題[1]。

1.3 生成函數(shù)的計(jì)算

將相對(duì)復(fù)雜的生成函數(shù)化簡(jiǎn)成簡(jiǎn)單的二次式類型，或者是若干個(gè)二項(xiàng)式類型的生成函數(shù)的積，這就是計(jì)算生成函數(shù)系數(shù)的方式，從而不難得出所需要的xk的系數(shù)。要運(yùn)用到牛頓二項(xiàng)式定理和它的生成函數(shù)的性質(zhì)。

牛頓二項(xiàng)式定理：

舉例求解生成函數(shù)：

求得生成函數(shù)的系數(shù)可借助牛頓二項(xiàng)式定理。

數(shù)學(xué)中的遞推關(guān)系問(wèn)題

在數(shù)學(xué)領(lǐng)域中，遞推關(guān)系在其有著很重要的位置和其應(yīng)用也很廣泛。一般情況下求解遞

推關(guān)系并容易，如果只是運(yùn)用遞推關(guān)系的一些定義是不能解決很多問(wèn)題，它關(guān)聯(lián)到很廣領(lǐng)域。

研究遞推關(guān)系是追溯到斐波納契關(guān)系：Fn+2=Fn+1+Fn，n≥0，F(xiàn)0=0，F(xiàn)1=1，最先給出的是比薩的數(shù)學(xué)家Leonardo。

數(shù)列xn必須有連續(xù)個(gè)k項(xiàng)滿足xn+k=f(xn+k-1，xn+k-2，…，xn)，滿足此式的數(shù)列叫它為數(shù)列xn的一個(gè)遞推關(guān)系式，這就是線性遞推關(guān)系定義。

由遞推關(guān)系式和滿足k個(gè)初始值可以確定的一個(gè)數(shù)列xn叫做遞推數(shù)列。所以，不管是設(shè)計(jì)到遞推數(shù)列解析題，證明題，還是需要建立遞推關(guān)系式的綜合題，則求通項(xiàng)公式就是解決遞推數(shù)列的核心，也是最基本的步驟[2]。

3 生成函數(shù)法應(yīng)用于遞推關(guān)系的求解

不少求排列組合計(jì)算問(wèn)題的時(shí)候一般都會(huì)歸結(jié)為求某個(gè)數(shù)列xn的通項(xiàng)公式，直接一些求數(shù)列的通項(xiàng)公式一般不是那么容易，然而可以求所滿足的遞推關(guān)系，則首選的方法就是生成函數(shù)，在求遞推數(shù)列關(guān)系，一種重要的思維與常用的方法就包括生成函數(shù)。

3.1 生成函數(shù)法應(yīng)用到常系數(shù)線性齊次遞推關(guān)系上

定義：常系數(shù)線性齊次遞推關(guān)系

將關(guān)于an的常系數(shù)線性齊次遞推關(guān)系轉(zhuǎn)化為an的生成函數(shù)G(x)，通常運(yùn)用錯(cuò)位相減法，然后運(yùn)用代數(shù)方法求G(x)，冪級(jí)數(shù)的形式把它把展成出來(lái)，xn的系數(shù)an就是所求，這就是使用生成函數(shù)法解常系數(shù)線性齊次遞推關(guān)系的基本思想。

在上面例中運(yùn)用到的方法，即錯(cuò)位相加減法，可以得知，和傳統(tǒng)方法相比，運(yùn)用生成函數(shù)的方法來(lái)求解an更加容易。

3.2 生成函數(shù)法應(yīng)用在常系數(shù)線性非齊次遞推關(guān)系上

使用生成函數(shù)法解常系數(shù)線性非齊次遞推關(guān)系的基本思想是：設(shè)序列an的生成函數(shù)是Q(X)=anxn將關(guān)于an的常系數(shù)線性非齊次遞推關(guān)系代入Q(X)=anxn的右端，得到Q(x)的方程，Q(X)的解求得出來(lái)。再用冪級(jí)數(shù)的形式把它展示出來(lái)，xn的系數(shù)an就是所求。

其中a是實(shí)數(shù)；b是常數(shù)；k是正整數(shù)。

4 結(jié)語(yǔ)

本文通過(guò)對(duì)問(wèn)題進(jìn)行引入、分析、解決和延伸，對(duì)生成函數(shù)法求解常系數(shù)線性非齊次遞推關(guān)系與常系數(shù)線性齊次遞推關(guān)系。通過(guò)舉例分析，生成函數(shù)運(yùn)用到遞推關(guān)系問(wèn)題的求解上是很有用的，已經(jīng)廣泛運(yùn)用到數(shù)學(xué)中。