生成函数学习笔记

幂级数

定义

定义一个 形式幂级数 （以下简称幂级数） 为形如

\[a_0 + a_1 x^1 + a_2 x^2 + \ldots \]

的表达式，其中 \(a_n\) 是具体的数，而 \(x\) 是一个形式符号。序列 \(\{a_n\}\) 为其系数序列，称两个幂级数相等当且仅当它们的系数序列相同。

为简便，一般记 \([x^n]f(x)\) 表示幂级数 \(f(x) = \sum_{n \geq 0} a_n x^n\) 的 \(n\) 次项系数 \(a_n\) 。

多项式可被视为一个特殊的幂级数：它的幂级数从某一项开始都为 \(0\)。

四则运算

与普通多项式运算法则相同。

\[\sum_{n \geq 0} a_n x^n \pm \sum_{n \geq 0} b_n x^n = \sum_{n \geq 0} (a_n \pm b_n) x^n \]

\[\sum_{n \geq 0} a_n x^n \times \sum_{n \geq 0} b_n x^n = \sum_{n \geq 0} c_n x^n, c_n = \sum_{k=0}^{n}a_k b_{n-k} \]

可以验证，幂级数仍然满足常见的实数域运算律。

定义一个幂级数 \(f\) 的逆元为 \(f^{-1}\) ，即满足 \(fg = 1\) 的 \(g\)。定义幂级数的除法 \(\dfrac{f}{g} = f g^{-1}\) 。

可以证明，若 \(f\) 的 \(0\) 次项为 \(0\) ，则 \(f\) 不存在逆元，否则 \(f\) 的逆元 \(f^{-1}\) 存在且唯一。

例如

\[(1 + x + x^2 + \ldots)(1 - x) = 1 \]

\[(1 + x + x^2 + \ldots) = (1 - x)^{-1} \]

基本运算

幂级数的级数

考虑对幂级数进行无限求和，即 \(\sum_{i \geq 0} f_i(x)\)，其中每个 \(f_i(x)\) 都为一个幂级数。

当 \(f_i(x)\) 的最低次项严格递增时，\(\sum_{i \geq 0} f_i(x)\) 有定义。

幂级数的复合

设 \(f,g\) 为幂级数，满足 \(f\) 是多项式或 \(g(0) = 0\) （即 \([x^0]g(x) = 0\)），定义 \(f,g\) 的复合 \(f(g(x))\) 为

\[f(g(x)) = \sum_{n \geq 0} f_n g(x)^n \]

当 \(f\) 为多项式时，这是有限个幂级数求和；当 \(g(0) = 0\) 时， \(g(x)^n\) 的最低次项为 \(n\)。

幂级数的 ln 与 exp

\(exp(x),ln(1+x)\) 为两个幂级数，定义为：

\[e^x = \exp(x) = \sum_{n \geq 0} \dfrac{1}{n!} x^n = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \ldots \]

\[\ln(1+x) = \sum_{n \geq 1} \dfrac{(-1)^{n+1}}{n} x^n = x - \dfrac{x^2}{2!} + \dfrac{x^3}{3!} - \ldots \]

可以验证：\(\exp(\ln(f(x))) = f(x)\) （\(f(0) = 1\)），\(\ln(\exp(f(x))) = f(x)\) （\(f(0) = 0\)）；实数域上 ln 和 exp 的运算规律仍然满足。

普通生成函数（OGF）

定义

定义序列 \(a\) 的 普通生成函数（OGF） \(f(x)\) 为幂级数

\[f(x) = \sum_{n \geq 0} a_n x^n \]

两个数列相加减，它们的 OGF 相加减；
两个数列做卷积，它们的 OGF 相乘。

封闭形式

使用生成函数时，一般会化成封闭形式以便更好化简。

例如：\(\langle 1,1,1,\ldots \rangle\) 的 OGF \(f(x) = \sum_{n \geq 0} x^n\) ，注意到 \(f(x) = x f(x) + 1\)，解该方程，得

\[f(x) = \dfrac{1}{1-x} \]

这就是 \(f(x) = \sum_{n \geq 0} x^n\) 的封闭形式。

一些常见的数列的生成函数：

• \[a = \langle 1,1,1,\ldots \rangle , f(x) = \sum_{n \geq 0} x^n = \dfrac{1}{1-x} \]

• \[a = \langle 1,0,1,0,1,0, \ldots \rangle , f(x) = \sum_{n \geq 0} x^{2n} = \dfrac{1}{1-x^2} \]

• \[a = \langle 1,2,3,4, \ldots \rangle , f(x) = \sum_{n \geq 0} (n+1) x^n = \dfrac{1}{(1-x)^2} \]

