生成函数 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-03-27 20:50

Visits: 1799

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

普通型生成函数 (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)
$$

参考资料

4条评论
  • EncodeTalker

    2020年3月30日 下午9:50

    您好!请问一下为什么$\frac{1}{(1-x)^2}=\sum_{n\geq 0}nx^n$呢?我推出来的是$\frac{1}{(1-x)^2}=\sum_{n\geq 0}(n+1)x^n$.

    1. xht37

      2020年3月30日 下午11:02

      抱歉写错了,已更正,感谢指出。

      1. EncodeTalker

        2020年3月30日 下午11:40

        以及在Fibonacci的生成函数的推导过程中貌似也有一些问题?$F(x)$前所乘的$x$的次数貌似不大对得上。

        1. xht37

          2020年3月31日 下午4:07

          已更正,再次感谢。

发表评论

电子邮件地址不会被公开。 必填项已用*标注