docs/math/poly/ogf.md
author: sshwy
序列 $a$ 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：
$$ F(x)=\sum_{n}a_n x^n $$
$a$ 既可以是有穷序列，也可以是无穷序列．常见的例子（假设 $a$ 以 $0$ 为起点）：
换句话说，如果序列 $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} $$
等比数列的封闭形式与展开形式是常用的变换手段．
???+ note "小练习" 请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）．难度是循序渐进的．
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$）．
??? note "答案" 第一个：
$$
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) &= \dfrac{x}{1-(x+x^2)} \ &= x\sum_{k=0}^{\infty}(x+x^2)^k \ &= x\sum_{k=0}^{\infty}\sum_{i=0}^k\binom{k}{i}x^{k-i}(x^2)^i \ &= \sum_{k=0}^{\infty}\sum_{i=0}^k\binom{k}{i}x^{k+i+1} \ &= \sum_{n=1}^{\infty}\sum_{i=0}^{\lfloor(n-1)/2\rfloor}\binom{n-i-1}{i}x^n. \end{aligned} $$
最后一步中，令 $n=k+i+1$ 并更换求和顺序．由此，可以得到通项公式：
$$ a_n = \sum_{i=0}^{\lfloor(n-1)/2\rfloor}\binom{n-i-1}{i}. $$
这并不是我们熟知的有关黄金分割比的形式．
考虑求解一个待定系数的方程：
$$ \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 中的具体应用．
???+ note "食物" 在许多不同种类的食物中选出 $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$ 个的方案数的生成函数也是它们生成函数的卷积．
在理解了方案数可以用卷积表示以后，我们就可以构造生成函数（标号对应题目中食物的标号）：
那么全部乘起来，得到答案的生成函数：
$$ 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}$．
???+ note "「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)$．