生成函數(shù)與指數(shù)生成函數(shù)的研究與應(yīng)用

1、生成函數(shù)與指數(shù)生成函數(shù)的研究與應(yīng)用生成函數(shù)與指數(shù)生成函數(shù)的研究與應(yīng)用作者：陳功 學(xué)號(hào)：ZY1021104摘 要本文系統(tǒng)的論述了生成函數(shù)與指數(shù)生成函數(shù)組合數(shù)學(xué)和計(jì)算數(shù)學(xué)中研究與應(yīng)用.生成函數(shù)又稱母函數(shù)，它是在冪級(jí)數(shù)和多項(xiàng)式理論的基礎(chǔ)上建立的.生成函數(shù)可分為普通型生成函數(shù)和指數(shù)型生成函數(shù)，他們?cè)谟?jì)算問題中有各自的應(yīng)用范圍.本文首先介紹了生成函數(shù)的基本理論，包括基本概念、性質(zhì)及其系數(shù)計(jì)算的一些技巧.其次介紹了普通型生成函數(shù)和指數(shù)型生成函數(shù)的基本模型及其應(yīng)用范圍.最后則具體討論了生成函數(shù)法在求解遞推關(guān)系和整數(shù)分拆中的應(yīng)用.通過本文的總結(jié)，可以使人們對(duì)生成函數(shù)有一個(gè)比較清晰的認(rèn)識(shí)，更加系統(tǒng)的掌握生成函數(shù)

2、這一數(shù)學(xué)工具.關(guān)鍵詞： 生成函數(shù)；普通型生成函數(shù)；指數(shù)型生成函數(shù)目 錄1生成函數(shù)與指數(shù)生成函數(shù)的研究與應(yīng)用I1 前言12 基本知識(shí)22.1基本概念22.2基本性質(zhì)32.3生成函數(shù)的計(jì)算43 通型生成函數(shù)模型73.1問題的提出73.2普通型生成函數(shù)模型及其應(yīng)用74 指數(shù)型生成函數(shù)模型114.1問題的提出114.2指數(shù)型生成函數(shù)模型及其應(yīng)用114.3指數(shù)型生成函數(shù)系數(shù)的計(jì)算技巧135 生成函數(shù)在遞推關(guān)系中的應(yīng)用165.1 生成函數(shù)法在常系數(shù)線性齊次遞推關(guān)系上的應(yīng)用165.2 生成函數(shù)法在常系數(shù)線性非齊次遞推關(guān)系上的應(yīng)用186 生成函數(shù)在整數(shù)分拆中的應(yīng)用22結(jié) 論24目前國內(nèi)外許多數(shù)學(xué)研究者都對(duì)生成

3、函數(shù)的應(yīng)用范圍進(jìn)行了大量的研究，成果顯著.但在這些文獻(xiàn)中，知識(shí)點(diǎn)不夠系統(tǒng)全面.本文汲取了他們的勞動(dòng)成果，通過大量的比較研究，比較系統(tǒng)的給出了生成函數(shù)的基本理論及其應(yīng)用模型.24- 23 -1 前言 生成函數(shù)又稱母函數(shù)，是計(jì)數(shù)問題中既簡單又精巧的數(shù)學(xué)模型，也是組合數(shù)學(xué)的一個(gè)重要理論和工具. 1720年前后De Moivre首先使用了組合生成函數(shù),通過使用生成函數(shù)得到斐波那契數(shù)的一個(gè)公式.1748年歐拉在他的著作中對(duì)分拆問題使用了生成函數(shù)，而他同時(shí)對(duì)概率生成函數(shù)的工作是18世紀(jì)后期發(fā)展起了的組合生函數(shù)理論的原始動(dòng)力.最早提出生成函數(shù)的人是法國數(shù)學(xué)家LaplaceP.S.在其1812年出版的概率的分

4、析理論中明確提出“生成函數(shù)的計(jì)算”，書中對(duì)生成函數(shù)思想奠基人Euler L在18世紀(jì)對(duì)自然數(shù)的分解與合成的研究做了延伸與發(fā)展，生成函數(shù)的理論由此基本建立.曹汝成在生成函數(shù)中提出了車問題及其解法，Alan Tucker在應(yīng)用組合數(shù)學(xué)中提出了生成函數(shù)系數(shù)的具體解法及一個(gè)求和的算法，RichardA.Brualdi具體提出了生成函數(shù)與遞推函數(shù)的關(guān)系等.每本著作中作者所提的概念、所引用的符號(hào)以及表述方法都有一些共同點(diǎn)和差異.本文主要是系統(tǒng)的總結(jié)生成函數(shù)的基本理論和應(yīng)用問題，使人們對(duì)生成函數(shù)有一個(gè)清晰的認(rèn)識(shí)，比較簡便的學(xué)會(huì)生成函數(shù)這一數(shù)學(xué)工具.本文第二部分主要回顧了生成函數(shù)的基本概念及其性質(zhì)，計(jì)算生成函

