今天大半天的時(shí)間在看這個(gè)。以下主要源于百度百科，講得還是比較清楚。這里也可以看出百度百科和wiki的差別，wiki的公式都寫得很漂亮，百度百科只是摘。
生成函數(shù)是說，構(gòu)造這么一個(gè)多項(xiàng)式函數(shù)g(x)，使得x的n次方系數(shù)為f(n)。 如：序列{0,1，2，3，4，5...n}的生成函數(shù)為：$f(x)=0+x+2x^2+3x^3+4x^4+...+nx^n$
生成函數(shù)最絕妙的是，某些生成函數(shù)可以化簡(jiǎn)為一個(gè)很簡(jiǎn)單的函數(shù)。也就是說，不一定每個(gè)生成函數(shù)都是用一長(zhǎng)串多項(xiàng)式來表示的。比如，這個(gè)函數(shù)f(n)=1 （n當(dāng)然是屬于自然數(shù)的），它的生成函數(shù)就應(yīng)該是$g(x)=1+x+x^2+x^3+x^4+\ldots$（每一項(xiàng)都是一，即使n=0時(shí)也有$x^0$系數(shù)為1，所以有常數(shù)項(xiàng)）。再仔細(xì)一看，這就是一個(gè)有無窮多項(xiàng)的等比數(shù)列求和嘛。如果-1<x<1，那么g(x)就等于1/(1-x)了。在研究生成函數(shù)時(shí)，我們都假設(shè)級(jí)數(shù)收斂，
因?yàn)樯珊瘮?shù)的x沒有實(shí)際意義，我們可以任意取值。
于是，我們就說，f(n)=1的生成函數(shù)是g(x)=1/(1-x)。
?
我們舉一個(gè)例子說明，一些具有實(shí)際意義的組合問題也可以用像這樣簡(jiǎn)單的一個(gè)函數(shù)全部表示出來。
考慮這個(gè)問題：從只有4個(gè)MM的二班選n個(gè)MM出來有多少種選法。學(xué)過簡(jiǎn)單的排列與組合的同學(xué)都知道，答案就是C(4,n)。也就是說。從n=0開始，問題的答案分別是1,4,6,4,1,0,0,0,...（從4個(gè)MM中選出4個(gè)以上的人來方案數(shù)當(dāng)然為0嘍）。那么它的生成函數(shù)g(x)就應(yīng)該是$g(x)=1+4x+6x^2+4x^3+x^4$。這不就是……二項(xiàng)式展開嗎？于是，$g(x)=(1+x)^4$。
你或許應(yīng)該知道，$(1+x)^k=C(k,0)x^0+C(k,1)x^1+\ldots+C(k,k)x^k$；但你或許不知道，即使k為負(fù)數(shù)和小數(shù)的時(shí)候，也有類似的結(jié)論：$(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$（一直加到無窮）。其中，廣義的組合數(shù)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。后面這個(gè)就叫做 牛頓二項(xiàng)式定理 。當(dāng)k為整數(shù)時(shí)，所有i>k時(shí)的C(k,i)中分子都要“越過”0這一項(xiàng)，因此后面C(k,k+1),C(k,k+2)之類的都為0了，與我們的經(jīng)典二項(xiàng)式定理結(jié)論相同；不同的是，牛頓二項(xiàng)式定理中的指數(shù)k可以是任意實(shí)數(shù)。
?
我們?cè)倥e一個(gè)例子說明一些更復(fù)雜的生成函數(shù)。n=x1+x2+x3+...+xk有多少個(gè)非負(fù)整數(shù)解？這道題是學(xué)排列與組合的經(jīng)典例題了。把每組解的每個(gè)數(shù)都加1，就變成n+k=x1+x2+x3+...+xk的正整數(shù)解的個(gè)數(shù)了。
教材上或許會(huì)出現(xiàn)這么一個(gè)難聽的名字叫“隔板法”：把n+k個(gè)東西排成一排，在n+k-1個(gè)空格中插入k-1個(gè)“隔板”。答案我們總是知道的，就是C(n+k-1,k-1)。它就等于C(n+k-1,n)。它關(guān)于n的生成函數(shù)是$g(x)=1/(1-x)^k$。這個(gè)生成函數(shù)是怎么來的呢？其實(shí)，它就是(1-x)的-k次方。把$(1-x)^{-k}$按照剛才的牛頓二項(xiàng)式展開，我們就得到了$x^n$的系數(shù)恰好是C(n+k-1,n)，因?yàn)?C(-k,n)*(-x)^n=[(-1)^n*C(n+k-1,n)]*[(-1)^n*x^n]=C(n+k-1,n)x^n$。這里看暈了不要緊，后文有另一種方法可以推導(dǎo)出一模一樣的公式。事實(shí)上，我們有一個(gè)純組合數(shù)學(xué)的更簡(jiǎn)單的解釋方法。因?yàn)槲覀儎偛诺膸缀渭?jí)數(shù)$1+x+x^2+x^3+x^4+...=1/(1-x)$，那么$(1+x+x^2+x^3+x^4+...)^k$就等于$1/(1-x)^k$。仔細(xì)想想k個(gè)($1+x+x^2+x^3+x^4+\ldots$)相乘是什么意思。$(1+x+x^2+x^3+x^4+\ldots)^k$的展開式中，n次項(xiàng)的系數(shù)就是我們的答案，因?yàn)樗倪@個(gè)系數(shù)是由原式完全展開后k個(gè)指數(shù)加起來恰好等于n的項(xiàng)合并起來得到的。
?
現(xiàn)在我們引用《組合數(shù)學(xué)》上最經(jīng)典的一個(gè)例題:
我們要從蘋果、香蕉、橘子和梨中拿一些水果出來，要求蘋果只能拿偶數(shù)個(gè)，香蕉的個(gè)數(shù)要是5的倍數(shù)，橘子最多拿4個(gè)，梨要么不拿，要么只能拿一個(gè)。問按這樣的要求拿n個(gè)水果的方案數(shù)。
結(jié)合剛才的k個(gè)($1+x+x^2+x^3+x^4+\ldots$)相乘，我們也可以算出這個(gè)問題的生成函數(shù)。
$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) （前兩個(gè)分別是公比為2和5的幾何級(jí)數(shù)）\\
=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 （參見剛才對(duì)1/(1-x)^k的展開）\\
=1+2x+3x^2+4x^3+5x^4+....$
?于是，拿n個(gè)水果有n+1種方法。我們利用生成函數(shù)，完全使用代數(shù)手段得到了答案！
我們用兩種方法得到了這樣一個(gè)公式：$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$。這個(gè)公式非常有用，是把一個(gè)生成函數(shù)還原為數(shù)列的武器。而且還是核武器。
接下來我們要演示如何使用生成函數(shù)求出Fibonacci數(shù)列的通項(xiàng)公式。
Fibonacci數(shù)列是這樣一個(gè)遞推數(shù)列：f(n)=f(n-1)+f(n-2)。現(xiàn)在我們需要求出它的生成函數(shù)g(x)。
$g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7\ldots$
等式兩邊同時(shí)乘以x，我們得到：
$x*g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+\ldots$
就像我們前面說過的一樣，這相當(dāng)于等式右邊的所有系數(shù)向右移動(dòng)了一位。
現(xiàn)在我們兩式相加，我們得到：
$g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+\ldots$
把這最后一個(gè)式子和第一個(gè)式子好好對(duì)比一下。如果第一個(gè)式子的系數(shù)往左邊移動(dòng)一位，然后把多余的“1”去掉，就變成了最后一個(gè)式子了。由于遞推函數(shù)的性質(zhì)，我們神奇地得到了：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)$。
現(xiàn)在把$x/(1-x-x^2)$還原成通項(xiàng)公式。這不是我們剛才的$1/(1-x)^n$的形式，我們要把它變成這種形式。
我們發(fā)現(xià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$的兩個(gè)根。
那么令$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}$
因?yàn)?\frac{1}{1-(1-\sqrt{5})x/2}$背后是一個(gè)$a_1=1, q=(1-\sqrt{5})x/2$的等比序列；
$\frac{1}{1-(1+\sqrt{5})x/2}$背后是一個(gè)$a_1=1, q=(1+\sqrt{5})x/2$的等比序列；
到這里我們就知道$x^n$的系數(shù)應(yīng)該是$f(n)=-(1/\sqrt{5})*[(1-\sqrt{5})/2]^n + (1/\sqrt{5})*[(1+\sqrt{5})/2]^n$。（這就是我們想要的通項(xiàng)公式）
事實(shí)上，用上面所說的方法，我們可以求出任何一個(gè)線性齊次遞推方程的通項(xiàng)公式。什么叫做線性齊次遞推呢？就是這樣的遞推方程：f(n)等于多少個(gè)f(n-1)加上多少個(gè)f(n-2)加上多少個(gè)f(n-3)等等。Fibonacci數(shù)列的遞推關(guān)系就是線性齊次遞推關(guān)系。
我們最后看一個(gè)例子。我們介紹硬幣兌換問題：我有1分、2分和5分面值的硬幣。請(qǐng)問湊出n分錢有多少種方法。
想一下剛才的水果，我們不難得到這個(gè)問題的生成函數(shù)：$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)]$。
現(xiàn)在，把它變成通項(xiàng)公式。我們的步驟同剛才的步驟完全相同。我們把$(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個(gè)解：$-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)()()()$ （省略不寫了）。注意那個(gè)(1-x)^3。由于等根的出現(xiàn)，我們不得不把(1-x)^3所包含的(1-x)和(1-x)^2因子寫進(jìn)一會(huì)兒的分母里，不然會(huì)導(dǎo)致解不出合適的c來。你可以看到很多虛數(shù)。不過沒關(guān)系，這些虛數(shù)同樣參與運(yùn)算，就像剛才的根式一樣不會(huì)影響到最后結(jié)果的有理性。然后，我們像剛才一樣求出常數(shù)滿足$1/(1-x)(1-x^2)(1-x^5)=c1/()+c2/(1-x)+c3/(1-x)^2+c4/(1-x)^3...+c8/()$。
下列代碼給出的是給定arr[] = {硬幣面值}，湊出target分錢的方法數(shù)：
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分別對(duì)應(yīng)于面值為1，2，5的生成函數(shù)。我們?cè)诨?jiǎn)的時(shí)候，首先化簡(jiǎn)的f1*f2，然后再用(f1*f2)的結(jié)果與f3進(jìn)行化簡(jiǎn)。Line11-18就是每次化簡(jiǎn)得到的等式。params[next][i] 表示的是化簡(jiǎn)得到的式子$x^i$的系數(shù)。
我們本來一開始是需要初始化f1對(duì)應(yīng)的系數(shù)的。但是注意到一點(diǎn)，如果target=0，且面值為0的情況，f0(x)=1.所以這里我們初始化params[0][0] = 1，其他仍為0.然后通過Line15-17，同樣可以初始化f1。
經(jīng)過n輪之后，整個(gè)g(x)就化簡(jiǎn)出來了。
這里雖然f1、f2、f3都是無限個(gè)項(xiàng)，但是為什么Line 13和Line 15只需要循環(huán)到target呢？因?yàn)閷?duì)于大于target的項(xiàng)，他們的和也一定會(huì)大于target，我們最終只需要$x^{target}$，所以到target為止就行了。
另外，注意Line 15，步進(jìn)是arr[i]，因?yàn)橹挥衚+arr[i]的系數(shù)為1.
有1克、2克、3克、4克的砝碼各一枚，能稱出哪幾種重量？每種重量各有幾種可能方案？
因?yàn)橹荒苋∫幻叮鶕?jù)前面，我們可以知道生成函數(shù)就是$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的重量，系數(shù)就是可能的方案。比如重量為4的可能方案就有2種。
網(wǎng)易游戲2011年筆試 考了這么一道題。尼瑪，沒搞過ACM的哪懂這個(gè)啊。。
?
普通的生成函數(shù)對(duì)于組合類型數(shù)列的研究很有幫助，而指數(shù)型母函數(shù)可以很方便的拿來研究排列類型的數(shù)列。
指數(shù)型母函數(shù)形式為$g(x) = 1 + f(1)x^1/1!+f(2)x^2/2!+\ldots$
有時(shí)可以利用一些級(jí)數(shù)公式來進(jìn)行化簡(jiǎn)推導(dǎo)，
$e^x = 1 + x + x^2 / 2! + x^3 / 3! + … + x^n / n! +\ldots$
這里 google的一道在線筆試題 就是用指數(shù)型生成函數(shù)的。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
