生成函数

定义

生成函数（Generating function），又称母函数，是一种形式幂级数。它由一个序列（可以是无穷的）和一个核函数生成。如下：

\[ G(x)=\sum_{n}{a_{n}k_{n}(x)} \]

其中 \(a\) 为序列， \(k_n(x)\) 为核函数。
不同的核函数会导出不同的生成函数，拥有不同的性质。常见的有：

• 普通生成函数： \(k_{n}(x)=x^{n}k\)
• 指数生成函数： \(k_{n}(x)=\frac{x^{n}}{n!}k\)
• 狄利克雷生成函数： \(k_{n}(x)=\frac{1}{n^{x}}k\)

普通生成函数

普通生成函数就是最常见的生成函数。一般来说，序列 \((a_{n})_{n\in \mathbb{N}}\) 的生成函数为：

\[ G(a_{n};x)=\sum^{\infty}_{n=0}a_{n}x^{n} \]

排列问题

普通生成函数可以用来解决这类问题：

确定一个序列 \((a_{n})_{n\in \mathbb{N}}\) ，其中 \(a_{i} \le v_{i}\) ，同时有一个权重序列 \((b_{n})\) ，计算使得 \(\sum_{i=1}^{n}{a_{i}b_{i}}\) 为一个确定值 \(k\) 的方案数。

则我们可以求出生成函数：

\[ G(x)=\prod_{i=1}^{n}{\sum_{j=0}^{v_{i}}{x^{jb_{i}}}} \]

注意上述的 \(n,v_{i}\) 都可以是无穷大。
展开之后得到的结果中， \(k\) 次项的系数就是答案。

举一个例子：

有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？每种重量各有几种可能方案？
我们用母函数来解决这个问题：
可知题目中 \(v_{1}=v_{2}=v_{3}=v_{4}=1\) ， \(b_{1}=1,b_{2}=2,b_{3}=3,b_{4}=4\)
那么生成函数就是：

\[ \begin{aligned} G(x)&=(x^{0}+x^{1})(x^{0}+x^{2})(x^{0}+x^{3})(x^{0}+x^{4})\\ &=(1+x^{1})(1+x^{2})(1+x^{3})(1+x^{4})\\ &=1+x+x^{2}+2x^{3}+2x^{4}+2x^{5}+2x^{6}+2x^{7}+x^{8}+x^{9}+x^{10} \end{aligned} \]

这个函数中可以看出重量为3克的方案有两种，重量为7克的方案有两种，重量为10克的有一种。

不难发现指数表示重量，系数表示方案。

虽然生成函数看上去很复杂，但实际上易于理解。

我们把问题转化为一个（完全）背包问题：

有 \(n\) 中物品，每个物品有 \(v_{i}\) 件，价值为 \(b_{i}\) ，选取若干物品，使得总价值恰好为 \(k\) ，求方案数。

相比起dp求解，生成函数简直就像是暴力。它把价值表现在指数上，把方案数表现在系数上，先列出每一种物品的所有可能，再把所有的物品都乘在一起。换句话说，问题的生成函数 \(G(x)=\prod_{i=1}^{n}{F_{i}(x)}\) 其中 \(F_{i}(x)\) 表示第 \(i\) 个物品的生成函数。

直接用代码写这种题大概长这样：

1
2
3
4
5

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= v[i] && j * b[i] <= k; j++) ans += cnt[k - j * b[i]];
    for (int j = 0; j <= v[i] && j * b[i] <= k; j++) cnt[j * b[i]]++;
}
printf("%d\n", ans);

在 \(v_{i}\) 很大的情况下，复杂度是 \(O(nk)\) 的，和dp复杂度一致。

但生成函数绝对不是用来重写dp的，借助数学上的一些公式，一些特定的问题会有更低的复杂度。

权值相同，个数为一

当 \(b_{1}=b_{2}=...=b_{n}=b,v_{1}=v_{2}=...=v_{n}=1\) 时

\[ \begin{aligned} G(x)&=\prod_{i=1}^{n}{\sum_{j=0}^{v_{i}}{x^{jb_{i}}}}\\ &=(1+x^{b})^{n} \end{aligned} \]

用二项式定理展开：

\[ G(x)=\sum_{i=0}^{n}C_{n}^{i}x^{bi} \]

则 \(bk\) 次项的系数为 \(C_{n}^{k}\) 。

权值相同，个数无限

前置知识：

\[ \sum_{i=0}^{\infty}{x^{i}}=\frac{1}{1-x}(x < 1) \]

证明：由等比数列求和公式得：

\[ \begin{aligned} \sum_{i=0}^{n}{x^{i}}&=\frac{1+x^{n+1}}{1-x}\\ \because \lim_{x \to \infty}x^{n+1} &= 0\\ \therefore \lim_{x \to \infty}{\frac{1+x^{n+1}}{1-x}}&=\frac{1}{1-x}\\ \therefore \sum_{i=0}^{n}{x^{i}}&=\frac{1}{1-x} \end{aligned} \]

当 \(b_{1}=b_{2}=...=b_{n}=b,v_{1}=v_{2}=...=v_{n}\) 时，