5、數(shù)系數(shù)的一些技巧.在第三部分和第四部分中主要介紹了普通型生成函數(shù)和指數(shù)型生成函數(shù)的基本模型及其應(yīng)用范圍.第五部分和第六部分則具體討論了生成函數(shù)在遞推關(guān)系和整數(shù)分拆中的應(yīng)用.2 基本知識(shí)2.1基本概念 計(jì)數(shù)問題是組合數(shù)學(xué)的一個(gè)重要內(nèi)容，而生成函數(shù)又是解決計(jì)數(shù)問題的一個(gè)重要的一般性的處理方法. 冪級(jí)數(shù)是我們所熟悉的多項(xiàng)式，我們定義為數(shù)列的生成函數(shù)，通常記為1 . 生成函數(shù)的中心思想是：首先使用多項(xiàng)式或冪級(jí)數(shù)把需要研究的數(shù)列合為一個(gè)整體，通過研究多項(xiàng)式或冪級(jí)數(shù)的性質(zhì)以及使用合并同類項(xiàng)的方法，來研究數(shù)列的性質(zhì)，從而得到相關(guān)的結(jié)論.例如 數(shù)列 的生成函數(shù)是 這個(gè)生成函數(shù)的值為用了非常簡潔緊湊的方式顯示了

6、上述數(shù)列的序列信息.下面列舉了幾個(gè)常見的生成函數(shù)2.(1)(2)(3)(4)(5)(6)(7)(8)(9)2.2基本性質(zhì)首先假定，序列，的生成函數(shù)分別為因?yàn)樯珊瘮?shù)與數(shù)列之間是一一對(duì)應(yīng)的關(guān)系，所以研究兩個(gè)數(shù)列之間的關(guān)系可以轉(zhuǎn)化為研究其生成函數(shù)的關(guān)系，這樣就給解題帶來了許多便利.線性性質(zhì)(1) 若 ，則 (2) 若 ，則 乘積性質(zhì) (3) 若 =，則 移位性質(zhì)(4) 若 ，則 (5) 若 ，則 ）(6) 若 ，則 =(7) 若 ，則 =，其中是收斂的換元性質(zhì)(8) 若 ，則 求導(dǎo)與積分性質(zhì)(9) 若 ，則 (10) 若 ，則 =2.3生成函數(shù)的計(jì)算 計(jì)算生成函數(shù)系數(shù)的方法是把比較復(fù)雜的生成函數(shù)化

7、簡為簡單的二次式類型，或若干個(gè)二項(xiàng)式類型的生成函數(shù)的積，這樣就比較容易得出所需的的系數(shù).我們需要用到牛頓二項(xiàng)式定理及其生成函數(shù)的性質(zhì).牛頓二項(xiàng)式定理，設(shè)實(shí)數(shù)，對(duì)一切有 其中=，當(dāng)時(shí)，變成我們所熟悉的二項(xiàng)式定理特別的當(dāng)時(shí)， 例1 求解。解 = =利用牛頓二項(xiàng)式求得生成函數(shù)的系數(shù).例2 已知，求解的值.解= = ，和在2.1中已注明，本題利用生成函數(shù)的加法運(yùn)算及其性質(zhì)求得.例3 在中的系數(shù)，？解= = 中的系數(shù)是即15，所以的系數(shù)是15.同理可得 =3 通型生成函數(shù)模型3.1問題的提出在現(xiàn)實(shí)生活中我們經(jīng)常遇見類似于這樣的問題：5個(gè)蘋果，4個(gè)橘子，3個(gè)梨，從中選出4個(gè)水果的組合數(shù)，及其組合方案.當(dāng)然