• \[a = \langle 1,p,p^2,p^3, \ldots \rangle , f(x) = \sum_{n \geq 0} p^n x^n = \dfrac{1}{1-px} \]

• \[a_n = {m \choose n} , f(x) = \sum_{n \geq 0} {m \choose n} x^n = (1+x)^m \]

• \[a_n = {m+n \choose n} , f(x) = \sum_{n \geq 0} {m+n \choose n} x^n = \dfrac{1}{(1-x)^{m+1}} \]

求解线性递推

例：已知 \(a_0,a_1\) 为常数，\(a_n = 2a_{n-1} + 3a_{n-2}\) ，求 \(a\) 的通项公式。

解：设 \(a\) 的 OGF 为 \(f(x) = \sum_{n \geq 0} a_n x^n\)，则：

\[ \begin{aligned} f(x)=&\sum_{n \geq 0} a_n x^n \\ =& a_0 + a_1 x + \sum_{n \geq 2} a_n x^n \\ =& a_0 + a_1 x + \sum_{n \geq 2}(2a_{n-1} + 3a_{n-2}) x^n \\ =& a_0 + a_1 x + 2x \sum_{n \geq 1}a_{n} x^n + 3x^2 \sum_{n \geq 0}a_{n} x^n\\ =& a_0 + a_1 x + 2x (f(x) - a_0) + 3x^2 f(x)\\ \end{aligned} \]

解得

\[f(x) = \dfrac{a_0 + (a_1 - 2a_0)x}{1 - 2x - 3x^2} = \dfrac{a_0 + (a_1 - 2a_0)x}{(1+x)(1-3x)} \]

不妨设

\[f(x) = \dfrac{A}{1+x} + \dfrac{B}{1-3x} \]

其中 \(A,B\) 不难由通过比较系数求得。

又因为

\[\frac{1}{1+x} = \frac{1}{1- (-x)} = 1 - x + x^2 - x^3 + \ldots \]

\[\frac{1}{1-3x} = \frac{1}{1- (3x)} = 1 + 3x + 9x^2 + 27x^3 + \ldots \]

因此 \([x^n]f(x) = A \times (-1)^n + B \times 3^n\) 。

对于任意多项式 \(F(x),G(x)\)，都可以用类似上面的方法求出生成函数 \(\dfrac{F(x)}{G(x)}\) 的展开式，实际运用中，一般先求出 \(G(x)\) 的根，将分母表示成 \(\prod (1 - p_ix)^{d_i}\) 的形式，然后求比较系数求分子，特别地，若 \(G(x)\) 存在重根，则每有一个重根则需多设一个分式。

例题

抽奖机

有一个抽奖机。当按下按钮时，抽奖机有 \(p\) 的概率掉出一个盲盒，\(1 − p\) 的概率关机。每个盲盒有一半的概率有奖品，一半的概率为空盲盒。
小 A 现在不断地按下按钮直到抽奖机关机。对 \(0\leq k \leq K\) 求出小 A 最后恰好得到 \(k\) 个奖品的概率。 \(K \leq 10^5\)。

---

抽到 \(k\) 个奖品的概率即为：

\[ \begin{aligned} &\sum_{i \geq 0} \dfrac{ p^i (1-p) {i \choose k} }{2^i} \\ =& (1-p) \sum_{i \geq 0} (\dfrac{p}{2})^i {i \choose k} \\ =& (1-p) \sum_{i \geq 0} (\dfrac{p}{2})^i [x^k] (1+x)^i \\ =& (1-p)[x^k] \sum_{i \geq 0} (\dfrac{p}{2}(1+x))^i \\ =& (1-p)[x^k] \dfrac{1}{1-\frac{p}{2}(1+x)} \\ =& (1-p)[x^k] \dfrac{1}{1-\frac{p}{2}-\frac{px}{2}} \\ =& \dfrac{1-p}{1-\frac{p}{2}}[x^k] \dfrac{1}{1-\frac{\frac{p}{2}}{1-\frac{p}{2}}x} \\ =& \dfrac{1-p}{1-\frac{p}{2}} (\dfrac{\frac{p}{2}}{1-\frac{p}{2}})^k \\ \end{aligned} \]

P10780 食物

• 承德汉堡：偶数个；
• 可乐：\(0\) 个或 \(1\) 个；
• 鸡腿：\(0\) 个，\(1\) 个或 \(2\) 个；
• 蜜桃多：奇数个；
• 鸡块：\(4\) 的倍数个；
• 包子：\(0\) 个，\(1\) 个，\(2\) 个或 \(3\) 个；
• 土豆片炒肉：不超过一个；
• 面包：\(3\) 的倍数个；

