母函數

在數學中，某個無窮序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ 的母函數（又稱生成函數，英語：Generating function）是一種形式冪級數，其每一項的係數可以提供關於這個序列的信息。母函數一般用有關原始序列進行操作後得到的封閉形式表示，而非一個序列。

母函數可分為很多種，包括普通母函數、指數母函數、朗伯級數、貝爾級數和狄利克雷級數。對任何序列理論上都可以寫出以上每個類型的一個母函數（除了朗伯級數和狄利克雷級數需要序列從${\displaystyle a_{1}}$而非${\displaystyle a_{0}}$開始），但是選用不同形式來解決問題的難度有顯著區別。最有用的母函數類型取決於具體問題和序列本身的性質。

母函數的表示一般使用解析形式，即寫成關於某個形式變量x的形式冪級數。對冪級數的收斂半徑中的某一點，可以求母函數在這一點的級數和。但無論如何，由於母函數是形式冪級數的一種，其級數和不一定對每個x的值都存在。

母函數方法不僅在概率論的計算中有重要地位，而且已成為組合數學中一種重要方法。此外，母函數在有限差分計算、特殊函數論等數學領域中都有着廣泛的應用。

歷史

母函數於1730年由法國數學家亞伯拉罕·棣莫弗 (Abraham de Moivre) 首次提出，以解決一般線性重複問題。^[1]

數學家喬治·波利亞 (George Pólya) 在《數學與猜想》（Mathematics and plausible reasoning）中寫道：

「母函數」這個名稱是由拉普拉斯命名的。然而，歐拉卻早在拉普拉斯[...]之前就使用了母函數這個工具，卻沒有為它命名。他將這個數學工具應用在《組合分析》和《數論》中的幾個問題上。

瑞士數學家雅各布·伯努利在考慮「當投擲n粒骰子時，加起來點數總和等於m的可能方式的數目」這個問題時首先使用了母函數方法，並得出可能的數目是${\displaystyle (x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{n}}$的展開式中${\displaystyle x^{m}}$項的係數。之後歐拉在研究自然數的分解時也使用了母函數方法並奠定了母函數方法的基礎。1812年，法國數學家拉普拉斯在著作《概率的分析理論》的第一卷中系統地研究了母函數方法及與之有關的理論。

定義

母函數具有類似於袋子的功能。我們不必把一些小物件分開攜帶（這樣會很尷尬不便），而是把他們全部放在一個袋子裡，這樣我們只需要攜帶一件物品——這個袋子。

——喬治·波利亞，數學與猜想 (1954)

母函數就是一列用來展示一系列數字的掛衣架。

——赫伯特·維爾夫，Generatingfunctionology (1994)

^[2]

斂散性

不像一個普通序列，形式冪級數不需要收斂：實際上，母函數並不真的是一個「函數」，而且「變量」始終是一個不定元（indeterminate形式變量）。無窮多維數列可以用含有多個不定元的形式冪級數表示，因此母函數不是一般意義下從某個定義域射到某個上域的函數。

這些關於不定元${\displaystyle x}$的表達式可包括算數運算、微分運算、與其他母函數的複合運算（比如代入）。這些運算也對函數有定義，因此結果看起來像關於${\displaystyle x}$的函數。封閉形式的表達式確實可以理解為對某些（足夠小的）具體數值${\displaystyle x}$可求值的函數，也有形式級數作為它的級數展開。這解釋了「母函數」這一名稱。但是不一定需要滿足這種解釋成立，因為當${\displaystyle x}$取非零數時，形式級數並不需要成為收斂數列。

局限性

不是所有作為關於${\displaystyle x}$的函數有意義的表達式都作為形式級數有意義。例如，${\displaystyle x}$的負數和分數指數冪就是沒有對應形式冪級數的函數的例子。

分類

普通母函數（OGF）

沒有特別說明時，母函數通常指普通母函數。序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的普通母函數是：

$${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}}$$如果${\displaystyle a_{n}}$ 是某個離散隨機變量的概率質量函數，那麼它的普通母函數稱為一個概率母函數。

多重下標的序列也可以有母函數，例如序列${\displaystyle (a_{m,n})_{m\in \mathbb {N} ,n\in \mathbb {N} }}$ 的母函數是

$${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}}$$

指數母函數（EGF）

序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的指數母函數是：

