生成函式

生成函式即母函式，是組合數學中尤其是計數方面的一個重要理論和工具。最早提出母函式的人是法國數學家LaplaceP.S.在其1812年出版的《機率的分析理論》中明確提出。 生成函式有普通型生成函式和指數型生成函式兩種，其中普通型用的比較多。 生成函式的套用簡單來說在於研究未知（通項）數列規律，用這種方法在給出遞推式的情況下求出數列的通項，生成函式是推導Fibonacci數列的通項公式方法之一。 另外生成函式也廣泛套用於編程與算法設計、分析上，運用這種數學方法往往對程式效率與速度有很大改進。

基本介紹

• 中文名：生成函式
• 外文名：Generating function
• 學科：組合數學
• 用途：求解計數問題
• 別稱：母函式
• 領域：數學

概念

生成函式即母函式，是組合數學中尤其是計數方面的一個重要理論和工具。

生成函式有普通型生成函式和指數型生成函式兩種，其中普通型用的比較多。形式上說，普通型生成函式用於解決多重集的組合問題，而指數型母函式用於解決多重集的排列問題。[請大牛補充解釋]

最早提出母函式的人是法國數學家LaplaceP.S.在其1812年出版的《機率的分析理論》中明確提出“生成函式的計算”，書中對生成函式思想奠基人——Euler L在18世紀對自然數的分解與合成的研究做了延伸與發展。生成函式的理論由此基本建立。

生成函式的套用簡單來說在於研究未知（通項）數列規律，用這種方法在給出遞推式的情況下求出數列的通項，生成函式是推導Fibonacci數列的通項公式方法之一，另外組合數學中的Catalan數也可以通過生成函式的方法得到。

另外生成函式也廣泛套用於編程與算法設計、分析上，運用這種數學方法往往對程式效率與速度有很大改進。

普通型母函式

定義

對於任意數列a0,a1,a2...an 即用如下方法與一個函式聯繫起來：

則稱G(x)是數列的生成函式(generating function)。

例子

比較典型的是：

指數型母函式

生成函式（也有叫做“母函式”的，但是我覺得母函式不太好聽）是說，構造這么一個多項式函式g(x)，使得x的n次方係數為f(n)。

生成函式最絕妙的是，某些生成函式可以化簡為一個很簡單的函式。也就是說，不一定每個生成函式都是用一長串多項式來表示的。比如，這個函式f(n)=1 （n當然是屬於自然數的），它的生成函式就應該是 （每一項都是一，即使n=0時也有x⁰係數為1，所以有常數項）。再仔細一看，這就是一個有無窮多項的等比數列求和嘛。如果-1<x<1，那么g(x)就等於1/(1-x)了。在研究生成函式時，我們都假設級數收斂，因為生成函式的x沒有實際意義，我們可以任意取值。於是，我們就說，f(n)=1的生成函式是g(x)=1/(1-x)。

我們舉一個例子說明，一些具有實際意義的組合問題也可以用像這樣簡單的一個函式全部表示出來。

考慮這個問題：從只有4個MM的二班選n個MM出來有多少種選法。學過簡單的排列與組合的同學都知道，答案就是C(4,n)。也就是說。從n=0開始，問題的答案分別是1,4,6,4,1,0,0,0,...（從4個MM中選出4個以上的人來方案數當然為0嘍）。那么它的生成函式g(x)就應該是g(x)=1+4x+6x²+4x³+x⁴。這不就是……二項式展開嗎？於是，g(x)=(1+x)⁴。

你或許應該知道， ；但你或許不知道，即使k為負數和小數的時候，也有類似的結論： （一直加到無窮；式子看著很彆扭，自己寫到草稿紙上吧，畢竟這裡輸入數學式子很麻煩）。其中，廣義的組合數C(k,i)就等於k(k-1)(k-2)(k-i+1)/i!，比如C(4,6)=4*3*2*1*0*(-1)/6!=0，再比如C(-1.4,2)=(-1.4)*(-2.4)/2!=1.68。後面這個就叫做牛頓二項式定理。當k為非負整數時，所有i>k時的C(k,i)中分子都要“越過”0這一項，因此後面C(k,k+1),C(k,k+2)之類的都為0了，與我們的經典二項式定理結論相同；不同的是，牛頓二項式定理中的指數k可以是任意實數。

