这里会显示出您选择的修订版和当前版本之间的差别。
后一修订版 | 前一修订版 | ||
2020-2021:teams:i_dont_know_png:nikkukun:generating-function [2020/08/07 18:07] nikkukun 创建 |
2020-2021:teams:i_dont_know_png:nikkukun:generating-function [2020/08/07 19:45] (当前版本) nikkukun add some contents |
||
---|---|---|---|
行 5: | 行 5: | ||
常见的生成函数形式: | 常见的生成函数形式: | ||
- | * 普通型生成函数:$f(x) = \sum_{i=0}^{\infty} a_i x^i$ | + | * 普通型生成函数(Ordinary Generating Function, OGF):$F(x) = \sum_{i=0}^{\infty} a_i x^i$ |
- | * 指数型生成函数:$f(x) = \sum_{i=0}^{\infty} \dfrac {a_i}{i!} x^i$ | + | * 指数型生成函数(Exponential Generating Function, EGF):$F(x) = \sum_{i=0}^{\infty} \dfrac {a_i}{i!} x^i$ |
+ | |||
+ | |||
+ | OGF 的卷积表示组合,而 EGF 的卷积表示排列——之前没怎么理解这个说法,现在就比较明白了。考虑卷积结果的某一项 $x^n$: | ||
+ | |||
+ | * 对 OGF 卷积 $F(x) = \prod_{i=1}^m F_i(x)$,我们只关注每种 $F_i(x)$ 性质的东西占了 $n$ 个物品中的多少,而不关注具体是哪几个物品,因此说是组合; | ||
+ | * 对 EGF 卷积 $G(x) = \prod_{i=1}^m G_i(x)$,我们用组合数钦定了每种 $G_i(x)$ 性质的东西分别是 $n$ 个物品的哪几个,相当于 OGF 卷积中给选中的物品钦定编号,因此说是排列。 | ||
行 13: | 行 19: | ||
===== 普通型生成函数 ===== | ===== 普通型生成函数 ===== | ||
- | 形式幂级数 $\sum_{i = 0} ^ {\infty} a^i x^i = \frac 1 {1 - ax}$ 并不太关注 $x$ 的取值是否使得式子收敛。给出一些常用生成函数的封闭形式: | + | 形式幂级数 $\sum_{i = 0} ^ {\infty} a^i x^i = \dfrac 1 {1 - ax}$ 并不太关注 $x$ 的取值是否使得式子收敛。给出一些常用 OGF 的封闭形式: |
* 完全背包生成函数 | * 完全背包生成函数 | ||
$$ | $$ | ||
- | \sum _{i=0} ^{\infty} x^{ai} = \frac 1{1-x^a} | + | \sum _{i=0} ^{\infty} x^{ai} = \dfrac 1{1-x^a} |
$$ | $$ | ||
行 24: | 行 30: | ||
$$ | $$ | ||
- | \sum _{i=0} ^{\infty} a^i x^i = \frac 1{1-ax} | + | \sum _{i=0} ^{\infty} a^i x^i = \dfrac 1{1-ax} |
$$ | $$ | ||
行 36: | 行 42: | ||
$$ | $$ | ||
- | \sum _{i=0} ^{\infty} \binom{n+i-1}{i}x^i = \frac {1}{(1-x)^n} | + | \sum _{i=0} ^{\infty} \binom{n+i-1}{i}x^i = \dfrac {1}{(1-x)^n} |
$$ | $$ | ||
行 46: | 行 52: | ||
$$ | $$ | ||
- | \sum _{i=0} ^n x^{ai} = \frac {1-(x^a)^{n+1}}{1-x^a} | + | \sum _{i=0} ^n x^{ai} = \dfrac {1-(x^a)^{n+1}}{1-x^a} |
$$ | $$ | ||
行 59: | 行 65: | ||
$$ | $$ | ||
- | \sum _{i=0} ^{\infty} \frac {x^{2i}}{(2i)!} = \frac {\mathrm{e}^x + \mathrm{e}^{-x}}2 | + | \sum _{i=0} ^{\infty} \dfrac {x^{2i}}{(2i)!} = \dfrac {\mathrm{e}^x + \mathrm{e}^{-x}}2 |
$$ | $$ | ||
$$ | $$ | ||
- | \sum _{i=0} ^{\infty} \frac {x^{2i+1}}{(2i+1)!} = \frac {\mathrm{e}^x - \mathrm{e}^{-x}}2 | + | \sum _{i=0} ^{\infty} \dfrac {x^{2i+1}}{(2i+1)!} = \dfrac {\mathrm{e}^x - \mathrm{e}^{-x}}2 |
$$ | $$ | ||
行 69: | 行 75: | ||
$$ | $$ | ||
- | \mathrm{e}^{ax} = \sum _{i=0} ^{\infty} \frac {a^i x^i}{i!} | + | \mathrm{e}^{ax} = \sum _{i=0} ^{\infty} \dfrac {a^i x^i}{i!} |
$$ | $$ | ||
行 78: | 行 84: | ||
==== 指数型生成函数与集合划分 ==== | ==== 指数型生成函数与集合划分 ==== | ||
- | 考虑一些具有性质 $A$ 的东西的指数型生成函数 $F(x)$,现在把 $A$ 里面的东西当成基本元素,像选物品一样合在一起获得具有 $B$ 性质的东西(也就是 $B$ 是几个 $A$ 属性的东西拼成的),且 $B$ 的生成函数是 $G(x)$,则 | + | 考虑一些具有性质 $A$ 的东西的指数型生成函数 $F(x)$,现在把 $A$ 里面的东西当成基本元素,像选物品一样合在一起获得具有 $B$ 性质的东西(也就是 $B$ 由几个 $A$ 属性的东西拼成,同时把这几个东西看做是无序的),且 $B$ 的生成函数是 $G(x)$,则 |
$$ | $$ | ||
行 84: | 行 90: | ||
$$ | $$ | ||
- | **例子 1** 令 $F(x)$ 为 $n$ 个点的无向连通图个数,$G(x)$ 为 $n$ 个点的**任意图**数量(且显然 $G(x) = \sum _{i=0}^{\infty} 2^{i(i-1)/2}x^i$),因此 $F(x) = \ln G(x)$。 | + | 利用该性质可以极大化简某些过程。 |
- | **例子 2** 令 $F(x)$ 为 $n$ 个点的连通 DAG 个数,$G(x)$ 为**不要求连通**的 $n$ 个点的 DAG 个数,显然这也同样满足集合划分要求。一个小证明:$G(x)$ 是 $F(x)$ 的一个划分,因此对 $G(x)$ 枚举它由几个 $F(x)$ 构成,即 | + | |
+ | |||
+ | |||
+ | **例子 1** [[https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%95%B0 | 贝尔数]] $B_n$ 表示将大小为 $n$ 的集合划分为非空集合的方案数。令 $G(x) = \sum_{i=1}^{\infty} \dfrac {x^i}{i!} = \mathrm{e}^x - 1$,则 $G(x)$ 的 $n$ 次项系数表示“选 $n$ 个数组成一个非空集合的方案数”。显然大小为 $n$ 的集合的一个划分中,每个子集都具有相同的性质(都来自 $G(x)$ 的某一项),因此有贝尔数生成函数 $F(x) = \mathrm{e}^{G(x)} = \mathrm{e}^{\mathrm{e}^x - 1}$。 | ||
+ | |||
+ | 另一种理解方式是,若 $n$ 由 $k$ 个子集构成,则 $G^k(x)$ 的 $n$ 次项系数对应了上述的方案数,而这 $k$ 个集合应当无序,故要乘 $\dfrac 1{k!}$,最终有 | ||
$$ | $$ | ||
\begin{aligned} | \begin{aligned} | ||
- | G(x) &= \sum _{i=0} ^{\infty} \frac {F^i(x)}{i!} \\ | + | F(x) |
- | &= \mathrm{e}^{F(x)} | + | &= \sum_{k=0}^{\infty} \dfrac {G^k(x)}{k!} \\ |
+ | &= \mathrm{e}^{G(x)} | ||
\end{aligned} | \end{aligned} | ||
$$ | $$ | ||
- | 利用该性质可以极大化简某些过程。 | ||
+ | |||
+ | **例子 2** 令 $F(x)$ 为 $n$ 个点的无向连通图个数,$G(x)$ 为 $n$ 个点的**任意图**数量(且显然 $G(x) = \sum _{i=0}^{\infty} 2^{i(i-1)/2}x^i$),因此 $F(x) = \ln G(x)$。 | ||
+ | |||
+ | |||
+ | |||
+ | **例子 3** 令 $F(x)$ 为 $n$ 个点的连通 DAG 个数,$G(x)$ 为**不要求连通**的 $n$ 个点的 DAG 个数,显然这也同样满足集合划分要求。证明不难,参考例子 1 即可。 | ||
行 103: | 行 120: | ||
===== 参考资料 ===== | ===== 参考资料 ===== | ||
- | * [[https://rqy.moe/Algorithms/generating-function/ | 生成函数简介 - _rqy's Blog]] | + | - [[https://rqy.moe/Algorithms/generating-function/ | 生成函数简介 - _rqy's Blog]] |