$${\displaystyle \operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}}$$對於含有有標號對象的組合計數問題，指數母函數通常來說比普通母函數更方便。 指數母函數的另一個優勢是易於把線性遞推公式轉化為微分方程領域。以斐波那契數列${\displaystyle \{f_{n}\}}$為例，它滿足線性遞推公式${\displaystyle f_{n+2}=f_{n+1}+f_{n}}$，它對應的指數母函數有如下形式：${\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}}$，且易證它的導數滿足微分方程${\displaystyle \operatorname {EF''} (x)+=\operatorname {EF'} (x)+\operatorname {EF} (x)}$，直接對應了前面的遞推公式。這樣看來，階乘項${\displaystyle n!}$只是為了在對${\displaystyle x^{n}}$進行微分時歸一化。

泊松母函數

序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的泊松母函數是：

$${\displaystyle \operatorname {PG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}e^{-x}{\frac {x^{n}}{n!}}=e^{-x}\,\operatorname {EG} (a_{n};x)}$$

朗伯級數

序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的朗伯級數是：

$${\displaystyle \operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}}$$注意在朗伯級數中，下標${\displaystyle n}$從1 而不是0 開始，否則第一項會未定義。

冪級數展開${\displaystyle b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x)}$中的朗伯級數係數（整數${\displaystyle n\geq 1}$）與因數之和${\displaystyle b_{n}=\sum _{d|n}a_{d}}$有關。

貝爾級數

序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的貝爾級數是一個同時關於不定數${\displaystyle x}$和質數${\displaystyle p}$的表達式：

$${\displaystyle \operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.}$$

狄利克雷級數母函數（DGF）

形式狄利克雷級數經常被歸為母函數，儘管它並不是嚴格意義上的形式冪級數。序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$的狄利克雷級數母函數是：

$${\displaystyle DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}}$$當 ${\displaystyle a_{n}}$ 是積性函數時狄利克雷級數非常有用，因為這時的母函數可以寫成一系列貝爾級數的歐拉積：

$${\displaystyle \operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,}$$如果 ${\displaystyle a_{n}}$是狄利克雷特徵，那麼它對應的狄利克雷級數母函數被稱為狄利克雷L函數。我們還可證明如上所寫朗伯級數展開的一對係數和它們的狄利克雷級數母函數的關係，即$${\displaystyle [x^{n}]\operatorname {LG} (a_{n};x)=b_{n}}$$

當且僅當

$${\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s)}$$，其中${\displaystyle \zeta (s)}$是黎曼ζ函數。

狄利克雷級數母函數${\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m}}$生成的數列對應的普通母函數為：

$${\displaystyle \sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots }$$

多項式序列母函數

母函數的思想可以延伸到其他方面里。例如，二項式型的多項式序列由如下母函數生成：$${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}}$$其中${\displaystyle p_{n}(x)}$是一序列多項式，${\displaystyle f(t)}$是特定形式的函數。Sheffer序列就是由類似方法生成的。

更複雜的母函數生成的多項式序列如：

• 阿佩爾多項式
• 切比雪夫多項式
• 差分多項式
• 廣義阿佩爾多項式
• q-查分多項式

其他母函數

其他通過更複雜母函數生成的序列包括：

• 雙重指數母函數，如貝爾數
• 母函數和對角母函數的阿達瑪乘積，及他們對應的積分變換

一般母函數

求和

${\displaystyle \displaystyle \sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}}$用於等比數列求和或推導級數${\displaystyle \displaystyle \sum _{n=0}^{\infty }n^{m}x^{n}}$。

不定方程的解數

${\displaystyle \displaystyle \sum _{n=0}^{\infty }{\binom {n+k}{k}}x^{n}={\frac {1}{(1-x)^{k+1}}}}$用於求解一次不定方程的解數，類似隔板法。

對於非負整數${\displaystyle x_{1},x_{2},...,x_{k}}$，${\displaystyle x_{1}+x_{2}+...+x_{k}=n}$有${\displaystyle {\binom {n+k-1}{k-1}}}$個解：

${\displaystyle \displaystyle {\frac {1}{(1-x)^{k}}}=\sum _{n=0}^{\infty }{\binom {n+k-1}{k-1}}x^{n}}$

對於非負整數${\displaystyle x_{1},x_{2},...,x_{k}}$，${\displaystyle x_{1}+2x_{2}+2x_{3}=m}$有${\displaystyle {\binom {[{\frac {m}{2}}]+2}{2}}}$個解：

${\displaystyle \displaystyle {\frac {1}{(1-x)(1-x^{2})^{2}}}={\frac {1+x}{(1-x^{2})^{3}}}=(1+x)\sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{2n}=\sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{2n}+{\binom {n+2}{2}}x^{2n+1}}$^[3]

參見

• 矩生成函數
• 概率母函數
• 動差母函數
• 其他處理數列的組合技巧，如：
  • 遞歸關係
• Z轉換
• 整數分拆