生成函数 学习笔记

生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。

普通型生成函数 (OGF)

对于一个数列 $f_n$，定义它的普通型生成函数为 $F(x)$。则：

$$F(x) = \sum_{n \ge 0} f_nx^n$$

$$f_n = [x^n]F(x)$$

基本运算

$H(x) = F(x) \pm G(x)$

$$\left(\sum_{n \geq 0} f_{n} x^{n}\right) \pm\left(\sum_{n \geq 0} g_{n} x^{n}\right)=\sum_{n \geq 0}\left(f_{n} \pm g_{n}\right) x^{n}$$

$H(x) = c \times F(x)$

$$c \times\left(\sum_{n \geq 0} f_{n} x^{n}\right)=\sum_{n \geq 0} (c f_{n}) x^{n}$$

$H(x) = F(x)G(x)$

$$\left(\sum_{n \geq 0} f_{n} x^{n}\right)\left(\sum_{n \geq 0} g_{n} x^{n}\right)=\sum_{n \geq 0}\left(\sum_{i=0}^{n} f_{i} g_{n-i}\right) x^{n}$$

$H(x) = F(x-m)$

$$\sum_{n \ge m} f_{n-m} x^{n} = \sum_{n \ge 0}f_nx^{n+m}$$

$H(x) = F(x+m)$

$$\sum_{n \ge 0} f_{n+m}x^n = \frac{\sum_{n \ge 0} f_nx^n - \sum_{i=0}^{m-1} f_ix^i}{x^m}$$

$H(x) = F^{\prime}(x)$

$$\left(\sum_{n \geq 0} f_{n} x^{n}\right)^{\prime} = \sum_{n \ge 0} ((n+1)f_{n+1})x^n$$

$H(x) = \int F(x) \mathrm{d}x$

$$\int\left(\sum_{n \geq 0} f_{n} x^{n}\right) \mathrm{d} x=\sum_{n>0} \frac{f_{n-1}}{n} x^{n} +C$$

$H(x) = F(cx)$

$$\sum_{n \ge 0} f_n(cx)^n = \sum_{n \ge 0} (c^nf_n)x^n$$

常见 OGF

常见的 OGF 通常可以用一个更加简单的式子代替，这个式子被称为其闭形式。

$x^m$

$$\begin{aligned} \sum_{n \ge 0} [n = 0] x^n &= 1 \\\\ \sum_{n \ge 0} [n = m] x^n &= x^m \\\\ \end{aligned}$$

$(1 + x)^m$

$$\begin{aligned} \sum_{n \ge 0} x^n &= \frac 1{1 - x} \\\\ \sum_{n \ge 0} (n+1)x^n &= \frac 1{(1 - x)^2} \\\\ \sum_{n \ge 0} (-1)^n x^n &= \frac 1{1 + x} \\\\ \sum_{n \ge 0} \binom mn x^n &= (1 + x)^m \\\\ \sum_{n \ge 0} \binom {n+m-1}n x^n &= (1 - x)^{-m} \\\\ \end{aligned}$$

$e$ 相关

$$\begin{aligned} \sum_{n > 0} \frac{1}{n} x^n &= \ln\frac1{1-x} \\\\ \sum_{n > 0} \frac{-(-1)^n}{n} x^n &= \ln(1+x) \\\\ \sum_{n \ge 0} \frac{1}{n!} x^n &= e^x \\\\ \end{aligned}$$

一些 OGF

Fibonacci

$$f_n = \begin{cases} n & n \leq 1 \\\\ f_{n-1} + f_{n-2} & n > 1 \\\\ \end{cases}$$

---

$$\begin{aligned}F(x) &= \sum_{n \ge 0} f_n x^n \\\\&= x + \sum_{n > 0} (f_n + f_{n-1}) x^{n+1} \\\\&= x + xF(x) + x^2F(x) \\\\\end{aligned}$$

---

$$\begin{aligned} F(x) &= \frac x{1-x-x^2} \\\\ &= \frac{x}{(1-\frac{1-\sqrt5}{2}x)(1-\frac{1+\sqrt5}{2}x)} \\\\ &= \frac{\left(\frac{1}{1-\frac{1+\sqrt5}{2}x} - \frac{1}{1-\frac{1-\sqrt5}{2}x}\right)}{\sqrt5} \\\\ \end{aligned}$$