计算携带 \(n\) 件物品的方案数，并对 \(10007\) 取模。\(1\leq n\leq 10^{500}\)；

---

首先计算每种食物的生成函数：

• 承德汉堡：\(1+x^2+x^4 + \ldots = \dfrac{1}{1-x^2}\)
• 可乐：\(1+x\)
• 鸡腿：\(1+x+x^2 = \dfrac{1-x^3}{1-x}\)
• 蜜桃多 \(x+x^3+x^5 + \ldots = \dfrac{x}{1-x^2}\)
• 鸡块：\(1+x^4+x^8+\ldots = \dfrac{1}{1-x^4}\)；
• 包子：\(1+x+x^2+x^3 = \dfrac{1-x^4}{1-x}\)
• 土豆片炒肉：\(1+x\)
• 面包：\(1+x^3+x^6+ \ldots = \dfrac{1}{1-x^3}\)

把这一堆东西乘起来，得到总的生成函数 \(f(x) = \dfrac{x}{(1-x)^4} = \sum_{n \geq 0} {n+4-1 \choose n} x^{n+1}\) 。

因此 \([x^n]f(x) = {(n-1)+4-1 \choose (n-1)} = {n+2 \choose 3}\) 。

整数拆分问题

设 \(p_n\) 表示将正整数 \(n\) 拆成若干个可以相同的正整数之和的方案数（只关心每个数出现的次数，不关心顺序），求 \(p_1,p_2,\ldots,p_n\)。\(n \leq 10^5\)。

---

不加证明地，我们给出五边形数定理：

\[\prod_{i \geq 1} (1-x^i) = \sum_{k = - \infty}^{ \infty} (-1)^k x^{\frac{k(3k + 1)}{2}} = 1 + \sum_{k \geq 1} (-1)^k x^{\frac{k(3k \pm 1)}{2}} \]

其中，形如 $ \dfrac{k(3k \pm 1)}{2}$ 的数被称为广义五边形数。

不难看出，在 \(\prod_{i \geq 1} (1-x^i)\) 的系数序列前 \(n\) 项中，仅有 \(\Theta(\sqrt{n})\) 项非零。

设 \(f(x) = \sum_{n \geq 0} p_nx^n\)，则

\[f(x) = \prod_{i \geq 1}(1+x^i+x^{2i}+ \ldots) = \prod_{i \geq 1} \dfrac{1}{1-x^i} \]

因此 $f(x)\prod_{i \geq 1}(1-x^i) = f(x) (1 + \sum_{k \geq 1} (-1)^k x^{\frac{k(3k \pm 1)}{2}}) = 1 $ 。即

\[(1 - x - x^2 +x^5 +x^7 - x^{12} - x^{15} + \ldots)(1+p_1x^1+p_2x^2+\ldots) = 1 \]

通过展开并比较 \(x^n\) 的系数，可得 $p_n - p_{n-1} - p_{n-2} + p_{n-5} + p_{n-7} - \ldots = 0 $。

又由于广义五边形数是 \(\Theta(\sqrt{n})\) 的，因此求出前 \(n\) 项的总时间复杂度为 \(\Theta(n \sqrt{n})\) 。

区间背包/可回退背包

有 \(n\) 个物品，第 \(i\) 个物品的重量为 \(w_i\)。有两个指针 \(1 \leq l \leq r \leq n\)。你要维护两种操作：

• 移动 \(l\) 或 \(r\) 指针一步。
• 问 \([l,r]\) 之间的物品是否能凑出重量 \(s\)。
  $ n, q \leq 2 \times 10^5 $ ，\(s,w_i \leq W = 100\)。

---

首先，每个背包都可以被视为一个 OGF，在 OGF 的角度上，本题即为要求维护 $f(x) = \prod_{i=l}^{r} (1 +x^{w_i}) $ 的前 \(W\) 位。

加入物品 \(i\)，可以视为乘上一个 \(1+ x^{w_i}\)，反过来，移除物品 \(i\) 即为除掉 \(1+ x^{w_i}\) 。注意到运算时 \(1+ x^{w_i}\) 只有 \(2\) 位，而又只需要求出多项式的前 \(W\) 位信息，因此都可以做到 \(\Theta(W)\)。

指数生成函数（EGF）

定义

定义序列 \(a\) 的 指数生成函数（EGF） \(\hat{f}(x)\) 为幂级数

\[\hat{f}(x) = \sum_{n \geq 0} a_n \dfrac{x^n}{n!} \]

两个数列相加减，它们的 EGF 相加减；