8、，通過列舉法可以來解決上述問題，但當(dāng)水果的種類和數(shù)量變多時(shí)，應(yīng)用列舉法就困難許多.在本節(jié)，我們?cè)诮M合問題中引入了生成函數(shù)法，使解題的過程更加簡便.3.2普通型生成函數(shù)模型及其應(yīng)用(1) 求的組合數(shù)，這是普通集合的組合問題.例1 現(xiàn)在有n個(gè)不同的球，求從中選出三個(gè)球的組合數(shù).解 顯然根據(jù)以前的學(xué)習(xí)，我們可以得到三個(gè)球的組合數(shù)為，一般的對(duì)于r組合數(shù)有，.我們知道是二項(xiàng)式中的系數(shù)，所以我們可以用多項(xiàng)式因子的乘積來表示題意信息，因子相乘后拆開的系數(shù)就是對(duì)應(yīng)的所選的組合數(shù)，即可用生成函數(shù)來解決此題.(2)求,的組合數(shù).例2 下面我們來解決3.1中所提出的問題.解 我們可以用方程整數(shù)解的方法來對(duì)這一組合問

9、題建模，3.1中的問題我們可以表示為= 4的形式，其中分別代表選取蘋果，橘子，梨的個(gè)數(shù)，05, 04, 03.基于多項(xiàng)式，我們想要建立多項(xiàng)式因子的乘積，使得當(dāng)這些因子乘開時(shí)，得到所有的乘積，拆開后所得多項(xiàng)式中的系數(shù)就是選出4個(gè)水果的組合數(shù)，所以我們需要三個(gè)因子，每個(gè)因子應(yīng)該包含的可能取值.即 （1+），（1+），（1+）我們所需的生成函數(shù)是上述三個(gè)因子的乘積，對(duì)于組合方案：我們可用代表蘋果，代表橘子，代表梨，展開多項(xiàng)式因子的乘積，使得=，即= 5的，的可能的取值是我們所求的組合方案，如當(dāng)= 1，= 1，= 2時(shí)的組合方案為：一個(gè)蘋果，一個(gè)橘子，兩個(gè)梨.當(dāng)水果的種類變多，數(shù)量變大時(shí)，就轉(zhuǎn)化為下面

10、（3）中的問題.(3)求的組合數(shù).由例二可知，就是將問題轉(zhuǎn)化為不定方程的非負(fù)整數(shù)解的問題.例3 從元集中可重復(fù)的選取個(gè)元作組合，每個(gè)元至少取一次，求作成的可重復(fù)的組合的個(gè)數(shù).解 設(shè)所求組合的個(gè)數(shù)為，則是展開式中的系數(shù)，=所以 綜合以上分析，我們可得下面定理.定理3.13 從元集合=， ，, . 中取個(gè)元素的組合數(shù)為，若限定元素出現(xiàn)的次數(shù)的集合為，則該組合數(shù)序列的生成函數(shù)為例4 現(xiàn)有無限多的一分，二分，五分，一角，五角的硬幣.確定這些硬幣湊成分錢的方法數(shù)的生成函數(shù).解 設(shè)湊成分錢的方法數(shù)為，則是方程=的非負(fù)整數(shù)解的個(gè)數(shù).即其生成函數(shù)為=（）（）（）（）（）化簡得=在組合型分配問題中我們也可以使用

11、這個(gè)數(shù)學(xué)模型，由此可得下面定理.定理3.23 (組合型分配問題)把個(gè)相同的球放入個(gè)不同的盒子， ，. ，中，限定盒子的容量集合為，則其分配方案數(shù)的生成函數(shù)為 在3.1節(jié)的問題中我們有=4，其中05, 04, 03.這相當(dāng)于把4個(gè)相同的球放入3個(gè)不同的盒子中，盒子的容量集合分，.我們稱對(duì)重復(fù)選擇問題進(jìn)行建模的生成函數(shù)為普通型生成函數(shù)3.4 指數(shù)型生成函數(shù)模型4.1問題的提出利用3.1節(jié)中所提出的問題，求從這12個(gè)水果中取4個(gè)水果進(jìn)行排列的排列數(shù).我們還是用代表蘋果，代表橘子，代表梨，展開成多項(xiàng)式因子的乘積，即使得=，其中 05, 04, 03.即=5中、的可能的取值是我們所求的組合方案，例如當(dāng)=