---

$$\begin{aligned} F(x) &= \sum_{n \ge 0} f_n x^n \\\\ f_n &= \frac{\left(\frac{1+\sqrt5}2\right)^n - \left(\frac{1-\sqrt5}2\right)^n}{\sqrt 5} \\\\ \end{aligned}$$

前缀和

$$s_n = \sum_{i=0}^n f_i$$

---

$$\begin{aligned} S(x) &= \sum_{n \ge 0} s_nx^n \\\\ &= \sum_{n \ge 0} \left(\sum_{i=0}^n f_i\right)x^n \\\\ &= \sum_{i \ge 0} \left(f_i \sum_{n \ge i} x^n\right) \\\\ &= \sum_{i \ge 0} \left(f_i \frac{x^i}{1-x}\right) \\\\ &= \frac{1}{1-x}\sum_{i \ge 0} f_ix^i \\\\ &= \frac{1}{1-x} F(x) \\\\ \end{aligned}$$

Catalan

$$c_n = \begin{cases} 1 & n = 0 \\\\ \sum_{i=0}^{n-1} c_ic_{n-i-1} & n > 0 \\\\ \end{cases}$$

---

$$\begin{aligned} C(x) &= \sum_{n \ge 0} c_nx^n \\\\ &= 1+\sum_{n \geq 1}\left(\sum_{i=0}^{n-1} c_{i} c_{n-i-1}\right) x^{n} \\\\ &= 1+x \sum_{m \geq 0}\left(\sum_{i=0}^{m} c_{i} c_{m-i}\right) x^{m} \\\\ &= 1 + xC^2(x) \end{aligned}$$

---

$$C(x)=\frac{1 - \sqrt{1-4 x}}{2 x}$$

---

$$\begin{aligned} \sqrt{1-4 x} &= (1-4 x)^{\frac 12} \\\\ &= \sum_{n \ge 0} \binom{\frac 12}n (-4x)^n \\\\ &= 1 + \sum_{n > 0}\frac{\left(\frac 12\right)^{\underline{n}}}{n!}(-4x)^n \\\\ &= 1 + \sum_{n > 0}\frac{(-1)^{n-1} (1 \times 3 \times \cdots \times (2n - 3))}{2^nn!}(-4x)^n \\\\ &= 1 + \sum_{n > 0}\frac{(-1)^{n-1} (2n-2)!}{2^nn!(2 \times 4 \times \cdots \times (2n-2))}(-4x)^n \\\\ &= 1 + \sum_{n > 0}\frac{(-1)^{n-1} (2n-2)!}{2^{2n-1}n!(n-1)!}(-4x)^n \\\\ &= 1 - 2\sum_{n > 0}\frac{(2n-2)!}{n!(n-1)!}x^n \\\\ \end{aligned}$$

---

$$\begin{aligned} C(x) &= \frac{1 - \sqrt{1-4 x}}{2 x} \\\\ &= \frac{1 - \left(1 - 2\sum_{n > 0}\frac{(2n-2)!}{n!(n-1)!}x^n\right)}{2 x} \\\\ &= \sum_{n \ge 0}\frac{(2n)!}{(n+1)!n!}x^n \\\\ &= \sum_{n \ge 0}\frac{\binom{2n}n}{n+1} x^n \\\\ \end{aligned}$$

应用

OGF 可以用来解决一些无标号组合计数问题。

用 $a_n$ 表示选 $n$ 件 A 物品的方案数，用 $b_n$ 表示选 $n$ 件 B 物品的方案数，用 $c_n$ 表示一共选 $n$ 件 A 或 B 物品的方案数，则有 $c_n = \sum_{i=0}^n a_ib_{n-i}$。

那么，换个写法就是：

$$C(x) = A(x)B(x)$$

【例题】P2000 拯救世界

把每条限制用一个生成函数表示，然后把这十个 OGF 相乘即可。

【例题】LOJ6268 分拆数

每一个正整数 $m$ 都对应着一个生成函数 $F_m(x) = \sum_{n \ge 0} x^{nm} = \frac{1}{1-x^m}$。

所以有：

$$F(x) = \prod_{n > 0} \frac{1}{1-x^n}$$

根据五边形数定理：

