本博客在看完《多项式：从入门到全家桶》和《组合数学：从入门到被入门》后食用更佳。

省流：

普通生成函数： \(\displaystyle f(x)=\sum_{i\ge0} a_ix^i\)

指数生成函数： \(\displaystyle f(x)=\sum_{i\ge0} \frac{a_ix^i}{i!}\)

狄利克雷函数生成函数： \(\displaystyle f(x)=\sum_{i\ge0}\frac{a^i}{i^x}\)

又记作OGF(Ordinary Generating Function)。

本章中记 \(\langle a_x\rangle\) 为序列 \(a\) 的普通生成函数 。

定义式：\(\displaystyle \langle a_x\rangle=\sum_{i\ge0} a_ix^i\)

并且，如果 \(f(x)\) 为一个函数，我们记 \(f_n\) 为其多项式表达中 \(x^n\) 的系数，反之亦然，即 \(f=\langle f_x\rangle\)。

加减法很显然。

乘法仔细想一想其实也不难，由基础的乘法分配律可知：

原本需要 \(O(n^2)\) 的时间计算，使用FFT或NTT即可加速到 \(O(n\log n)\)，有关多项式快速运算的内容请见《多项式：从入门到全家桶》。

举个栗子。

假设我们现在有一个函数叫做 \(f(x)=\langle 1,1,1,\cdots,1\rangle\)。

我们发现这个式子有一个性质：

于是 \(f(x)=\frac 1{x-1}\)，这就是 \(f(x)\) 的封闭形式。

一般来说，把一个式子写成它的封闭形式能够便于推式子。

比如让你求 \(f(x)*(x^2-2x+1)\) ，我们用定义式可能要推很久，但你用封闭形式就能马上推出上式 \(=x-1\)。

建议大家多练习一下推封闭形式。

多项式的四则运算，求导，积分等所有运算对封闭形式同样适用。

小练习：请求出以下几个式子的生成函数的封闭形式。

可使用归纳法进行证明。

\(m=0\) 时显然成立。

\(m>0\) 时：

我们定义 \(a_0=1,a_1=a,a_i=a_{i-1}+a_{i-2}(i\ge2)\)，那我们该怎样求出 \(\langle a_t\rangle\) 呢？

一个显然的方法就是利用 \(a_i=a_{i-1}+a_{i-2}\) 这一性质。

我们知道多项式乘 \(x\) 相当于把这个多项式向高次项移一位。

于是我们可以得到这个方程：

解得 \(f(x)=\frac 1{1-x-x^2}\) 。

于是我们接下来的问题就是如何把这个式子展开。

我们将 \(x+x^2\) 视作一个整体。则有：

我们发现我们成功地解决了通项公式，但这是一个组合数求和的形式，并不是我们熟知的黄金分割比。

所以这个方法不行。

考虑求解一个待定系数的方程：

通分后得到：

则有：

它的一组解为：

于是

这有的时候也被称为斐波那契数列的第二个封闭形式。（第一个封闭形式：\(\frac x{1-x-x^2}\)）

其实，我们求 \(\frac{p(x)}{q(x)}\) 的时候基本上都会用这种办法（即待定系数法）求出它的展开式。

一般来说，对于 \(q(x)\) 比较容易因式分解时，我们就可以直接把几个分式的分母表示成它的几个因式，然后列方程求解。

如果有相同因式（即次数 \(\ge 2\)），就设其中一个分式为这个因式的高次方。

比如 \(\frac 1{(1-x)(1-2x)^2}\) 就可以写成 \(\frac A{1-x}+\frac B{1-2x}+\frac C{(1-2x)^2}\) 的形式。

生成函数主要应用于各种计数问题，其目的是用简单的式子把一些复杂的转移表示出来。

下面举几个例子：

这个不说了，前面的斐波那契数列的例子已经说过了。

传统的解决背包问题的方法就是dp，但这种办法在有些比较复杂的题上就行不通。

其实，如果你要求价值和刚好为 \(n\) 的答案（一般是方案数），你可以把这个答案写成生成函数的形式。

就拿方案数来说，你对每种不同的限制计算出它的生成函数，并把它们乘起来，最终式子的第 \(n\) 项就是答案。

以某道题为例：

在许多不同种类的食物中选出 \(n\) 个，\(n\le 10^{500}\)，求方案数，对 \(10007\) 取模，每种食物的限制如下：

我们设 \(a_{i,j}\) 表示第 \(i\) 种食物选 \(j\) 个的方案数，则 \([x^n](\prod_i\langle a_{i,t}\rangle)\) 就是答案。

考虑卷积的定义，值为 \(1\) ，下标和为 \(n\) 的几项相乘就代表分别选择那几项是一种符合条件的方案，而这对 \(x^n\) 的系数贡献为 \(1\)。

建议此处读者自行推导一下这几种食物的生成函数，争取自己把式子推出来。

把上面所有式子乘起来可得：

由之前的第五条小练习，我们知道这就是 \(\displaystyle\sum_{n\ge 1}x^n\binom {n+1}{n-2}\) 。

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

代码略。