我們再舉一個例子說明一些更複雜的生成函式。n=x1+x2+x3+...+xk有多少個非負整數解？這道題是學排列與組合的經典例題了。把每組解的每個數都加1，就變成n+k=x1+x2+x3+...+xk的正整數解的個數了。教材上或許會出現這么一個難聽的名字叫“隔板法”：把n+k個東西排成一排，在n+k-1個空格中插入k-1個“隔板”。答案我們總是知道的，就是C(n+k-1,k-1)。它就等於C(n+k-1,n)。它關於n的生成函式是g(x)=1/(1-x)^k。這個生成函式是怎么來的呢？其實，它就是(1-x)的-k次方。把(1-x)^(-k)按照剛才的牛頓二項式展開，我們就得到了x^n的係數恰好是C(n+k-1,n)，因為C(-k,n)*(-x)^n=[(-1)^n*C(n+k-1,n)]*[(-1)^n*x^n]=C(n+k-1,n)x^n。這裡看暈了不要緊，後文有另一種方法可以推導出一模一樣的公式。事實上，我們有一個純組合數學的更簡單的解釋方法。

現在我們引用《組合數學》上暴經典的一個例題。很多書上都會有這類題。

我們要從蘋果、香蕉、橘子和梨中拿一些水果出來，要求蘋果只能拿偶數個，香蕉的個數要是5的倍數，橘子最多拿4個，梨要么不拿，要么只能拿一個。問按這樣的要求拿n個水果的方案數。

引用內容

（前兩個分別是公比為2和5的幾何級數，

第三個嘛，(1+x+x^2+x^3+x^4)*(1-x)不就是1-x^5了嗎）

=1/(1-x)^2 （約分，把一大半都約掉了）

（參見剛才對1/(1-x)^k的展開）

於是，拿n個水果有n+1種方法。我們利用生成函式，完全使用代數手段得到了答案！

如果你對1/(1-x)^k的展開還不熟悉，我們這裡再介紹一個更加簡單和精妙的手段來解釋 。

是前面說過的。我們對這個式子等號兩邊同時求導數。於是， 。一步就得到了我們所需要的東西！不斷地再求導數，我們同樣可以得到剛才用複雜的牛頓二項式定理得到的那個結論（自己試試吧）。生成函式還有很多其它的處理手段，比如等式兩邊同時乘以、除以常數（相當於等式右邊每一項乘以、除以常數），等式兩邊同時乘以、除以一個x（相當於等式右邊的係數“移一位”），以及求微分積分等。神奇的生成函式啊。

我們用兩種方法得到了這樣一個公式： 。這個公式非常有用，是把一個生成函式還原為數列的武器。而且還是核武器。

接下來我們要演示如何使用生成函式求出Fibonacci數列的通項公式。

Fibonacci數列是這樣一個遞推數列： 。現在我們需要求出它的生成函式g(x)。g(x)應該是一個這樣的函式：

等式兩邊同時乘以x，我們得到：

就像我們前面說過的一樣，這相當於等式右邊的所有係數向右移動了一位。

現在我們把前面的式子和後面的式子相加，我們得到：

把這最後一個式子和第一個式子好好對比一下。如果第一個式子的係數往左邊移動一位，然後把多餘的“1”去掉，就變成了最後一個式子了。由於遞推函式的性質，我們神奇地得到了：g(x)+x*g(x)=g(x)/x-1。也就是說，g(x)*x^2+g(x)*x-g(x)=-x。把左邊的g(x)提出來，我們有：g(x)(x^2+x-1)=-x。於是，我們得到了g(x)=x/(1-x-x^2)。

我們最後看一個例子。我們介紹硬幣兌換問題：我有1分、2分和5分面值的硬幣。請問湊出n分錢有多少種方法。想一下剛才的水果，我們不難得到這個問題的生成函式：

現在，我們需要把它變成通項公式。我們的步驟同剛才的步驟完全相同。我我們像剛才一樣求出常數滿足：

這個解太複雜了，我用Mathematica解了幾分鐘，列印出了起碼幾十KB的式子。雖然複雜，但我確實是得到了通項公式。你有興趣的話可以嘗試用Mathematica解決一下1/[(1-x)(1-x^3)] （只有1分和3分的硬幣）。解c的值時可以用SolveAlways[]函式。你可以親眼見到，一個四五行的充滿虛數的式子最後總是得到正確的整數答案。