普通生成函數

序列 \(a\) 的普通生成函數（ordinary generating function，OGF）定義為形式冪級數：

\[ F(x)=\sum_{n}a_n x^n \]

\(a\) 既可以是有窮序列，也可以是無窮序列。常見的例子（假設 \(a\) 以 \(0\) 為起點）：

序列 \(a=\langle 1,2,3\rangle\) 的普通生成函數是 \(1+2x+3x^2\)。
序列 \(a=\langle 1,1,1,\cdots\rangle\) 的普通生成函數是 \(\sum_{n\ge 0}x^n\)。
序列 \(a=\langle 1,2,4,8,16,\cdots\rangle\) 的生成函數是 \(\sum_{n\ge 0}2^nx^n\)。
序列 \(a=\langle 1,3,5,7,9,\cdots\rangle\) 的生成函數是 \(\sum_{n\ge 0}(2n+1)x^n\)。

換句話説，如果序列 \(a\) 有通項公式，那麼它的普通生成函數的係數就是通項公式。

基本運算

考慮兩個序列 \(a,b\) 的普通生成函數，分別為 \(F(x),G(x)\)。那麼有

\[ F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n \]

因此 \(F(x)\pm G(x)\) 是序列 \(\langle a_n\pm b_n\rangle\) 的普通生成函數。

考慮乘法運算，也就是卷積：

\[ F(x)G(x)=\sum_n x^n \sum_{i=0}^na_ib_{n-i} \]

因此 \(F(x)G(x)\) 是序列 \(\langle \sum_{i=0}^n a_ib_{n-i} \rangle\) 的普通生成函數。

封閉形式

在運用生成函數的過程中，我們不會一直使用形式冪級數的形式，而會適時地轉化為封閉形式以更好地化簡。

例如 \(\langle 1,1,1,\cdots\rangle\) 的普通生成函數 \(F(x)=\sum_{n\ge 0}x^n\)，我們可以發現

\[ F(x)x+1=F(x) \]

那麼解這個方程得到

\[ F(x)=\frac{1}{1-x} \]

這就是 \(\sum_{n\ge 0}x^n\) 的封閉形式。

考慮等比數列 \(\langle 1,p,p^2,p^3,p^4,\cdots\rangle\) 的生成函數 \(F(x)=\sum_{n\ge 0}p^nx^n\)，有

\[ \begin{aligned}F(x)px+1 &=F(x)\\F(x) &=\frac{1}{1-px}\end{aligned} \]

等比數列的封閉形式與展開形式是常用的變換手段。

小練習

請求出下列數列的普通生成函數（形式冪級數形式和封閉形式）。難度是循序漸進的。

\(a=\langle 0,1,1,1,1,\cdots\rangle\)。
\(a=\langle 1,0,1,0,1,\cdots \rangle\)。
\(a=\langle 1,2,3,4,\cdots \rangle\)。
\(a_n=\binom{m}{n}\)（\(m\) 是常數，\(n\ge 0\)）。
\(a_n=\binom{m+n}{n}\)（\(m\) 是常數，\(n\ge 0\)）。

答案

第一個：

\[ F(x)=\sum_{n\ge 1}x^n=\dfrac{x}{1-x} \]

第二個：

\[ \begin{aligned} F(x)&=\sum_{n\ge 0}x^{2n}\\ &=\sum_{n\ge 0}(x^2)^{n}\\ &=\frac{1}{1-x^2} \end{aligned} \]

第三個（求導）：

\[ \begin{aligned}F(x)&=\sum_{n\ge 0}(n+1)x^n\\&=\sum_{n\ge 1}nx^{n-1}\\&=\sum_{n\ge 0}(x^n)'\\&=\left(\frac{1}{1-x}\right)'\\&=\frac{1}{(1-x)^2}\end{aligned} \]

第四個（二項式定理）：

\[ F(x)=\sum_{n\ge 0}\binom{m}{n}x^n=(1+x)^m \]

第五個：

\[ F(x)=\sum_{n\ge 0}\binom{m+n}{n}x^n=\frac{1}{(1-x)^{m+1}} \]

可以使用歸納法證明。

首先當 \(m=0\) 時，有 \(F(x)=\dfrac{1}{1-x}\)。

