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

熊傳霞

摘 要：該文論述了生成函數的概念及相關理論，生成函數方法作為一種特殊的輔助計算方法，能簡單而有效的解決組合數學和計算數學中的遞推關系、排列組合等問題。文章介紹了如何使用生成函數方法解決遞推關系問題，并且結合實例中進行了應用。

關鍵詞：遞推關系 生成函數 應用 計算

中圖分類號：O174 文獻標識碼：A 文章編號：1674-098X（2016）04（a）-0154-02

遞推關系是數學中特有的思維方法，探求某一事物、現象所遵循的一般規律，并用數學語言表達出來，在數學學科的所有分支中都有著重要的應用。比如：求解排列組合問題、歸納數列遞推關系問題都需要用到遞推思維方法。但是，遞推思維方法比較抽象，遞推關系的求解一般也比較困難。而生成函數正是解決這一難題最好的數學工具，經過長期的理論實踐研究，生成函數方法已經發展成為了解決遞推關系問題的重要工具之一。

1 生成函數的相關知識

1.1 生成函數的定義

生成函數又稱為做母函數。生成函數方法是離散數學的一個重要分支，生成函數方法把離散數學和連續數學串聯溝通在一起。在分析組合數學問題中，在組合計數方面生成函數具有天生的優越性，成為了解決組合計數問題的強大工具。

生成函數的中心思想是：首先使用多項式或冪級數把需要研究的數列合為一個整體，通過研究多項式或冪級數的性質以及使用合并同類項的方法，來研究數列的性質，從而得到相關的結論。

1.2 生成函數的基本性質

1.3 生成函數的計算

計算生成函數系數的方法是把比較復雜的生成函數化簡為簡單的二次式類型，或若干個二項式類型的生成函數的積，這樣就比較容易得出所需的的系數。需要用到牛頓二項式定理及其生成函數的性質。

2 數學中的遞推關系問題

遞推關系幾乎在所有的數學領域中都占據著重要的比例和廣泛應用。通常情況下遞推關系的求解比較困難，僅局限于使用遞推關系的一些定義很多問題是不能解決的，并且所涉及的領域也很廣。遞推關系的研究還可以追溯到斐波納契關系：≥0，F0=0，F1=1，它是比薩的數學家Leonardo最先給出的。

線性遞推關系可定義為，數列必須有連續個k項滿足，滿足此式的數列叫它為數列的一個遞推關系式。

由遞推關系式及滿足k個初始值可以確定的一個數列叫做遞推數列。因此，無論是牽涉到遞推數列的證明題，解析題，還是需要建立遞推關系式的綜合題，那么解決遞推數列的核心是求通項公式，也是最基本的步驟。

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

數學中很多求排列組合計算問題時通常都會歸結為求某個數列的通項公式，而直接求某些數列的通項公式常常比較艱難，但可以求所滿足的遞推關系，那么生成函數是首選的方法，并且生成函數是求遞推數列關系的一種重要的思維和常用的方法。

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

在上述例中使用了錯位相加減的方法，大家發現，使用生成函數的方法來求解比傳統的方法容易得多。

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

4 結語

該文將生成函數分為普通型生成函數和指數則型生成函數通過問題引入、問題分析、問題解決、問題延伸的步驟介紹了應用生成函數法求解常系數線性非齊次遞推關系和常系數線性齊次遞推關系。通過例子可以看出，在遞推關系問題的求解上，生成函數方法是比較有效，已經得到了普遍廣泛的應用。

參考文獻

[1]羅建林，張艷紅.利用生成函數求解遞推關系[J].科技信息，2009（28）：386.

[2]肖啟明.利用母函數法求解一類遞推關系[J].宜春學院學報，2006（4）：1-3.

[3]程曉生.淺談生成函數的應用[J].科技風，2013（20）：183.

[4]安永紅，張春霞.生成函數的若干應用[J].呼倫貝爾學院學報，2010（3）：78-80.