用户工具

站点工具


2020-2021:teams:i_dont_know_png:nikkukun:generating-function

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

后一修订版
前一修订版
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]]
2020-2021/teams/i_dont_know_png/nikkukun/generating-function.1596794872.txt.gz · 最后更改: 2020/08/07 18:07 由 nikkukun