$$\begin{aligned} \prod_{n > 0} (1-x^n) &= \sum_{m \ge 0} (-1)^{m} x^{\frac{k(3 k \pm 1)}2} \\\\ &= 1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+\cdots \\\\ \end{aligned}$$

又有 $F(x) \prod_{n > 0} (1-x^n) = 1$：

$$F(x)-x F(x)-x^{2} F(x)+x^{5} F(x)+x^{7} F(x)-x^{12} F(x)-x^{15} F(x) + \cdots = 1$$

$$F(x) = 1+x F(x)+x^{2} F(x)-x^{5} F(x)-x^{7} F(x)+x^{12} F(x)+x^{15} F(x) - \cdots$$

则有：

$$f_{n}=[n=0]+f_{n-1}+f_{n-2}-f_{n-5}-f_{n-7}+f_{n-12}+f_{n-15} -\cdots$$

由于五边形数 $\frac{k(3 k \pm 1)}2$ 只有 $\mathcal O(\sqrt n)$ 个，因此可以 $\mathcal O(n \sqrt n)$ 解决此问题。

指数型生成函数 (EGF)

对于一个数列 $f_n$，定义它的指数型生成函数为 $F(x)$。则： $$F(x) = \sum_{n \ge 0} \frac{f_n}{n!}x^n$$

OGF 可以用来解决一些无标号组合计数问题，相对地 EGF 可以用来解决一些有标号排列计数问题。原理是在有标号的情况下，每次先除掉 $n!$ 使其变成无标号，所有 EGF 相乘之后再乘上 $n!$ 即可变成有标号，本质上是一个多重组合数。

基本运算

$H(x) = F(x)G(x)$

$$\left(\sum_{n \geq 0} \frac {f_{n}}{n!} x^{n}\right)\left(\sum_{n \geq 0} \frac{g_{n}}{n!} x^{n}\right)=\sum_{n \geq 0}\left(\sum_{i=0}^{n} \frac{f_{i} g_{n-i}}{n!}\right) x^{n} = \sum_{n \geq 0} \frac{\sum_{i=0}^{n} f_{i} g_{n-i}}{n!}x^{n}$$

常见 EGF

$e$ 相关

$$\begin{aligned} \sum_{n \ge 0} \frac{1}{n!} x^n &= e^x \\\\ \sum_{n \ge 0} [n \bmod 2 = 0] \frac1{n!}x^n &= \frac{e^x + e^{-x}}{2} \\\\ \sum_{n \ge 0} [n \bmod 2 = 1] \frac1{n!}x^n &= \frac{e^x - e^{-x}}{2} \end{aligned}$$

一些 EGF

排列

$$\sum_{n \ge 0} \frac{n!}{n!} x^n = \frac{1}{1-x}$$

圆排列

$$\sum_{n > 0} \frac{(n-1)!}{n!} x^n = \sum_{n>0} \frac{1}{n}x^n = \ln\frac1{1-x}$$

注意到 $e^{\ln\frac1{1-x}} = \frac1{1-x}$，发现排列和圆排列之间有关联。

集合 EGF

若一个集合 $A$ 是由若干个集合 $B$ 组合而成的，那么 $A(x) = e^{B(x)}$，其中 $A(x),B(x)$ 分别为 $A,B$ 的 EGF。

排列（置换）正是由若干个圆排列（轮换）组合而成的，因此有上面的关联。

错位排列

错位排列实际上就是去掉大小为 $1$ 的圆排列后再进行组合。 $$e^{\ln \frac1{1-x} - x} = \frac{e^{-x}}{1-x}$$

有标号无向连通图（无重边无自环）

有标号无向图： $$\sum_{n \ge 0} 2^{\binom{n}{2}} x^n$$ 有标号无向图可以看成有标号无向连通图组合而成的，因此后者的 EGF 为： $$\ln \left(\sum_{n \ge 0} 2^{\binom{n}{2}} x^n \right)$$

参考资料

• _rqy 铃悬的数学小讲堂——生成函数初步
• _rqy 生成函数简介
• 胡小兔 趣谈生成函数 =v=
• LuYouQi233 洛谷2000：拯救世界——题解
• 罗煜楚 《生成函数》课件
• 翁文涛 《多项式与生成函数》课件