淺論生成函數(shù)在組合數(shù)學(xué)中的應(yīng)用

魏建剛

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

【關(guān)鍵詞】組合函數(shù)；數(shù)學(xué)；應(yīng)用

引言

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

1.生成函數(shù)在組合計(jì)數(shù)中的應(yīng)用

生成函數(shù)作為在組合計(jì)數(shù)學(xué)習(xí)中極其重要的一個(gè)工具，在處理某些相關(guān)問題時(shí)運(yùn)用生成函數(shù)，往往會(huì)使問題簡(jiǎn)單明了。

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

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

+x10+…）

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

根據(jù)生成函數(shù)展開式可知

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分

……

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

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

2.生成函數(shù)在整數(shù)拆分中的應(yīng)用

在很多數(shù)學(xué)實(shí)際問題中， 往往會(huì)整數(shù)拆分與組合數(shù)學(xué)聯(lián)系在一起，既將組合數(shù)學(xué)中的很多實(shí)際問題看做整數(shù)拆分問題。

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

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

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

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

3.生成函數(shù)在線性遞推數(shù)列通項(xiàng)中的應(yīng)用

遞推關(guān)系是數(shù)學(xué)中運(yùn)用特別多的一種工具形式關(guān)系，很多數(shù)學(xué)中的關(guān)系都可以轉(zhuǎn)化為遞推關(guān)系，但是對(duì)于遞推關(guān)系的處理上存在著一定的困難。此部分以遞推數(shù)列通項(xiàng)為例，簡(jiǎn)要說明生成函數(shù)在數(shù)學(xué)遞推關(guān)系中的重要作用。

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

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

例3求證

分析：由于恒等式比較復(fù)雜運(yùn)用組合計(jì)數(shù)公式化簡(jiǎn)存在一定的困難，但是根據(jù)左端式子規(guī)律構(gòu)造二項(xiàng)式展開式的生成函數(shù)模型，對(duì)模型進(jìn)行化簡(jiǎn)處理，從而證明等式成立

解：構(gòu)造生成函數(shù)g（x）=（1+x）+2（1+x） +3（1+x） +…+n（1+x） 由此易發(fā)現(xiàn)，g（x）中x 所對(duì)應(yīng)的系數(shù)應(yīng)為恒等式的左端。

則我們對(duì)g（x）進(jìn)行化簡(jiǎn)求和，利用錯(cuò)位相減法得到g（x）= 由此可得x 所對(duì)應(yīng)的

項(xiàng)的系數(shù)為 既左邊等于右邊，則恒等式成立。

運(yùn)用二項(xiàng)式的展開式證明組合函數(shù)的恒等問題是組合數(shù)學(xué)恒等式證明的重要方法，而在二項(xiàng)式的展開式處理上，又應(yīng)用生成函數(shù)作為重要工具。關(guān)鍵在于如何適當(dāng)?shù)倪x取多個(gè)二項(xiàng)式，使其對(duì)應(yīng)項(xiàng)的系數(shù)恰為所要證的恒等式，以此為生成函數(shù)，進(jìn)而證明恒等成立。

5.總結(jié)

生成函數(shù)作為組合數(shù)學(xué)中的重要工具，在其應(yīng)用中極為廣泛，在此文章中我們住研究生成函數(shù)在遞推關(guān)系中的應(yīng)用，整數(shù)拆分中的應(yīng)用，在組合計(jì)數(shù)問題中的應(yīng)用及生成函數(shù)在恒等式證明中的應(yīng)用，事實(shí)上生成函數(shù)的應(yīng)用不僅僅局限于此。

【參考文獻(xiàn)】

[1]王中平.生成函數(shù)在組合數(shù)學(xué)中的若干應(yīng)用[J].貴陽學(xué)院學(xué)報(bào)（自然科學(xué)版），2016.01：1-7

[2]唐海軍，余躍玉，李合朋.數(shù)學(xué)專業(yè)學(xué)生“組合數(shù)學(xué)”學(xué)習(xí)探析[J].樂山師范學(xué)院學(xué)報(bào)，2013.12：120-123