12、1，=1，=2時(shí)就是選取一個(gè)蘋果，一個(gè)橘子，兩個(gè)梨，以此類推.展開式中4次方項(xiàng)有，從這12個(gè)水果中選取4個(gè)進(jìn)行排列，其排列數(shù)應(yīng)是每一組合的排列數(shù)之和.例如項(xiàng)表示選一個(gè)蘋果，一個(gè)橘子，兩個(gè)梨，它所對(duì)應(yīng)的排列數(shù)為明白上述意思后，我們就不難得出上面所說的取四個(gè)元素的排列數(shù).即=80 通過一一列舉展開式中4次方項(xiàng)，再算出每個(gè)組合的排列數(shù)之和，這種方法既麻煩又復(fù)雜，漏掉任意一項(xiàng)就會(huì)非常麻煩.本節(jié)我們將引入指數(shù)型生成函數(shù)，它可以使排列問題的計(jì)算變得簡單方便.4.2指數(shù)型生成函數(shù)模型及其應(yīng)用首先我們給出指數(shù)型生成函數(shù)的定義，對(duì)于序列 ， ，. ，我們定義 = 稱為序列的指數(shù)型生成函數(shù)1. 由生成函數(shù)的思想我

13、們可以試著應(yīng)用指數(shù)型生成函數(shù)來解決4.1中提出的問題.我們令 =（）（）（）各多項(xiàng)式因子相乘后，取的系數(shù)，得80.我們還可以發(fā)現(xiàn)的系數(shù)正是從中選取個(gè)水果的排列數(shù).這并不是巧合，在排列問題中，我們不能將 =4 其中05, 04, 03，的每個(gè)整數(shù)解在可能的排列計(jì)數(shù)中記為1.實(shí)際上每個(gè)整數(shù)解必須貢獻(xiàn) ，用生成函數(shù)表示，的系數(shù)將是帶有下面系數(shù)的所有形式積 =其中05, 04, 03，上式中的指數(shù)和等于4，而我們知道指數(shù)型生成函數(shù)正好產(chǎn)生這種形式的形式積.可見指數(shù)型生成函數(shù)可以解決一般的有重復(fù)的排列問題，并且計(jì)算方便.例1 這5個(gè)字母組成的位數(shù)單詞的個(gè)數(shù)，其中出現(xiàn)奇數(shù)次，出現(xiàn)偶數(shù)次，其它的沒有次數(shù)要求

14、.解 所求的生成函數(shù)為 展開式中的系數(shù)就是位數(shù)單詞的排列數(shù).例2 將個(gè)不同的小球放入個(gè)不同的盒子中去，且要求每個(gè)盒子均不為空的方法數(shù).解 將個(gè)不同小球放入個(gè)不同的盒子中，相當(dāng)于個(gè)不同元素的次重復(fù)排列，即多重集合的排列數(shù)，且要求每個(gè)元素至少取一次.由此可得 = 綜合以上分析，我們可以得到下面定理.定理4.11 多重集合=的排列中，若限定元素出現(xiàn)的次數(shù)集合為()，則排列數(shù)的指數(shù)型生成函數(shù)為在排列型分配問題中我們也可以使用這個(gè)數(shù)學(xué)模型.例1中的問題我們可以轉(zhuǎn)化為，把個(gè)不同的球放5個(gè)不同的盒子中，盒子的容量集合分別為， ，可以得到相同的解.定理4.21 把個(gè)不同的球1，2，3，. 放入個(gè)不同的盒子，

15、，. ，中，限定盒子的容量集合為，則其分配方案數(shù)的生成函數(shù)為4.3指數(shù)型生成函數(shù)系數(shù)的計(jì)算技巧指數(shù)型生成函數(shù)的基本展開式是我們知道 (4.1)他們有相似的形式，我們考慮用它來化簡求解過程. 現(xiàn)在用來代替，可得 (4.2)并且我們可得 (4.3) (4.4)利用公式(4.1)-(4.4)可以使系數(shù)的計(jì)算過程變得相對(duì)簡單.對(duì)于例1 = = 所以展開式中的系數(shù)就是中的系數(shù)，簡化了解題過程.例2 求解。解 =+求得 5 生成函數(shù)在遞推關(guān)系中的應(yīng)用遞推關(guān)系是計(jì)算數(shù)學(xué)的一個(gè)重要工具，但其求解一般比較困難.本章介紹了生成函數(shù)法，使用它可以簡單有效的解決這類問題中的某些部分.5.1 生成函數(shù)法在常系數(shù)線性齊次