\[ \begin{aligned} G(x)&=\prod_{i=1}^{n}{\sum_{j=0}^{v_{i}}{x^{jb_{i}}}}\\ &=(\frac{1}{1-x^{b}})^{n}\\ &=(1-x^b)^{-n} \end{aligned} \]

用广义二项式定理展开：

\[ \begin{aligned} G(x)&=\sum_{i=0}^{\infty}{\frac{-m(-m-1)...(-m-i+1)}{i!}(-x)^{bi}}\\ &=\sum_{i=0}^{\infty}{\frac{(-1)^{i}m(m+1)...(m+i-1)}{i!}(-1)^{i}x^{bi}}\\ &=\sum_{i=0}^{\infty}{\frac{(m+i-1)!}{i!(m-1)!}x^{bi}}\\ &=\sum_{i=0}^{\infty}{C_{m+i-1}^{m-1}x^{bi}} \end{aligned} \]

则 \(bk\) 项的系数为 \(C_{m+k-1}^{m-1}\) 。

权值连续，个数无限，种类无限

当 \(\forall i \in \mathbb{N}, b_{i}=i,v_{i}=\infty\) 时：

同上一种情况易得：

\[ G(x)=\prod_{i=1}^{\infty}{\frac{1}{1-x^{i}}} \]

这要怎么展开呢？欧拉研究过这个连乘式，并给出了五边形数定理：

\[ \prod_{i=1}^{\infty}{(1-x^{i})}=\sum_{i=-\infty}^{\infty}{(-1)^{i}x^{\frac{i(3i-1)}{2}}}=\sum_{i=0}^{\infty}{(-1)^{i}x^{\frac{i(3i\pm1)}{2}}} \]

展开之后为 \(1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}+...\)

其中\((-1)^{n} \cdot \frac{n(3n\pm1)}{2}\) 恰为广义五边形数。

注意如下变换： \((-1)^{n} \cdot \frac{n(3n\pm1)}{2}=(-1)^{n} \cdot \frac{\pm n(\pm 3n - 1)}{2}\)

我们设 \(\prod_{i=1}^{\infty}{\frac{1}{1-x^{i}}}=\sum_{i=0}^{\infty}P(i)x^{i}\) ，则：

\[ \begin{aligned} \because \prod_{i=1}^{\infty}{(1-x^{i})} \cdot \prod_{i=1}^{\infty}{\frac{1}{1-x^{i}}}=\prod_{i=1}^{\infty}{\frac{1-x^{i}}{1-x^{i}}}&=1\\ \therefore \sum_{i=0}^{\infty}P(i)x^{i} \cdot \sum_{i=0}^{\infty}{(-1)^{i}x^{\frac{i(3i\pm1)}{2}}}&=1 \end{aligned} \]

展开可得：

\[ (1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+...)(1+P(1)x+P(2)x...)=1 \]

原式为1，说明除了常数项系数都为0。展开可得 \(n\) 次项的系数为：

\[ \begin{aligned} P(n)-P(n-1)-P(n-2)+P(n-5)+...=0\\ \therefore P(n)=\sum_{i}{P((-1)^{i} \cdot \frac{\pm i(\pm 3i-1)}{2})} \end{aligned} \]

将 \((-1)^{i} \cdot \frac{\pm i(\pm 3i-1)}{2}\) 预处理，就可以 \(O(n\sqrt{n})\) 递推求出 \(P(x)\) 了。

而 \(P(k)\) 就是原生成函数 \(k\) 次项的系数。

例子：整数划分问题 一个正整数可以被用多少种方式划分为其他正整数的和？例如，4可以被划分为4、2+2、1+3、1+1+2、1+1+1+1。

序列生成函数

也总是有数学题，让我们求一个序列的通项公式，其实这可以由生成函数轻易地求出。

首先题目得告诉你数列，它总不能告诉你通项式是吧（那还求啥玩意啊），它就得告诉你递推式。

我们以斐波那契数列为例吧： \(a_{0} = 1, a_{1}=1; \forall i>1,a_{i}=a_{i-1}+a_{i-2}\)

设其生成函数为 \(F(x)=\sum_{i=0}^{\infty}{a_{i}x^{i}}\) ，则：

\[ x \cdot F(x)=\sum_{i=0}^{\infty}a_ix^{i+1} \]

像处理等比数列一样，把 \(x \cdot F(x)\) 和\(F(x)\) 相加：

\[ \begin{aligned} x \cdot F(x) + F(x)&=a_0 + \sum_{i=1}^{\infty}a_ix^i+\sum_{i=0}^{\infty}a_ix^{i+1}\\ (x + 1) \cdot F(x)&=a_0+\sum_{i=0}^{\infty}a_{i+1}x^{i+1}+a_ix^{i+1}\\ &=a_0+\sum_{i=0}^{\infty}(a_{i+1}+a_i)x^{i+1}\\ &=a_0+\sum_{i=0}^{\infty}a_{i+2}x^{i+1}\\ &=a_0+\sum_{i=2}^{\infty}a_ix^{i-1} \end{aligned} \]

