生成函數在遞推關系問題上的應用

■崔龍飛 劉浩東

武警警官學院

1 生成函數的相關知識

1.1 生成函數的定義

母函數又叫生成函數，作為離散數學的一個重要部分的生成函數方法，其將離散數學串聯溝通起連續數學，在對組合數學問題進行分析時，在組合計數方面生成函數具有天生的優越性，是對組合計數問題解決的工具。

將需要研究的數列運用冪級數或多項式合成一個整體，通過對多項式或冪級數的性質和對合并同類項的方法這個方法的使用進行研究，最終得到相關的結論，這就是生成函數的中心思想。

1.2 生成函數的基本性質

假設，序列（ak），（bk）的生成函數的分別是：

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

生成函數和數列之間是一一對應的，因此要對兩個數列之間的關系進行研究可以轉化為研究它們的生成函數的關系，從而就方便解題[1]。

1.3 生成函數的計算

將相對復雜的生成函數化簡成簡單的二次式類型，或者是若干個二項式類型的生成函數的積，這就是計算生成函數系數的方式，從而不難得出所需要的xk的系數。要運用到牛頓二項式定理和它的生成函數的性質。

牛頓二項式定理：

舉例求解生成函數：

求得生成函數的系數可借助牛頓二項式定理。

數學中的遞推關系問題

在數學領域中，遞推關系在其有著很重要的位置和其應用也很廣泛。一般情況下求解遞

推關系并容易，如果只是運用遞推關系的一些定義是不能解決很多問題，它關聯到很廣領域。

研究遞推關系是追溯到斐波納契關系：Fn+2=Fn+1+Fn，n≥0，F0=0，F1=1，最先給出的是比薩的數學家Leonardo。

數列xn必須有連續個k項滿足xn+k=f(xn+k-1，xn+k-2，…，xn)，滿足此式的數列叫它為數列xn的一個遞推關系式，這就是線性遞推關系定義。

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

3 生成函數法應用于遞推關系的求解

不少求排列組合計算問題的時候一般都會歸結為求某個數列xn的通項公式，直接一些求數列的通項公式一般不是那么容易，然而可以求所滿足的遞推關系，則首選的方法就是生成函數，在求遞推數列關系，一種重要的思維與常用的方法就包括生成函數。

3.1 生成函數法應用到常系數線性齊次遞推關系上

定義：常系數線性齊次遞推關系

將關于an的常系數線性齊次遞推關系轉化為an的生成函數G(x)，通常運用錯位相減法，然后運用代數方法求G(x)，冪級數的形式把它把展成出來，xn的系數an就是所求，這就是使用生成函數法解常系數線性齊次遞推關系的基本思想。

在上面例中運用到的方法，即錯位相加減法，可以得知，和傳統方法相比，運用生成函數的方法來求解an更加容易。

3.2 生成函數法應用在常系數線性非齊次遞推關系上

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

其中a是實數；b是常數；k是正整數。

4 結語

本文通過對問題進行引入、分析、解決和延伸，對生成函數法求解常系數線性非齊次遞推關系與常系數線性齊次遞推關系。通過舉例分析，生成函數運用到遞推關系問題的求解上是很有用的，已經廣泛運用到數學中。