母函數

在數學中，某個序列${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ 的母函數（又稱生成函數，英語：Generating function）是一種形式冪級數，其每一項的系數可以提供關於這個序列的資訊。使用母函數解決問題的方法稱為母函數方法。

母函數可分為很多種，包括普通母函數、指數母函數、L級數、貝爾級數和狄利克雷級數。對每個序列都可以寫出以上每個類型的一個母函數。構造母函數的目的一般是為了解決某個特定的問題，因此選用何種母函數視乎序列本身的特性和問題的類型。

母函數的表示一般使用解析形式，即寫成關於某個形式變量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年，法國數學家拉普拉斯在著作《概率的分析理論》的第一卷中系統地研究了母函數方法及與之有關的理論。

1 sources

定義

“	母函數就是一列用來展示一串數字的掛衣架。	”
——赫伯特·維爾夫[2]

1 sources

普通母函數

普通母函數就是最常見的母函數。一般來說，序列${\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}}$。

指數母函數

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

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

泊松母函數

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

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

L級數

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

${\displaystyle LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}}$

注意這裏的下標 n 從1 而不是0 開始。

貝爾級數

關於算術函數 :${\displaystyle f(n)}$ 和 ${\displaystyle p}$ 的貝爾級數是：

${\displaystyle f_{p}(x)=\sum _{n=0}^{\infty }f(p^{n})x^{n}}$

狄利克雷級數母函數

狄利克雷級數經常被用作母函數，儘管實際上狄利克雷級數並不是嚴格意義上的形式冪級數。序列${\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 DG(a_{n};s)=\prod _{p}f_{p}(p^{-s})\,}$

如果 ${\displaystyle a_{n}}$是狄利克雷特徵，那麼它對應的狄利克雷級數母函數被稱為狄利克雷L函數。

一般母函數

1 sources

求和

${\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]

1 sources

參見

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

參考來源

1. Knuth, Donald E. §1.2.9 Generating Functions. Fundamental Algorithms. The Art of Computer Programming 1 3rd. Addison-Wesley. 1997. ISBN 0-201-89683-4.
2. 赫伯特·維爾夫（Herbert S. Wilf）. 母函数理论. Academic Press. 1994 [2009-11-26]. （原始內容存檔於2013-02-11）.
3. 王迪吉 高福康 段芳. 关于不定方程的整数解及其解数的讨论. 新疆師範大學學報(自然科學版). 2008, (3) [2015-09-20]. （原始內容存檔於2019-06-03）.