两个数列做如下卷积：

\[c_n = \sum_{i=0}^{n} {n \choose i} a_i b_{n-i} \]

，则 \(c\) 的 EGF 是 \(a,b\) 的 EGF 的乘积。

无序组合与有序组合

无序组合

对于 A，B 两类物品，从中选出若干个物品，定义一种方案的权值是选出的所有物品权值乘积。对于每个 \(n\)，求选 \(n\) 个物品的所有方案权值和。

假设已经求出了 \(a_i\) 表示从 A 中选 \(i\) 个物品的所有方案权值和，\(b_j\) 表示从 B 中选 \(j\) 个物品的所有方案权值和。

此时， \(ans_n = \sum_{i=0}^n a_i b_{n-i}\)。因此 \(ans\) 的 OGF 为 \(a,b\) 的 \(OGF\) 的乘积：

\[\sum_{n \geq 0} ans_n x^n = (\sum_{i \geq 0} a_i x^i)(\sum_{j \geq 0} b_j x^j) \]

有序组合

对于 A，B 两类物品，从中选出若干个物品并安排顺序，定义一种方案的权值是选出的所有物品权值乘积。对于每个 \(n\)，求选 \(n\) 个物品并安排顺序的所有方案权值和。

假设已经求出了 \(a_i\) 表示从 A 中选 \(i\) 个物品并安排顺序的所有方案权值和，\(b_j\) 表示从 B 中选 \(j\) 个物品并安排顺序的所有方案权值和。

此时， \(ans_n = \sum_{i=0}^n {i\choose n} a_i b_{n-i}\)。因此 \(ans\) 的 EGF 为 \(a,b\) 的 \(EGF\) 的乘积：

\[\sum_{n \geq 0} \dfrac{ans_n}{n!} x^n = (\sum_{i \geq 0} \dfrac{a_i}{i!} x^i)(\sum_{j \geq 0} \dfrac{b_j}{j!} x^j) \]

---

类似地，若有 \(k\) 类物品，情况类似。

若选出若干物品，则

\[ans_n = \sum_{i_1,i_2,\dots,i_k \geq 0,i_1 + i_2 + \dots + i_k = n} \prod_{j=1}^{k} a_{j,i_j} \]

对应 OGF 的乘积。

若选出若干物品并安排顺序，则

\[ans_n = \sum_{i_1,i_2,\dots,i_k \geq 0,i_1 + i_2 + \dots + i_k = n} {n\choose i_1,i_2,\dots,i_k} \prod_{j=1}^{k} a_{j,i_j} \]

对应 EGF 的乘积。

分组模型

有 \(n\) 个不同的元素，要将它们分到 \(k\) 个不同的组中。如果当第 \(j\) 个组分到 \(i_j\) 个元素时，会有贡献 \(a_{j,i_j}\)，而一种分组方案的贡献是每个组的贡献乘积，那么所有分组方案的贡献和为

\[\sum_{i_1,i_2,\dots,i_k \geq 0,i_1 + i_2 + \dots + i_k = n} {n\choose i_1,i_2,\dots,i_k} \prod_{j=1}^{k} a_{j,i_j} \]

这与刚刚有序组合问题的答案相一致，因此，该问题同样可看作 \(k\) 个组的 EGF 相乘再取 \(n\) 次项系数。

特别地，如果组的数量不再给定，而是任意；忽略组的编号，只关心两个元素是否在同一个组；每个组的 EGF 都相同，记为 \(\hat{A}(x)\)，那么所求即为

\[\sum_{k \geq 0} \dfrac{\hat{A}(x)^k}{k!} = \exp(\hat{A}(x)) \]

例题

有标号生成树计数

给定一个森林，由 \(k\) 个大小分别为 \(s_{1},s_{2},\ldots, s_k\) 的树构成，再连 \(k − 1\) 条边整张图连成一棵树，求能得到多少棵不同的有标号树。

前置知识：prufer 序列。
所有点集为 \(\{1,2,\ldots,n\}\) 的树与所有长度为 \(n − 2\)、值域为 \(\{1,2,\ldots,n\}\) 的数列一一对应。所以总共有 \(n^{n−2}\) 棵大小为 \(n\) 的有标号生成树。
我们将一棵树对应的数列称为该树的 prufer 序列。如果一个点在树上的度数为 \(d\)，那么它在 prufer 序列中出现 \(d − 1\) 次。

---

