首页 > 其他分享 >浅析生成函数

浅析生成函数

时间:2023-03-05 13:13:42浏览次数:41  
标签:函数 dfrac sum 多重集 生成 浅析

浅析生成函数

目录

更好的阅读体验戳此进入

定义

生成函数(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

相关文章

  • 浅析群论
    GroupTheory-浅析群论目录GroupTheory-浅析群论更好的阅读体验戳此进入群阶子群陪集定义与性质常见表述拉格朗日定理置换定义运算置换群定义群作用群对自身的作用群......
  • Python 字符串切割函数设计
    s="fs.fes..23...43....tghf"print"要切割的字符串为:",s,"\n"s=s.strip()#去掉字符串左右两边空格print"输出去掉空格的字符串:",s,"\n"#sep为切割字符串的......
  • WebStorage 浏览器的本地存储(4个函数:setItem、getItem、removeItem、clear)
    一、WebStorage1、内存内容大小一般支持5MB左右,不同浏览器可能还不一样2、浏览器端通过Window.sessionStorage和Window.localStorage属性来实现本地存储机制3、相关......
  • 8.实现一个sleep函数
    实现一个sleep函数①利用堵塞循环实现,因为js是单线程的,所以这个其实就是根本上的sleepfunctionsleep(delay){varstart=(newDate()).getTime();while((new......
  • 6.手写函数柯里化工具函数、并理解其应用场景和优势
    手写函数柯里化工具函数、并理解其应用场景和优势什么是柯里化(Curring)???什么意思?简单来说,柯里化是一项技术,它用来改造多参数的函数。  简单讲就是把一个多参数的函......
  • STATA:字符串处理函数收集
    //*命令subinstr(S1,S2,S3,n),n表示迭代的次数,S1是变量,S2是需要替代的变量,S3是新替换的变量。如果n是.代表所有的都换*///reverse()字符串逆顺localwjm="`c(current_t......
  • day3函数
    """函数的概念:S=πr²,当我们知道半径r的值时,就可以通过公式计算出面积,假设我们需要计算3个不同大小的圆的面积:出现了几乎完全重复的代码,每次计算圆的面积的......
  • SQL中只要用到聚合函数就一定要用到group by 吗?
    今天记录一个弱智问题,一直没发现这个问题。答:看情况1、当聚集函数和非聚集函数出现在一起时,需要将非聚集函数进行groupby2、当只做聚集函数查询时候,就不需要进行分组了......
  • 数论学习笔记2:数论函数
    积性函数定义积性函数是满足\(\forallu\perpv,f(uv)=f(u)f(v)\)的数论函数,\(f(1)\)总是等于\(1\)。求值由定义可知,积性函数在全体正整数处的取值由其在\(p^k\)......
  • ES6-ES11 生成器函数的实例(解决回调地狱问题)
    原视频<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><titl......