浅析生成函数
目录更好的阅读体验戳此进入
定义
生成函数(Generating Function),又称母函数,其严谨一点的定义:序列 $ a_n $ 的生成函数是一种形式幂级数,每一项的系数会提供关于这个序列的信息。
更详细地解释一下,就是对于函数中第 $ i $ 项的系数就代表了序列第 $ i $ 项的值,但是不同于一般的函数 $ G(x) $,这里的 $ x $ 的取值并不会对其本身的意义有任何影响,这种函数就被称作形式幂级数。
OGF(普通生成函数)
引入生成函数,最好的例子应该就是多重集的组合了,容斥思想的做法可以参考 浅析排列组合、卡特兰数、斯特林数、贝尔数、二项式定理与推论及其反演、子集反演、广义容斥、范德蒙德卷积 - 多重集的排列组合数。
而另一种思想,不难发现这就是个简单的背包,我们可以考虑对每种物品,假设第 $ i $ 种物品有 $ n_i $ 个,共有 $ k $ 种,则:
第 $ i $ 个物品的生成函数为:$ G_i(x) = 1 + x^1 + x^2 + \cdots + x^{n_i} $。
若我们将所有生成函数乘在一起,则 $ \prod_{i = 1}^k G_i(x) $ 的第 $ \alpha $ 项即为多重集选择 $ \alpha $ 个的组合数的答案。
考虑证明,感性理解一下显然对于两个多项式的卷积 $ f \ast g $,有 $ (f \ast g)k = \sum^k f_ig_{k - i} $,这个式子即在枚举从 $ f $ 物品中选择 $ i $ 个的方案数与 $ g $ 中选择 $ k - i $ 个的方案数通过乘法原理合成的共选择 $ k $ 个的方案数。
而对于这种形如 $ G(x) = \sum a_ix^i $ 的生成函数,称其为普通生成函数,即 OGF。
OGF 在多项式相乘时的形式即为:$ \sum_{i = 0}^n a_ib_{n - i} $。
EGF(指数生成函数)
而对于多重集的非全排列,似乎就不可以通过容斥原理处理了(或者我不会),于是我们可以引入一种新的生成函数。
还是考虑类似的问题,即多重集的排列,了解这个我们可以先想到多重集的全排列,具体可以从上文的链接去看细节,这里仅简单提一下:
\[P = \dfrac{N!}{\prod_{i = 1}^k n_k!} \]也就是从排列数中去掉每一种的总个数,对于非全排列,也不难想到其即为从每种组合方案中进行排列并除以对应的分母。
于是引入指数生成函数,即 EGF,具体来讲其形式为:$ G(x) = \sum a_i \dfrac{x^i}{i!} $。
对于多重集的排列,则对于每个集合的 $ n_i $ 构造:
\[G_i(x) = 1 + \dfrac{x}{1!} + \dfrac{x^2}{2!} + \cdots + \dfrac{x^{n_i}}{n_i!} \]然后全部乘在一起得到:
\[\prod_{i = 1}^k G_i(x) \]然后从中选择 $ m $ 个元素的方案数即该式的 $ m $ 次项系数乘上 $ m! $ 即为答案。
EGF 在多项式相乘时的形式为 $ \dfrac{1}{n!}\sum_{i = 0}^n {n \choose i}a_i b_{n - i} $。这个东西也比较显然,展开化简后可得。
CGF(组合生成函数)
组合生成函数,形如:
\[G(x) = \sum a_i \dfrac{x^i}{i!2^{i \choose 2}} \]CGF 在多项式相乘时的形式为 $ \dfrac{1}{n!2^{n \choose 2}}\sum_{i = 0}^n {n \choose i}2^{i(n - i)}a_ib_{n - i} \(,意义上很好理解,\) 2^{i(n - i)} $ 就是在枚举两者之间的边的方向。
用于解决的是有标号有向图计数,资料不足剩余待补。
PGF(概率生成函数)
对于随机变量 $ X \(,有其概率生成函数:\) G(x) = \sum_i P{X = i }x^i $。
显然 $ G(1) = \sum_i P{X = i } = 1$。
同时对 $ G(x) $ 求导有 $ G'(x) = \sum_i P{ X = i }ix^{i - 1} $。
则 $ G'(1) = \sum_i P{ X = i }i = E(X) $。
而对于高阶导数,或者说 $ k $ 阶导数,有 $ G^{(k)}(1) = E(X^{\underline{k}}) $,这个东西我们考虑对一个多项式求导,展开得到 $ G^{(k)}(1) = \sum_i P{X = i}\prod_{i = 0}^{k - 1}(i - k) $,也就是其 $ k $ 阶导数的意义为 $ k $ 次下降幂的期望。
同时对于方差有:$ \sigma^2 = E(X^2) - E(X)^2 = G''(1) + G'(1) - (G'(1)) ^2 $。
证明:
首先考虑 $ G''(1) $,有 $ G''(1) = E(X(X - 1)) $,也就是 $ \sum_i P{X = i}i(i - 1) $ 把这个转化一下就是:$ \sum_i P{X = i}i^2 - \sum_i P{X = i}i $,也就是 $ E(X^2) - E(X) $,那么有 $ E(X^2) - E(X) = G''(1) $,又有 $ E(X) = G'(1) $,那么 $ E(X^2) = E(X) + G''(1) = G'(1) + G''(1) \(,带入,\) \mathrm{QED} $。
然后 PGF 在多项式相乘的形式为 $ \sum_{i = 0}^n P{X = i}P{Y = n - i} $,当然也可形象地记为 $ P{X + Y = n} $。
同时不难发现第二种记法同时体现出了其中的一个性质,即 $ F_X(x) \ast F_Y(x) = F_{X + Y}(x) $。
感觉下一部分内容今天写不完了,先这些,下一部分写完之后再 update。
UPD
update-2023_02_07 初稿
标签:函数,dfrac,sum,多重集,生成,浅析 From: https://www.cnblogs.com/tsawke/p/17180271.html