而當 \(m>0\) 時，有

\[ \begin{aligned} \frac{1}{(1-x)^{m+1}} &=\frac{1}{(1-x)^m}\frac{1}{1-x}\\ &=\left(\sum_{n\ge 0}\binom{m+n-1}{n}x^n \right)\left(\sum_{n\ge 0}x^n \right)\\ &=\sum_{n\ge 0} x^n\sum_{i=0}^n \binom{m+i-1}{i}\\ &=\sum_{n\ge 0}\binom{m+n}{n}x^n \end{aligned} \]

斐波那契數列的生成函數

接下來我們來推導斐波那契數列的生成函數。

斐波那契數列定義為 \(a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}\;(n>1)\)。設它的普通生成函數是 \(F(x)\)，那麼根據它的遞推式，我們可以類似地列出關於 \(F(x)\) 的方程：

\[ F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0 \]

那麼解得

\[ F(x)=\frac{x}{1-x-x^2} \]

那麼接下來的問題是，如何求出它的展開形式？

展開方式一

不妨將 \(x+x^2\) 當作一個整體，那麼可以得到

\[ \begin{aligned} F(x)&=\frac{x}{1-(x+x^2)}\\ &=\sum_{n\ge 0}(x+x^2)^n\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{2i}x^{n-i}\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{n+i}\\ &=\sum_{n\ge 0}x^n\sum_{i=0}^n\binom{n-i}{i} \end{aligned} \]

我們得到了 \(a_n\) 的通項公式，但那並不是我們熟知的有關黃金分割比的形式。

展開方式二

考慮求解一個待定係數的方程：

\[ \frac{A}{1-ax}+\frac{B}{1-bx}= \frac{x}{1-x-x^2} \]

通分得到

\[ \frac{A-Abx+B-aBx}{(1-ax)(1-bx)} = \frac{x}{1-x-x^2} \]

待定項係數相等，我們得到

\[ \begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1 \end{cases} \]

解得

\[ \begin{cases} A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ a=\frac{1+\sqrt{5}}{2}\\ b=\frac{1-\sqrt{5}}{2} \end{cases} \]

那麼我們根據等比數列的展開式，就可以得到斐波那契數列的通項公式：

\[ \frac{x}{1-x-x^2}=\sum_{n\ge 0}x^n \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right) \]

這也被稱為斐波那契數列的另一個封閉形式（\(\frac{x}{1-x-x^2}\) 是一個封閉形式）。

對於任意多項式 \(P(x),Q(x)\)，生成函數 \(\dfrac{P(x)}{Q(x)}\) 的展開式都可以使用上述方法求出。在實際運用的過程中，我們往往先求出 \(Q(x)\) 的根，把分母表示為 \(\prod (1-p_ix)^{d_i}\) 的形式，然後再求分子。

當對分母進行因式分解但有重根時，每有一個重根就要多一個分式，如考慮生成函數

\[ G(x)=\frac{1}{(1-x)(1-2x)^2} \]

的係數的通項公式，那麼有

\[ G(x)=\frac{c_0}{1-x}+\frac{c_1}{1-2x}+\frac{c_2}{(1-2x)^2} \]

解得

\[ \begin{cases} c_0&=1\\ c_1&=-2\\ c_2&=2 \end{cases} \]

那麼

\[ [x^n]G(x)=1-2^{n+1}+(n+1)\cdot 2^{n+1} \]

牛頓二項式定理

我們重新定義組合數的運算：

\[ \binom{r}{k}=\frac{r^{\underline{k}}}{k!}\quad(r\in\mathbf{C},k\in\mathbf{N}) \]

注意 \(r\) 的範圍是複數域。在這種情況下。對於 \(\alpha\in\mathbf{C}\)，有

\[ (1+x)^{\alpha}=\sum_{n\ge 0}\binom{\alpha}{n}x^n \]

二項式定理其實是牛頓二項式定理的一個特殊情況。

卡特蘭數的生成函數

參考 Catalan 數的封閉形式

應用

接下來給出一些例題，來介紹生成函數在 OI 中的具體應用。

食物

在許多不同種類的食物中選出 \(n\) 個，每種食物的限制如下：