有的时候，有些题会让你求恰好等于 \(n\) 的方案数、在某个区间内的方案数，或者对于每个数都求一遍。

这种题有的时候就可以用生成函数的形式推。（尤其是有包含组合数的式子）

结合上某些多项式高科技，一般可以比传统方法快很多。

又记作EGF(Exponential Generating Function)。

本章中记 \(\{a_x\}\) 为序列 \(a\) 的指数生成函数。

定义式：\(\displaystyle \{a_x\}=\sum_{i\ge0} \frac{a_ix^i}{i!}\)

加减法也很显然。

乘法可能会稍稍难一些，但经过一些推导实际上也不难。

指数生成函数与普通生成函数互转的公式：

另外，由于指数生成函数的定义，其导数和积分很好求。

疯毙形式（确信）

一般来说，指数生成函数的多项式的封闭形式和泰勒展开有关。（因为泰勒展开主要就是 \(\sum_{i\ge0} \frac{a_ix^i}{i!}\) 的形式）

我们考虑 \(f(x)=\{1,1,1,1,\cdots\}\) ，有两种方式求出它的封闭形式：

类似的，等比数列的生成函数 \(f(x)=\{1,p,p^2,p^3,\cdots\}\) 的封闭形式就是 \(e^px\) 。

长度为 \(n\) 的排列数（\(n!\)）的EGF是:

圆排列数的定义是旋转后方案等价的排列数。

长度为 \(n\) 的圆排列数（\((n-1)!\)）的EGF是：

于是我们就有 \(f(x)=\exp g(x)\) 。

但这只是数学上的推导，我们还需要一些直观理解。

我们引入一个概念，叫做置换环。

对于一个排列 \(p\) ，我们对于每个 \(i\) 向 \(p_i\) 连边，置换环就是这张图中所有连成的环。（包括自环）

并且对于两个排列，当且仅当它们所有的置换环相同时，这两个排列才相同。

于是对于长度为 \(n\) 的排列数，我们可以按照以下这个步骤进行计算：

这样得出的方案数就是长度为 \(n\) 的排列数。

更进一步，我们发现对于一个集合，构造置换环的方案数就是这个集合的圆排列数。

所以，长度为 \(n\) 的排列数就是将 \(1,2,\cdots,n\) 划分成若干集合，每一部分做圆排列数的方案数。

因此，多项式 \(\exp\) 的直观理解就是：

若 \(f(x)=\exp g(x)\) ，则 \(f_n\) 代表将 \(1,2,\cdots,n\) 分成若干集合，每一集合 \(S\) 的方案数为 \(g_{|S|}\) 时总共的方案数。

类似的，我们举一些例子：

如果 \(n\) 个带标号点的生成树个数的EGF为 \(f(x)\) ，则 \(n\) 个带标号点的生成森林个数的EGF为 \(\exp f(x)\) 。

如果 \(n\) 个带标号点的无向连通图个数的EGF为 \(f(x)\) ，则 \(n\) 个带标号点的无向图个数的EGF为 \(\exp f(x)\) 。

因此，只要这两个中求出任意一个，则可利用多项式 \(\ln\) 或 \(\exp\) 求出另一个。

举个例子：求错排数的EGF。

我们都知道错排数就是 \(\forall i,i\ne p_i\) 的方案数，也就是不存在长度为 \(1\) 的置换环的个数。

而后者的EGF为 \(\displaystyle\sum_{i\ge 2} \frac{x^i}i=\sum_{i\ge 1} \frac{x^i}i-x=-\ln (1-x)-x\) 。

于是错排数的EGF为 \(\exp(-\ln (1-x)-x)\) 。

前面说过，不讲。

可转化为EGF进行求解。

例：分别求出有 \(i(1\le i\le 10^5)\) 个节点的竞赛图（一个完全图，但是每条边定向）中至少有一条哈密顿回路的方案数。

不妨设这个答案数组为 \(g_i\) ，有 \(i\) 个节点的竞赛图个数为 \(\displaystyle f_i=2^\binom i2=2^\frac{i(i-1)}2\)。 由于一张竞赛图缩点就变成了一个链状DAG（有向无环图），因此我们枚举最后一个连通块内有多少点：

这个式子和分治FFT很像，但是多了一个组合数。

于是我们设 \(f'_i=\frac{f_i}{i!}\) ， \(g'_i=\frac{g_i}{i!}\)。

于是就有

化为分治FFT或多项式求逆即可。

顺便复习一下上面那个式子如何多项式求逆：

由于 \(f_0=1\) （计算方案时可定义），则原式可化为：

即：\(f(x)=\frac 1{1-g(x)}\)，\(g(x)=1-\frac1{f(x)}\)。

以后再说。

本章主要记载了推式子过程中容易用到的知识。

见《组合数学：从入门到被入门》。

我们都知道，著名的二项式定理是指：

更进一步，我们把组合数的定义域拓展到复数上：

其中 \(a^\underline b=a(a-1)(a-2)\cdots(a-b+1)\) 。

于是我们就有了：

虽然这个定理不常用，但有的时候推式子还是用得上的。