16、遞推關(guān)系上的應(yīng)用定義5.14 序列相鄰的項(xiàng)間有如下關(guān)系： ， 我們稱為序列的常系數(shù)線性齊次遞推關(guān)系.使用生成函數(shù)法解常系數(shù)線性齊次遞推關(guān)系的基本思想是：把關(guān)于的常系數(shù)線性齊次遞推關(guān)系轉(zhuǎn)化為的生成函數(shù)，通常采取錯(cuò)位相減法，再利用代數(shù)方法求解，將其展成冪級(jí)數(shù)的形式，的系數(shù)就是我們所求.例1 解 = (5.1) = (5.2) (5.3)將(5.1)-(5.3)相加得 解得=即 例25 遞推關(guān)系被稱為斐波那契關(guān)系，由斐波那契關(guān)系和初始條件所得到的數(shù)成為斐波那契數(shù).我們知道斐波那契數(shù)在數(shù)學(xué)領(lǐng)域的應(yīng)用廣泛，下面我們用生成函數(shù)法來求解.解 我們令 = 為， ，. 的生成函數(shù)，此時(shí)，我們有 = (5.4)

17、= (5.5) = (5.6)將(5.4)-(5.6)相加得=由于 ，以及我們有 =1得其中=，因?yàn)榭傻玫膬缂?jí)數(shù)的展開式中的系數(shù)為其中，.在上述兩例中我們使用了錯(cuò)位相加減的方法，我們發(fā)現(xiàn)，使用生成函數(shù)的方法來求解比傳統(tǒng)的方法容易得多.5.2 生成函數(shù)法在常系數(shù)線性非齊次遞推關(guān)系上的應(yīng)用定義5.26 序列相鄰的項(xiàng)間有如下關(guān)系： 其中是常數(shù)，均為非負(fù)整數(shù)，我們稱為序列的常系數(shù)線性非齊次遞推關(guān)系.使用生成函數(shù)法解常系數(shù)線性非齊次遞推關(guān)系的基本思想是：設(shè)序列的生成函數(shù)為，把關(guān)于的常系數(shù)線性非齊次遞推關(guān)系代入的右端，得到的方程，解出的解.再將其展成冪級(jí)數(shù)的形式，的系數(shù)就是我們所求.例3 ，其中.解 因此

18、 例48 在一個(gè)非常富有的國家，一天國王想要獎(jiǎng)賞他的一個(gè)臣子，就問他想要什么.這個(gè)臣子拿出一張88的棋盤，說他的要求并不高，第一個(gè)格子放一顆大麥粒，第二個(gè)格子放2顆，第三個(gè)格子放顆， ，第六十四格放顆，國王以為糧倉富足，這不是什么問題就答應(yīng)了，其實(shí)并不是這樣的.現(xiàn)在讓我們來計(jì)算一下一共需要多少顆大麥粒.解 設(shè)前個(gè)格子上的大麥粒數(shù)為，由題意可得=且，則我們令 為，. 的生成函數(shù).我們將代入上式右端，整理得=+可得 我們可得 這樣還是比較抽象，我們假設(shè)每秒運(yùn)送粒大麥粒，則需時(shí)間T=(年)5.1，5.2節(jié)的例子中所使用的求解方法可以推廣到求解任意的常系數(shù)階線性齊次或非齊次遞推關(guān)系中.即：我們所使用的

19、生成函數(shù)可以化為的形式，其中是次數(shù)小于的多項(xiàng)式，是常數(shù)項(xiàng)為1的次多項(xiàng)式.再利用部分分式的方法將其化為下述分式和的形式 其中是實(shí)數(shù)，是常數(shù)，是正整數(shù)利用公式將其展開，合并同類項(xiàng)，就可得到冪級(jí)數(shù)的形式.6 生成函數(shù)在整數(shù)分拆中的應(yīng)用在這一節(jié)中我們將討論生成函數(shù)在整數(shù)分拆中的應(yīng)用.個(gè)相同對(duì)象的一個(gè)分拆定義為：把這些對(duì)象分成各種組合，這些組合中對(duì)象的的數(shù)量可以相同也可不同.類似的我們可以定義整數(shù)的分拆，就是把分解成若干個(gè)整數(shù)的組合，并且與其順序無關(guān).當(dāng)然會(huì)有許多不同的分拆方案，我們稱所有這些拆分方案的數(shù)目為拆分?jǐn)?shù)(或分拆數(shù)).例如正整數(shù)4對(duì)應(yīng)的分拆可以為1+1+1+1，1+1+2，1+3，2+2，4，分拆數(shù)為5下面我們來構(gòu)造整數(shù)分拆的生成函數(shù)模型.(1)我們可以把正整數(shù)分拆看作是，由個(gè)1，個(gè)2，個(gè)3，. ，個(gè)所組成的和.則 =+由第三節(jié)的分析可得其生成函數(shù)為展開式中的系數(shù)為的所有分拆數(shù).(2)正整數(shù)的各分布量都屬于集合的生成函數(shù).在前面3.2節(jié)中所討論的例四就