考虑将每个连通块当成一个大点，那么需要连 \(k − 1\) 条边让这 \(k\) 个大点构成一棵树，这 \(k\) 个大点构成的树会对应一个长度为 \(k − 2\),值域为 \([1, k]\) 的 prufer 序列。如果这个 prufer 序列确定了，连边的方案数就是 \(\prod_{i=1}^{k} s_i^{d_i}\) ，其中 \(d_i\) 为第 \(i\) 个大点的度数（即 prufer 序列中出现的次数加一）。这相当于将 prufer 序列上的每一个位置分配一个连通块，此时，若第 \(i\) 个连通块被分配给了 \(x\) 个位置，那么贡献会乘上 \(s_i^{x+1}\)。

不难发现这即为分组模型一，因此结果即为所有连通块的 EGF 之积：

\[ \begin{aligned} &(k-2)! [x^{k-2}] \prod_{i=1}^k \sum_{j \geq 0} \dfrac{s_i^{j+1}}{j!} x^j \\ =& (k-2)! [x^{k-2}] \prod_{i=1}^k s_i \exp(s_ix) \\ =& (k-2)! \prod_{i=1}^k s_i [x^{k-2}] \exp(\sum_{i=1}^k s_i x) \\ =& \prod_{i=1}^k s_i (\sum_{i=1}^k s_i)^{k-2} \\ \end{aligned} \]

该结论也被称为扩展 Cayley 公式。

错排数计数

求 $\forall i \in [1,n],p_i \neq i $ 的长度为 \(n\) 的排列数。

---

排列可以被视为若干个置换环，错排则可以被视为若干个大小不为 \(1\) 的置换环。原问题即可看作将 \(1,2,\ldots,n\) 分成若干个环，每个环的大小 \(i\) 满足 \(i \geq 2\)，贡献为 $(i-1)! $（环内圆排列方案数），由此可得，一个这样的环的 EGF 为

\[\hat{f}(x) = \sum_{i \geq 2} \dfrac{(i-1)!}{i!} x^i = \sum_{i \geq 2} \dfrac{x^i}{i} = -\ln(1-x)-x \]

可以发现，此时我们的问题与分组模型二相似，因此错排的 EGF 即为

\[\exp(-\ln(1-x)-x) = \dfrac{e^{-x}}{1-x} = (\sum_{n \geq 0} \dfrac{(-1)^n}{n!}x^n)(\sum_{n \geq 0} x^n) \]

UVA1305 Chocolate

有一个长度为 \(n\) 的数列 \(a\)，每一位都在 \({1,2,\ldots,c}\) 里均匀随机生成，问有多少个可能的 \(a\)，使得恰好有 \(m\) 个 \(x\) 满足 \(x\) 在数列中出现奇数次。\(n,m \leq 10^6,c \leq 10\) 。

---

显然可以令 \(m \gets \min(n,c)\) 。考虑每种颜色对应的 EGF，若它出现奇数次，则它的 EGF

\[\hat{f}(x) = x + \dfrac{x^3}{3!} + \dfrac{x^5}{5!} + \ldots = \dfrac{e^x - e^{-x}}{2} \]

若它出现偶数次，则它的 EGF

\[\hat{g}(x) = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \ldots = \dfrac{e^x + e^{-x}}{2} \]

最终答案即为 \(n! {c \choose m} [x^n](\dfrac{e^x - e^{-x}}{2})^m (\dfrac{e^x + e^{-x}}{2})^{c-m}\) 。

又因为

\[ \begin{aligned} &[x^n](\dfrac{e^x - e^{-x}}{2})^m (\dfrac{e^x + e^{-x}}{2})^{c-m}\\ =& [x^n] 2^{-c} (\sum_{i=0}^{m} (-1)^i {m \choose i} e^{m-2i}x)(\sum_{i=0}^{c-m}{c-m \choose i} e^{c-m-2i}x) \\ =& [x^n] 2^{-c} \sum_{i=0}^{m} \sum_{j=0}^{c-m} (-1)^i {m \choose i} {c-m \choose j} e^{c-2i-2j}x \\ =& [x^n] 2^{-c} \sum_{i=0}^{m} \sum_{j=0}^{c-m} (-1)^i {m \choose i} {c-m \choose j} ( \sum_{k \geq 0}\dfrac{((c-2i-2j)x)^k}{k!} ) \\ =& 2^{-c} \sum_{i=0}^{m} \sum_{j=0}^{c-m} (-1)^i {m \choose i} {c-m \choose j} \dfrac{(c-2i-2j)^n}{n!} \end{aligned} \]

因此，最终答案为 $n! {c \choose m} 2^{-c} \sum_{i=0}^{m} \sum_{j=0}^{c-m} (-1)^i {m \choose i} {c-m \choose j} \dfrac{(c-2i-2j)^n}{n!} $ 。