淺論生成函數在組合數學中的應用

魏建剛

【摘 要】發生函數是組合數學中許多問題的首要解決方法，他可以將很多數學問題轉化為生成函數問題，從而簡單明了提供解題思路與方法，使得復雜困難的問題迎刃而解。本文主要研究生成函數在組合計數、整數拆分、遞推問題和恒等式證明等問題中的應用，從而體現生成函數在組合數學中的作用。

【關鍵詞】組合函數；數學；應用

引言

所謂生成函數也就是母函數，又被稱為發生函數，它是鏈接離散函數和連續函數的結合點，是組合數學中許多問題的首要解決方法。可以將很多數學問題轉化為生成函數問題，從而簡單明了的為數學中的許多問題提供解題思路與方法，使得復雜困難的問題迎刃而解。

1.生成函數在組合計數中的應用

生成函數作為在組合計數學習中極其重要的一個工具，在處理某些相關問題時運用生成函數，往往會使問題簡單明了。

例1.現有1分2分5分郵票，郵票可重復使用，則能貼出那些面值的郵票？每種面值有多少種貼法？

解：a 把表示為用1分2分5分郵票貼出面值為n的有票的不同貼法，則我們可以得到一個數列{a }的生成函數f（x）=∑n≥0anxn=（1+x+x2+x3+…）（1+x2+x4+…）（1+x5

+x10+…）

=1+x+2x2+2x3+3x4+4x5+…

根據生成函數展開式可知

x表示貼出面值為1分的方案有1種：1分

2x 表示貼出面值為2分的方案有2種：1分+1分，2分

2x 表示貼出面值為3分的方案有2種：1分+1分+1分，2分+1分

3x 表示貼出面值為4分的方案有3種：1分+1分+1分+1分，2分+1分+1分，2分+2分

……

由生成函數就可以看出，可以貼出那些面值的郵票，貼出n面值的郵票有多少種貼法。

通過上述例子我們可以看出，在現實學習生活中，很多問題看似復雜，處理起來毫無頭緒，但只要我們合理的運用生成函數處理為，很多難題復雜題迎刃而解，且過程簡單明了，容易掌握。

2.生成函數在整數拆分中的應用

在很多數學實際問題中， 往往會整數拆分與組合數學聯系在一起，既將組合數學中的很多實際問題看做整數拆分問題。

例2.求方程x +x +x +x =12，滿足0≤x ≤5，1≤x ≤4，3≤x ≤7，4≤x ≤6的整數解個數。

解：此類問題可看做是整數拆分問題，將12拆分成滿足題干4個條件的整數和的方法問題。

通過分析可以構建如下生成函數g（x）=（1+x+…+x ）（x+x +x +x ）（x +x +…+x ）（x +x +x ）將函數展開，則其展開式中x 的系數a 則為符合條件的整數的放法數。

由上述問題不難看出，在組合數學中，整數拆分占有很重要的位置，用于研究所拆分函數的某些性質和所求結果，而生成函數又是解決整數拆分的重要手段和有效工具。

3.生成函數在線性遞推數列通項中的應用

遞推關系是數學中運用特別多的一種工具形式關系，很多數學中的關系都可以轉化為遞推關系，但是對于遞推關系的處理上存在著一定的困難。此部分以遞推數列通項為例，簡要說明生成函數在數學遞推關系中的重要作用。

4.生成函數在組合恒等式中的證明

在組合數學中往往會涉及到各種不同類型的組合恒等式的證明，融二項式系數恒等式、整數拆分恒等式等。在這些恒等式證明過程中往往存在計算量大或證明復雜等問題，將生成函數運用進恒等式證明可以使問題一目。以二項式為例，它在數學學習中占有很重要的位置，且在其他組合問題證明中往往也會運用二項式展開式系數。做此類題的一般先觀察所正等式兩邊結構特點，然后構造生成函數，最后進行比較證明。

例3求證

分析：由于恒等式比較復雜運用組合計數公式化簡存在一定的困難，但是根據左端式子規律構造二項式展開式的生成函數模型，對模型進行化簡處理，從而證明等式成立

解：構造生成函數g（x）=（1+x）+2（1+x） +3（1+x） +…+n（1+x） 由此易發現，g（x）中x 所對應的系數應為恒等式的左端。

則我們對g（x）進行化簡求和，利用錯位相減法得到g（x）= 由此可得x 所對應的

項的系數為 既左邊等于右邊，則恒等式成立。

運用二項式的展開式證明組合函數的恒等問題是組合數學恒等式證明的重要方法，而在二項式的展開式處理上，又應用生成函數作為重要工具。關鍵在于如何適當的選取多個二項式，使其對應項的系數恰為所要證的恒等式，以此為生成函數，進而證明恒等成立。

5.總結

生成函數作為組合數學中的重要工具，在其應用中極為廣泛，在此文章中我們住研究生成函數在遞推關系中的應用，整數拆分中的應用，在組合計數問題中的應用及生成函數在恒等式證明中的應用，事實上生成函數的應用不僅僅局限于此。

【參考文獻】

[1]王中平.生成函數在組合數學中的若干應用[J].貴陽學院學報（自然科學版），2016.01：1-7

[2]唐海軍，余躍玉，李合朋.數學專業學生“組合數學”學習探析[J].樂山師范學院學報，2013.12：120-123