普通生成函数

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

$$F(x)=\sum _n{a}_n{x}^n$$

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

1. 序列 $a=⟨1,2,3⟩$ 的普通生成函数是 $1+2x+3x^2$。
2. 序列 $a=⟨1,1,1,\cdots ⟩$ 的普通生成函数是 $\sum _{n\ge 0}{x}^n$。
3. 序列 $a=⟨1,2,4,8,16,\cdots ⟩$ 的生成函数是 $\sum _{n\ge 0}{2}^n{x}^n$。
4. 序列 $a=⟨1,3,5,7,9,\cdots ⟩$ 的生成函数是 $\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)$ 是序列 $⟨a_n\pm b_n⟩$ 的普通生成函数。

考虑乘法运算，也就是卷积：

$$F(x)G(x)=\sum _n{x}^n\sum _{i=0}^n{a}_i{b}_{n-i}$$

因此 $F(x)G(x)$ 是序列 $⟨\sum _{i=0}^n{a}_i{b}_{n-i}⟩$ 的普通生成函数。

封闭形式

在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。

例如 $⟨1,1,1,\cdots ⟩$ 的普通生成函数 $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$ 的封闭形式。

考虑等比数列 $⟨1,p,p^2,p^3,p^4,\cdots ⟩$ 的生成函数 $F(x)=\sum _{n\ge 0}{p}^n{x}^n$，有

$$\begin{array}{rl}F(x)px+1& =F(x)\\ F(x)& =\frac{1}{1-px}\end{array}$$

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

答案

第一个：

$$F(x)=\sum _{n\ge 1}{x}^n={\displaystyle \frac{x}{1-x}}$$

第二个：

$$\begin{array}{rl}F(x)& =\sum _{n\ge 0}{x}^{2n}\\ & =\sum _{n\ge 0}(x^2{)}^n\\ & =\frac{1}{1-x^2}\end{array}$$

第三个（求导）：

$$\begin{array}{rl}F(x)& =\sum _{n\ge 0}(n+1)x^n\\ & =\sum _{n\ge 1}n{x}^{n-1}\\ & =\sum _{n\ge 0}(x^n{)}^{\prime }\\ & ={\left(\frac{1}{1-x}\right)}^{\prime }\\ & =\frac{1}{(1-x{)}^2}\end{array}$$

第四个（二项式定理）：

$$F(x)=\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{m}{n})x^n=(1+x{)}^m$$

第五个：

$$F(x)=\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{m+n}{n})x^n=\frac{1}{(1-x{)}^{m+1}}$$

可以使用归纳法证明。

首先当 $m=0$ 时，有 $F(x)={\displaystyle \frac{1}{1-x}}$。

而当 $m>0$ 时，有

$$\begin{array}{rl}\frac{1}{(1-x{)}^{m+1}}& =\frac{1}{(1-x{)}^m}\frac{1}{1-x}\\ & =\left(\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{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(\genfrac{}{}{0ex}{}{m+i-1}{i})\\ & =\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{m+n}{n})x^n\end{array}$$

斐波那契数列的生成函数

接下来我们来推导斐波那契数列的生成函数。

斐波那契数列定义为 $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^{2}F(x)-a_{0}x+a_{1}x+a_0$$

那么解得

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

那么接下来的问题是，如何求出它的展开形式？

展开方式一

不妨将 $x+x^2$ 当作一个整体，那么可以得到

$$\begin{array}{rl}F(x)& =\frac{x}{1-(x+x^2)}\\ & =\sum _{n\ge 0}(x+x^2{)}^n\\ & =\sum _{n\ge 0}\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})x^{2i}{x}^{n-i}\\ & =\sum _{n\ge 0}\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})x^{n+i}\\ & =\sum _{n\ge 0}{x}^n\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n-i}{i})\end{array}$$

我们得到了 $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{array}{l}A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1\end{array}$$

解得

$$\{\begin{array}{l}A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ a=\frac{1+\sqrt{5}}{2}\\ b=\frac{1-\sqrt{5}}{2}\end{array}$$

那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式：

$$\frac{x}{1-x-x^2}=\sum _{n\ge 0}{x}^n\frac{1}{\sqrt{5}}({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n)$$

这也被称为斐波那契数列的另一个封闭形式（$\frac{x}{1-x-x^2}$ 是一个封闭形式）。

对于任意多项式 $P(x),Q(x)$，生成函数 ${\displaystyle \frac{P(x)}{Q(x)}}$ 的展开式都可以使用上述方法求出。在实际运用的过程中，我们往往先求出 $Q(x)$ 的根，把分母表示为 $\prod (1-p_{i}x{)}^{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{array}{ll}{c}_0& =1\\ c_1& =-2\\ c_2& =2\end{array}$$

那么

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

牛顿二项式定理

我们重新定义组合数的运算：

$$(\genfrac{}{}{0ex}{}{r}{k})=\frac{r^{\underset{―}{k}}}{k!}(r\in \mathbf{C},k\in \mathbf{N})$$

注意 $r$ 的范围是复数域。在这种情况下。对于 $\alpha \in \mathbf{C}$，有

$$(1+x{)}^{\alpha }=\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{\alpha }{n})x^n$$

二项式定理其实是牛顿二项式定理的一个特殊情况。

卡特兰数的生成函数

参考 Catalan 数的封闭形式

应用

接下来给出一些例题，来介绍生成函数在 OI 中的具体应用。

食物

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

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

1. ${\displaystyle \sum _{n\ge 0}{x}^{2n}={\displaystyle \frac{1}{1-x^2}}}$。
2. $1+x$。
3. $1+x+x^2={\displaystyle \frac{1-x^3}{1-x}}$。
4. ${\displaystyle \frac{x}{1-x^2}}$。
5. ${\displaystyle \sum _{n\ge 0}{x}^{4n}={\displaystyle \frac{1}{1-x^4}}}$。
6. $1+x+x^2+x^3={\displaystyle \frac{1-x^4}{1-x}}$。
7. $1+x$。
8. ${\displaystyle \frac{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}(\genfrac{}{}{0ex}{}{n+2}{n-1})x^n$$

因此答案就是 ${\displaystyle (\genfrac{}{}{0ex}{}{n+2}{n-1})}={\displaystyle (\genfrac{}{}{0ex}{}{n+2}{3})}$。

Sweet

在第 $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{array}{rl}(1-x{)}^{-n}& =\sum _{i\ge 0}(\genfrac{}{}{0ex}{}{-n}{i})(-x{)}^i\\ & =\sum _{i\ge 0}(\genfrac{}{}{0ex}{}{n-1+i}{i})x^i\end{array}$$

我们枚举 $\prod _{i=1}^n(1-x^{m_i+1})$ 中 $x^k$ 项的系数，假设为 $c_k$。那么它和 $(1-x{)}^{-n}$ 相乘后，对答案的贡献就是

$$c_k\sum _{i=a-k}^{b-k}(\genfrac{}{}{0ex}{}{n-1+i}{i})=c_k((\genfrac{}{}{0ex}{}{n+b-k}{b-k})-(\genfrac{}{}{0ex}{}{n+a-k-1}{a-k-1}))$$

这样就可以 $O(b)$ 地求出答案了。

时间复杂度 $O(2^n+b)$。

本页面最近更新：2024/11/19 22:34:33，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：sshwy, CCXXXI, countercurrent-time, Enter-tainer, Great-designer, hly1204, Molmin, NachtgeistW, purple-vine, schtonn, shuzhouliu, skylee03, SukkaW
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用