承德漢堡：偶數個
可樂：0 個或 1 個
雞腿：0 個，1 個或 2 個
蜜桃多：奇數個
雞塊：4 的倍數個
包子：0 個，1 個，2 個或 3 個
土豆片炒肉：不超過一個。
麪包：3 的倍數個

每種食物都是以「個」為單位，只要總數加起來是 \(n\) 就算一種方案。對於給出的 \(n\) 你需要計算出方案數，對 \(10007\) 取模。

這是一道經典的生成函數題。對於一種食物，我們可以設 \(a_n\) 表示這種食物選 \(n\) 個的方案數，並求出它的生成函數。而兩種食物一共選 \(n\) 個的方案數的生成函數，就是它們生成函數的卷積。多種食物選 \(n\) 個的方案數的生成函數也是它們生成函數的卷積。

在理解了方案數可以用卷積表示以後，我們就可以構造生成函數（標號對應題目中食物的標號）：

\(\displaystyle\sum_{n\ge 0}x^{2n}=\dfrac{1}{1-x^2}\)。
\(1+x\)。
\(1+x+x^2=\dfrac{1-x^3}{1-x}\)。
\(\dfrac{x}{1-x^2}\)。
\(\displaystyle \sum_{n\ge 0}x^{4n}=\dfrac{1}{1-x^4}\)。
\(1+x+x^2+x^3=\dfrac{1-x^4}{1-x}\)。
\(1+x\)。
\(\dfrac{1}{1-x^3}\)。

那麼全部乘起來，得到答案的生成函數：

\[ F(x)=\frac{(1+x)(1-x^3)x(1-x^4)(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x^4)(1-x)(1-x^3)} =\frac{x}{(1-x)^4} \]

然後將它轉化為展開形式（使用封閉形式練習中第五個練習）：

\[ F(x)=\sum_{n\ge 1}\binom{n+2}{n-1}x^n \]

因此答案就是 \(\dbinom{n+2}{n-1}=\dbinom{n+2}{3}\)。

Sweet

「CEOI2004」Sweet

有 \(n\) 堆糖果。不同的堆裏糖果的種類不同（即同一個堆裏的糖果種類是相同的，不同的堆裏的糖果的種類是不同的）。第 \(i\) 個堆裏有 \(m_i\) 個糖果。現在要吃掉至少 \(a\) 個糖果，但不超過 \(b\) 個。求有多少種方案。

兩種方案不同當且僅當吃的個數不同，或者吃的糖果中，某一種糖果的個數在兩個方案中不同。

\(n\le 10,0\le a\le b\le 10^7,m_i\le 10^6\)。

在第 \(i\) 堆吃 \(j\) 個糖果的方案數（顯然為 1）的生成函數為

\[ F_i(x)=\sum_{j=0}^{m_i}x^j=\frac{1-x^{m_i+1}}{1-x} \]

因此總共吃 \(i\) 個糖果的方案數的生成函數就是

\[ G(x)=\prod_{i=1}^n F_i(x)=(1-x)^{-n}\prod_{i=1}^n(1-x^{m_i+1}) \]

現在我們要求的是 \(\sum_{i=a}^b[x^i]G(x)\)。

由於 \(n\le 10\)，因此我們可以暴力展開 \(\prod_{i=1}^n(1-x^{m_i+1})\)（最多隻有 \(2^n\) 項）。

然後對 \((1-x)^{-n}\) 使用牛頓二項式定理：

\[ \begin{aligned} (1-x)^{-n} &=\sum_{i\ge 0}\binom{-n}{i}(-x)^i\\ &=\sum_{i\ge 0}\binom{n-1+i}{i}x^i \end{aligned} \]

我們枚舉 \(\prod_{i=1}^n(1-x^{m_i+1})\) 中 \(x^k\) 項的係數，假設為 \(c_k\)。那麼它和 \((1-x)^{-n}\) 相乘後，對答案的貢獻就是

\[ c_k\sum_{i=a-k}^{b-k}\binom{n-1+i}{i}=c_k\left( \binom{n+b-k}{b-k}- \binom{n+a-k-1}{a-k-1} \right) \]

這樣就可以 \(O(b)\) 地求出答案了。

時間複雜度 \(O(2^n+b)\)。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：sshwy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用