把无穷和用 \(F(x)\) 代换掉：

\[ (x + 1) \cdot F(x)=a_0+\frac{F(x)-a_0-a_1x}{x} \]

两边同乘 \(x\) ，移项，将 \(F(x)\) 解出：

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

这就是第一步：用类似等比数列的方法解出 \(F(x)\) 。当然方法不止一种，你也可以寻找 \(F(x),x \cdot F(x),x^2 \cdot F(x)\) 的关系。一般来说，如果 \(a_n+a_{n+1}+a_{n+2}+...+a_{n+k-1}=a_{n+k}\) ，我们就需要寻找 \(F(x),x \cdot F(x),...,x^k \cdot F(x)\) 的关系。

好，我们已经知道了斐波那契数列的生成函数。但是，只有形如 \(\sum_{i=0}^{\infty}f(i)x^i\) 的式子才能告诉我们 \(a_i\) 的通项公式： \(a_i=f(i)\) 。所以我们要把 \(F(x)\) 转化为无穷级数的形式。

主要有两部分：

1. 将 \(F(x)\) 分解成 \(\sum{\frac{1}{(a_ix+b_i)^k}}\) 的形式
2. 分别求出每一个 \(\frac{1}{(a_ix+b_i)^k}\) 的级数形式，然后，显然的，生成函数具有可加性，再得到 \(F(x)\) 的级数形式。

第一步考虑待定系数法，设有 \(a_1,b_1,a_2,b_2\) 使得：

\[ \frac{1}{a_1x+b_1} + \frac{1}{a_2x+b_2}=\frac{kx}{k(1-x-x^2)} \]

左边通分得：

\[ \begin{aligned} \frac{a_1x+b_1+a_2x+b_2}{(a_1x+b_1)(a_2x+b_2)}&=\frac{kx}{k(1-x-x^2)}\\ \frac{(a_1+a_2)x+b_1+b_2}{a_1a_2x^2+(a_1b_2+a_2b_1)x+b_1b_2}&=\frac{kx}{k(1-x-x^2)}\\ \therefore \begin{cases} a_1+a_2=k\\ b_1+b_2=0\\ a_1a_2=-k\\ a_1b_2+a_2b_1=-k\\ b_1b_2=k \end{cases} \end{aligned} \]

解得：

\[ \begin{cases} a_1=\frac{-\sqrt5-5}{2}\\ a_2=\frac{\sqrt5-5}{2}\\ b_1=\sqrt5\\ b_2=-\sqrt5\\ k=5 \end{cases} \]

注意进行分式的待定系数法时，设出了分子分母的比例系数 \(k\) ，得到一组特解。

回代可得：

\[ \frac{1}{\frac{-\sqrt5-5}{2}x+\sqrt5} + \frac{1}{\frac{\sqrt5-5}{2}x-\sqrt5}=\frac{x}{1-x-x^2} \]

第一步成功了。

接下来我们来看，对于简单的分式 \(\frac{1}{ax+b}\) ，如何求出其作为生成函数对应的序列。

考虑在权值相同，个数无限的题目下介绍的前置知识：

\[ \sum_{i=0}^{\infty}{x^{i}}=\frac{1}{1-x}(x < 1) \]

那么，我们有：

\[ \frac{1}{ax+b}=\frac{1}{b} \cdot \frac{1}{1-(-\frac{a}{b}x)}=\frac{1}{b}\cdot \sum_{i=0}^{\infty}{(-\frac{a}{b}x)^{i}} \]

将 \(a\) 和 \(b\) 的特殊值代入，就得到了斐波那契数列的生成函数：

\[ F(x)=\frac{1}{\sqrt5}\cdot \sum_{i=0}^{\infty}{(-\frac{\frac{-\sqrt5-5}{2}}{\sqrt5}x)^{i}} + \frac{1}{-\sqrt5}\cdot \sum_{i=0}^{\infty}{(-\frac{\frac{\sqrt5-5}{2}}{-\sqrt5}x)^{i}} \]

化简一下：

\[ F(x)=\frac{1}{\sqrt5}\sum_{i=0}^{\infty}{((\frac{1+\sqrt5}{2})^{i}} - (\frac{1-\sqrt5}{2})^{i})x^{i} \]

最终我们得到了最为熟悉的通项公式：

\[ a_n=n\text{次项的系数}=\frac{1}{\sqrt5}{((\frac{1+\sqrt5}{2})^n} - (\frac{1-\sqrt5}{2})^n) \]

总结一下，虽然看上去比较烦，但是每一步都是比较模板的：

• 用类似等比数列的方法解出 \(F(x)\) 。
• 用待定系数法将 \(F(x)\) 分解成 \(\sum{\frac{1}{(a_ix+b_i)^k}}\) 的形式
• 分别求出每一个 \(\frac{1}{(a_ix+b_i)^k}\) 的级数形式： \(\frac{1}{ax+b}=\frac{1}{b}\cdot \sum_{i=0}^{\infty}{(-\frac{a}{b}x)^{i}}\)