资源描述：
《数学传播32卷3期》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、數學傳播32卷3期,pp.12-35一般生成函數之應用張福春·曾介玫摘要:生成函數是利用冪級數中變數的係數來表達數列,在組合數學上有廣泛的應用。本文中將介紹一般生成函數重要的性質並透過大量的例子說明他們在組合數學上的應用。關鍵詞:一般生成函數、二項式定理、二項係數、遞迴、遞迴關係、冪級數、恆等式、等比級數、數學歸納法、計數問題、整數分割、費伯那西、分項分式、摺積。一.前言在數學的領域中常常遇到艱難的數列問題,若能利用生成函數則會使得問題變為輕而易舉。生成函數是一種常被運用在離散數學上的進階計算技巧。在數學中有很廣泛的應用,常見的有計數問題、整數的分割、解遞迴關係、求數列和與恆等式的證明。西元十
2、三世紀初,義大利數學家費伯那西(Fibonacci,1175∼1250)研究費伯那西(Fi-bonacci)數列0,1,1,2,3,5,8,13,21,...,得到遞迴關係為Fn+2=Fn+1+Fn,n≥0F0=0,F1=1直到西元1843年,法國數學家棣美弗(Jacques-Philippe-MarieBinet,1786∼1856)利用一般生成函數才得到Fn一般解的式子,"√!n√!n#11+51−5Fn=√−,n≥0522在西元1748時,尤拉(Euler,1707∼1783)利用一般生成函數的技巧,深入研究整數的分割。利用111Y∞1P(x)=···=,1−x1−x21−x31−xii
3、=112一般生成函數之應用13我們得到p(0),p(1),p(2),...的生成函數,其中p(n)代表正整數n的不同分割數,p(0)定義為1。Wilf(1994)介紹了生成函數的基本定義、應用和離散數學上相關的例子。Stanley(1999)兩冊的書總共用了八百多頁詳細的介紹生成函數的性質及在計數組合學上各方面的應用。Grimaldi(2004)討論到生成函數的運算技巧和提到生成函數的相關歷史。黃子嘉(2001)收錄許多台灣地區關於生成函數的研究所入學考題。讀者若對生成函數有深入瞭解,可參考上述書目。本文取材參考了上述文獻。關於著名整數數列的生成函數及其相關性質,請參閱網路整數數列百科全書“T
4、heOn-LineEncyclopediaofIntegerSequences”(Sloane,2007)。在2007年5月27號共蒐集了130017個數列,每個數列包含:1.數列的名稱;2.數列前幾十項;3.數列的別名;4.參考文獻;5.相關連結;6.生成函數;7.Mathematica,Maple及一般程式的程式碼;8.相關數列;9.關鍵字;10.作者。生成函數可分為一般生成函數與指數生成函數,指數生成函數主要是用於計算與排列有關的計數問題,限於篇幅大小,這裡只討論一般生成函數。本文的主要目的是要介紹單變數的一般生成函數的基本性質,並透過大量的例子說明他們在計數、整數分割、遞迴關係式、數列
5、和與恆等式上廣泛的應用。一般生成函數更深入的應用,如解數列的漸近公式與證明數列的單一性、凸性和同餘性等,有興趣的讀者若想更進一步了解可參閱Wilf(1994)。二.基本性質生成函數(generatingfunction)是藉由冪級數中的係數來呈現數列,是研究數列性質非常有用的工具。他能用於解很多不同類型的計數(組合)問題,像是選擇或分配不同種類物件的方法數,這些計數問題受制於各種限制。應用於解遞迴關係中,藉由轉換遞迴關係項成數列的項到生成函數的方程式中。這方程式能由找到生成函數的解得到答案,從這個解,能找到生成函數的冪級數係數,解出原來的遞迴關係式。他也能應用於計算數列和與證明恆等式,藉由相關
6、地簡單關係函數的優點,此函數能轉換到包含數列的等式。在生成函數的冪次的運算中使用到下面兩個重要的觀念:(a)藉由xn乘以xm後能得到xm+n,這呈現了個數相加與多項式相乘之間的關係。(b)多項式或冪級數中的係數提供了生成函數中所要包含的資訊。這說明利用生程函數來解問題的動機。可由下面幾節的例子看見上述兩個理由是生成函數可以解多種應用問題的主要原因。14數學傳播32卷3期民97年9月首先介紹一般生成函數的定義如下:定義2.1:設{a}∞={a,a,a,...}是一數列,則函數k0012X∞2kf(x)=a0+a1x+a2x+···=akx(2.1)k=0稱為{a}∞的一般生成函數(ordinar
7、ygeneratingfunction)。k0換言之,一般生成函數是以{a}∞為係數之x的冪級數。k0如果只有有限個a6=0,則{a}∞的生成函數是一個多項式。我們能定義有限項實數數kk0列的生成函數藉由令an+1=0,an+2=0,...來擴充有限的數列a0,a1,...,an成為無窮的數列。下面計算幾個常見數列的生成函數。例2.1:(常數數列的生成函數)常數數列{1}∞的生成函數是0X∞23k
