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

熊傳霞

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

關(guān)鍵詞：遞推關(guān)系 生成函數(shù) 應(yīng)用 計算

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

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

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

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

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

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

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

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

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

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

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

線性遞推關(guān)系可定義為，數(shù)列必須有連續(xù)個k項滿足，滿足此式的數(shù)列叫它為數(shù)列的一個遞推關(guān)系式。

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

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

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

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

在上述例中使用了錯位相加減的方法，大家發(fā)現(xiàn)，使用生成函數(shù)的方法來求解比傳統(tǒng)的方法容易得多。

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

4 結(jié)語

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

參考文獻

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

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

[3]程曉生.淺談生成函數(shù)的應(yīng)用[J].科技風(fēng)，2013（20）：183.

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