今天大半天的時間在看這個。以下主要源于百度百科，講得還是比較清楚。這里也可以看出百度百科和wiki的差別，wiki的公式都寫得很漂亮，百度百科只是摘。
生成函數是說，構造這么一個多項式函數g(x)，使得x的n次方系數為f(n)。 如：序列{0,1，2，3，4，5...n}的生成函數為：$f(x)=0+x+2x^2+3x^3+4x^4+...+nx^n$
生成函數最絕妙的是，某些生成函數可以化簡為一個很簡單的函數。也就是說，不一定每個生成函數都是用一長串多項式來表示的。比如，這個函數f(n)=1 （n當然是屬于自然數的），它的生成函數就應該是$g(x)=1+x+x^2+x^3+x^4+\ldots$（每一項都是一，即使n=0時也有$x^0$系數為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^2+4x^3+x^4$。這不就是……二項式展開嗎？于是，$g(x)=(1+x)^4$。
你或許應該知道，$(1+x)^k=C(k,0)x^0+C(k,1)x^1+\ldots+C(k,k)x^k$；但你或許不知道，即使k為負數和小數的時候，也有類似的結論：$(1+x)^k=C(k,0)x^0+C(k,1)x^1+...+C(k,k)x^k+C(k,k+1)x^{k+1}+C(k,k+2)x^{k+2}+\ldots$（一直加到無窮）。其中，廣義的組合數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$。這里看暈了不要緊，后文有另一種方法可以推導出一模一樣的公式。事實上，我們有一個純組合數學的更簡單的解釋方法。因為我們剛才的幾何級數$1+x+x^2+x^3+x^4+...=1/(1-x)$，那么$(1+x+x^2+x^3+x^4+...)^k$就等于$1/(1-x)^k$。仔細想想k個($1+x+x^2+x^3+x^4+\ldots$)相乘是什么意思。$(1+x+x^2+x^3+x^4+\ldots)^k$的展開式中，n次項的系數就是我們的答案，因為它的這個系數是由原式完全展開后k個指數加起來恰好等于n的項合并起來得到的。
?
現在我們引用《組合數學》上最經典的一個例題:
我們要從蘋果、香蕉、橘子和梨中拿一些水果出來，要求蘋果只能拿偶數個，香蕉的個數要是5的倍數，橘子最多拿4個，梨要么不拿，要么只能拿一個。問按這樣的要求拿n個水果的方案數。
結合剛才的k個($1+x+x^2+x^3+x^4+\ldots$)相乘，我們也可以算出這個問題的生成函數。
$g(x)=(1+x^2+x^4+...)(1+x^5+x^10+..)(1+x+x^2+x^3+x^4)(1+x) \\
=[1/(1-x^2)]*[1/(1-x^5)]*[(1-x^5)/(1-x)]*(1+x) （前兩個分別是公比為2和5的幾何級數）\\
=1/(1-x)^2 \\
=(1-x)^{-2}=C(1,0)+C(2,1)x+C(3,2)x^2+C(4,3)x^3+\ldots （參見剛才對1/(1-x)^k的展開）\\
=1+2x+3x^2+4x^3+5x^4+....$
?于是，拿n個水果有n+1種方法。我們利用生成函數，完全使用代數手段得到了答案！
我們用兩種方法得到了這樣一個公式：$1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+\ldots$。這個公式非常有用，是把一個生成函數還原為數列的武器。而且還是核武器。
接下來我們要演示如何使用生成函數求出Fibonacci數列的通項公式。
Fibonacci數列是這樣一個遞推數列：f(n)=f(n-1)+f(n-2)。現在我們需要求出它的生成函數g(x)。
$g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7\ldots$
等式兩邊同時乘以x，我們得到：
$x*g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+\ldots$
就像我們前面說過的一樣，這相當于等式右邊的所有系數向右移動了一位。
現在我們兩式相加，我們得到：
$g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+\ldots$
把這最后一個式子和第一個式子好好對比一下。如果第一個式子的系數往左邊移動一位，然后把多余的“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)$。
現在把$x/(1-x-x^2)$還原成通項公式。這不是我們剛才的$1/(1-x)^n$的形式，我們要把它變成這種形式。
我們發現，$1-x-x^2=[1-(1-\sqrt{5})x/2]*[1-(1+\sqrt{5})x/2]$，$(1-\sqrt{5})/2$和$(1+\sqrt{5})/2$是$x^2-x-1=0$的兩個根。
那么令$x/(1-x-x^2) = \frac{c_1}{1-(1-\sqrt{5})x/2}+\frac{c_2}{1-(1+\sqrt{5})x/2}$
$=\frac{c_1*[1-(1+√5)x/2]+c_2*[1-(1-√5)x/2]}{[1-(1-\sqrt{5})x/2] * [1-(1+\sqrt{5})x/2]}$
$=\frac{c_1*[1-(1+√5)x/2]+c_2*[1-(1-√5)x/2]}{1-x-x^2}$
也就是說，$c_1*[1-(1+√5)x/2]+c_2*[1-(1-√5)x/2]=x$。
代入x=0,得$c_1+c_2=0$；代入x=1，得$\frac{1-\sqrt{5}}{2}c_1+\frac{1+\sqrt{5}}{2}c_2=1$。可以求得$c_1=-1/\sqrt{5}，c_2=1/\sqrt{5}$。
所以$x/(1-x-x^2) = \frac{-1/\sqrt{5}}{1-(1-\sqrt{5})x/2}+\frac{1/\sqrt{5}}{1-(1+\sqrt{5})x/2}$
因為$\frac{1}{1-(1-\sqrt{5})x/2}$背后是一個$a_1=1, q=(1-\sqrt{5})x/2$的等比序列；
$\frac{1}{1-(1+\sqrt{5})x/2}$背后是一個$a_1=1, q=(1+\sqrt{5})x/2$的等比序列；
到這里我們就知道$x^n$的系數應該是$f(n)=-(1/\sqrt{5})*[(1-\sqrt{5})/2]^n + (1/\sqrt{5})*[(1+\sqrt{5})/2]^n$。（這就是我們想要的通項公式）
事實上，用上面所說的方法，我們可以求出任何一個線性齊次遞推方程的通項公式。什么叫做線性齊次遞推呢？就是這樣的遞推方程：f(n)等于多少個f(n-1)加上多少個f(n-2)加上多少個f(n-3)等等。Fibonacci數列的遞推關系就是線性齊次遞推關系。
我們最后看一個例子。我們介紹硬幣兌換問題：我有1分、2分和5分面值的硬幣。請問湊出n分錢有多少種方法。
想一下剛才的水果，我們不難得到這個問題的生成函數：$g(x)=(1+x+x^2+x^3+\ldots)(1+x^2+x^4+\ldots)(1+x^5+x^10+\ldots)=1/[(1-x)(1-x^2)(1-x^5)]$。
現在，把它變成通項公式。我們的步驟同剛才的步驟完全相同。我們把$(1-x)(1-x^2)(1-x^5)$展開，得到$1-x-x^2+x^3-x^5+x^6+x^7-x^8$。
我們求出$-1+x+x^2-x^3+x^5-x^6-x^7+x^8=0$的解，得到了以下8個解：$-1,1,1,1,-(-1)^{1/5},(-1)^{2/5},-(-1)^{3/5},(-1)^{4/5}$。解得$(1-x)(1-x^2)(1-x^5)=(1+x)(1-x)^3(1+(-1)^(1/5) x)()()()$ （省略不寫了）。注意那個(1-x)^3。由于等根的出現，我們不得不把(1-x)^3所包含的(1-x)和(1-x)^2因子寫進一會兒的分母里，不然會導致解不出合適的c來。你可以看到很多虛數。不過沒關系，這些虛數同樣參與運算，就像剛才的根式一樣不會影響到最后結果的有理性。然后，我們像剛才一樣求出常數滿足$1/(1-x)(1-x^2)(1-x^5)=c1/()+c2/(1-x)+c3/(1-x)^2+c4/(1-x)^3...+c8/()$。
下列代碼給出的是給定arr[] = {硬幣面值}，湊出target分錢的方法數：
1
#include <iostream>
2
#include <vector>
3
using
namespace
std;
4
5
int
generateFunction(
int
arr[],
int
n,
int
target) {
6
if
(n <=
0
)
return
target ==
0
?
1
:
0
;
7
vector<vector<
int
> >
params
(
2
, vector<
int
>(target +
1
,
0
));
8
params
[
0
][
0
] =
1
;
9
int
cur =
0
, next =
1
;
10
11
for
(
int
i =
0
; i < n; ++
i) {
12
params
[next].assign(target +
1
,
0
);
13
for
(
int
j =
0
; j <= target; ++
j) {
14
if
(
params
[cur][j] ==
0
)
continue
;
15
for
(
int
k =
0
; k + j <= target; k +=
arr[i]) {
16
params
[next][j + k] +=
params
[cur][j];
//
* 1
17
}
18
}
19
cur = !
cur;
20
next = !
next;
21
}
22
return
params
[cur][target];
23
}
24
25
int
main() {
26
int
n =
3
;
27
int
arr[] = {
1
,
2
,
5
};
28
29
for
(
int
i =
1
; i <=
100
; ++
i) {
30
cout << i <<
"
:
"
<< generateFunction(arr, n, i) <<
endl;
31
}
32
return
0
;
33
}
g(x)=f1(x)*f2(x)*f3(x); f1、f2和f3分別對應于面值為1，2，5的生成函數。我們在化簡的時候，首先化簡的f1*f2，然后再用(f1*f2)的結果與f3進行化簡。Line11-18就是每次化簡得到的等式。params[next][i] 表示的是化簡得到的式子$x^i$的系數。
我們本來一開始是需要初始化f1對應的系數的。但是注意到一點，如果target=0，且面值為0的情況，f0(x)=1.所以這里我們初始化params[0][0] = 1，其他仍為0.然后通過Line15-17，同樣可以初始化f1。
經過n輪之后，整個g(x)就化簡出來了。
這里雖然f1、f2、f3都是無限個項，但是為什么Line 13和Line 15只需要循環到target呢？因為對于大于target的項，他們的和也一定會大于target，我們最終只需要$x^{target}$，所以到target為止就行了。
另外，注意Line 15，步進是arr[i]，因為只有k+arr[i]的系數為1.
有1克、2克、3克、4克的砝碼各一枚，能稱出哪幾種重量？每種重量各有幾種可能方案？
因為只能取一枚，根據前面，我們可以知道生成函數就是$g(x) = (1+x)(1+x^2)(1+x^3)(1+x^4)=1 + x + x^2 + 2x^3 + 2x^4 + 2x^5 + 2x^6 + 2x^7 + x^8 + x^9 + x^{10}$.
所以可以稱出0-10的重量，系數就是可能的方案。比如重量為4的可能方案就有2種。
網易游戲2011年筆試 考了這么一道題。尼瑪，沒搞過ACM的哪懂這個啊。。
?
普通的生成函數對于組合類型數列的研究很有幫助，而指數型母函數可以很方便的拿來研究排列類型的數列。
指數型母函數形式為$g(x) = 1 + f(1)x^1/1!+f(2)x^2/2!+\ldots$
有時可以利用一些級數公式來進行化簡推導，
$e^x = 1 + x + x^2 / 2! + x^3 / 3! + … + x^n / n! +\ldots$
這里 google的一道在線筆試題 就是用指數型生成函數的。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
