[科普中國]-母函數(shù)

歷史

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

普通型母函數(shù)母函數(shù)就是一列用來展示一串?dāng)?shù)字的掛衣架。

——赫伯特·唯爾夫1。

定義：

對于任意數(shù)列 即用如下方法與一個函數(shù)聯(lián)系起來：

則稱G(x)是數(shù)列的生成函數(shù)(generating function)

其一般形式為：

指數(shù)型母函數(shù)序列 的指數(shù)型母函數(shù)為：

母函數(shù)的應(yīng)用生成函數(shù)的應(yīng)用簡單來說在于研究未知（通項）數(shù)列規(guī)律，用這種方法在給出遞推式的情況下求出數(shù)列的通項，生成函數(shù)是推導(dǎo)Fibonacci數(shù)列的通項公式方法之一，另外組合數(shù)學(xué)中的Catalan數(shù)也可以通過生成函數(shù)的方法得到2。

生成函數(shù)是說，構(gòu)造這么一個多項式函數(shù)g(x)，使得x的n次方系數(shù)為f(n)。 如：序列{0,1，2，3，4，5...n}的生成函數(shù)為：g(x)=0+x+2x^2+3x^3+4x^4+...+nx^n

生成函數(shù)最絕妙的是，某些生成函數(shù)可以化簡為一個很簡單的函數(shù)。也就是說，不一定每個生成函數(shù)都是用一長串多項式來表示的。比如，這個函數(shù)f(n)=1 （n當(dāng)然是屬于自然數(shù)的），它的生成函數(shù)就應(yīng)該是g(x)=1+x+x^2+x^3+x^4+...（每一項都是一，即使n=0時也有x^0系數(shù)為1，所以有常數(shù)項）。再仔細(xì)一看，這就是一個有無窮多項的等比數(shù)列求和嘛。如果-1> nNum)

{

for(i=0; i