跳转至

普通生成函数

序列 \(a\) 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：

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

\(a\) 既可以是有穷序列，也可以是无穷序列。常见的例子（假设 \(a\) 以 \(0\) 为起点）：

  1. 序列 \(a=\langle 1,2,3\rangle\) 的普通生成函数是 \(1+2x+3x^2\)。
  2. 序列 \(a=\langle 1,1,1,\cdots\rangle\) 的普通生成函数是 \(\sum_{n\ge 0}x^n\)。
  3. 序列 \(a=\langle 1,2,4,8,16,\cdots\rangle\) 的生成函数是 \(\sum_{n\ge 0}2^nx^n\)。
  4. 序列 \(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} \]

等比数列的封闭形式与展开形式是常用的变换手段。

小练习

请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）。难度是循序渐进的。

  1. \(a=\langle 0,1,1,1,1,\cdots\rangle\)。
  2. \(a=\langle 1,0,1,0,1,\cdots \rangle\)。
  3. \(a=\langle 1,2,3,4,\cdots \rangle\)。
  4. \(a_n=\binom{m}{n}\)（\(m\) 是常数，\(n\ge 0\)）。
  5. \(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\) 个，每种食物的限制如下：

  1. 承德汉堡：偶数个
  2. 可乐：0 个或 1 个
  3. 鸡腿：0 个，1 个或 2 个
  4. 蜜桃多：奇数个
  5. 鸡块：4 的倍数个
  6. 包子：0 个，1 个，2 个或 3 个
  7. 土豆片炒肉：不超过一个。
  8. 面包：3 的倍数个

每种食物都是以「个」为单位，只要总数加起来是 \(n\) 就算一种方案。对于给出的 \(n\) 你需要计算出方案数，对 \(10007\) 取模。

这是一道经典的生成函数题。对于一种食物，我们可以设 \(a_n\) 表示这种食物选 \(n\) 个的方案数，并求出它的生成函数。而两种食物一共选 \(n\) 个的方案数的生成函数，就是它们生成函数的卷积。多种食物选 \(n\) 个的方案数的生成函数也是它们生成函数的卷积。

在理解了方案数可以用卷积表示以后，我们就可以构造生成函数（标号对应题目中食物的标号）：

  1. \(\displaystyle\sum_{n\ge 0}x^{2n}=\dfrac{1}{1-x^2}\)。
  2. \(1+x\)。
  3. \(1+x+x^2=\dfrac{1-x^3}{1-x}\)。
  4. \(\dfrac{x}{1-x^2}\)。
  5. \(\displaystyle \sum_{n\ge 0}x^{4n}=\dfrac{1}{1-x^4}\)。
  6. \(1+x+x^2+x^3=\dfrac{1-x^4}{1-x}\)。
  7. \(1+x\)。
  8. \(\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)\)。