形式幂级数

定义

与多项式的联系

一个关于 $x$ 的多项式可以写作:

去掉项数的限制:

普通生成函数

对于一类无标号对象,使用普通生成函数:

指数生成函数

对于一类有标号对象,使用指数生成函数:

无标号是易于理解的,考虑有标号对象的合并:除以 $i!$ 不妨可以看作一次对于该对象内部元素的重标号,若要合并两个标号,则新的重标号方式为:

那么考虑一次卷积:

移项,发现其形式依然是:

组合生成函数

对于一类特殊的对象——一般是有编号有向图的计数题中出现——使用组合生成函数:

乘法逆元

定义

$x$ 是形式化的,对于形式幂级数求和时,默认 $x^{\infty}$ 趋近于 $0$ 。

例如:

借助二项式系数,或者考虑一些组合意义,有:

逆元的求法,本处不作赘述。

应用

例题1

有若干颜色不同的骨牌,其中大小为 $1\times i$ 的骨牌恰好有 $a_i$ 种,每种骨牌都能够无限使用,不重叠地铺满 $1\times n$ 的放个有几种方法?

$a_i, n \leq 10^5$

这是一道十分基础的生成函数题,答案显然为:

例题2

字符集大小为 $m$ ,给定一个长为 $k$ 的字符串 $s$ ,求所有长为 $n$ 的串中,不包含子串 $s$ 的有多少个?

$n, m, k \leq 10^5$

直接计数非常困难,需要二维表示状态,正难则反,尝试计算出所有的不合法串。

这时候需要设计一个状态,尽可能简单且能够转移,故令 $f_i$ 表示第一次匹配上 $s$ 的位置是 $[i - k + 1, i]$ 。

当 $i < k$ 时:

当 $i >= k$ 时:

集合 $C = {d \geq 0|s_{d + 1, k} = s_{1, k - d}}$。

第一项是全集;第二项是前面已经计算过的,第一次不在区间内的个数;第三次第一次匹配也在该区间内的,但是已经记入过答案。

$C$ 可以利用 $\mbox{KMP}$ 预处理出来,利用生成函数的思想优化之:

令 $g_n = m^n - \sum \limits_{i = 0}^{n}f_im_{i - j}$ ,有:

对数与指数

复合运算

对于 $A(x) = \sum \limits_{i \geq 0}a_ix^i, B(x) = \sum \limits_{i \geq 1}b_ix^i$ ,有:

显然可以整理为:

注意,此处 $B(x)$ 并无常数项,所以复合运算成立,反之不成立。

形式导数

对于 $A(x) = \sum \limits_{i \geq 0}a_ix^i$ ,其形式导数为:

基本求导法则对于形式导数依然成立。

对数函数

对于 $A(x) = \sum \limits_{i \geq 1}a_ix^i$ ,其对数函数等价于将给定级数与其对应的麦克劳林级数复合,即:

通过导数,有一种简单的计算方式:

给定 $A(x) = 1 + \sum \limits_{i \leq 1}a_ix^i$,令:

则:

$\ln$ 一般在已知不同集合个数,求不同元素个数时使用。

指数函数

对于 $A(x) = \sum \limits_{i \geq 1}a_ix^i$ ,其对数函数等价于将给定级数与其对应的麦克劳林级数复合,即:

定义:$B(x) = \exp(A(x))$ ,有:

利用牛顿迭代法求解。

$\exp$ 一般在已知不同元素个数,求不同集合个数时使用。

集合的计数

有标号集合的计数

集合内的元素没有顺序关系,所以有:

有标号环的计数

环内的元素旋转后相同会被认为相同,故:

应用

例题1

求出 $n$ 个顶点的连通无向图个数,顶点有编号,不允许重边和自环。

$n \leq 10^5$

设 $G$ 为所有简单无向图,则:

设 $C$ 为所有简单连通图,由于一个简单无向图可以看作若干个连通分量组成的集合,所以:

即:

有:

例题2

你有若干种不同的物品,其中体积为 $i$ 的物品有 $a_i$ 种,每种物品有无限个,求物品恰好装满总体积为 $n$ 的背包的方案数。

$a_i, n \leq 10^5$

有一个最基础的解法:

当然这在这里时不适用的,因为无标号集合中可能出现重复元素,而无法去重。

考虑对于每一个不同的体积写出其生成函数:

这里有一个启示:对于这种有求和式的计数题而言,更换求和方式不失为一种优秀的求解方式,而不是一味的尝试容斥。

对上式进行变换:

使用对数函数化乘为加:

$A(x^j)$ 只有 $\frac{n}{j}$ 项有用,故复杂度为调和级数:$O(n\log n)$ 。

此处的完全背包可以替换成 $01$ 背包,处理方式相同。

例题3

求包含 $n$ 个顶点的基环树个数。

$n \leq 10^5$

根据 $\mbox{Carley}$ 定理,设 $T(x)$ 为有根树数量的生成函数,有:

一棵基环树等价于若干棵树拼接在环上得到,故答案为:

例题4

给定集合 $S$ 和正整数 $n$,计算有多少个 $n$ 阶置换 $p$ ,满足 $p$ 分解后的每一个轮换的大小都在 $S$ 内。

$n\leq 10^5$

每一个轮换等价于一个圆排列的方案数,那么对于每一个 $k \in S$,都可以有:

一个置换就是若干个轮换的集合,于是有:

答案为: