generating functionology

Chapter 1

normal generating function

生成函数的意义

对于一个数列, 例如斐波那契数列, 我们也许没法给出一个较为简便的通项公式, 但我们可以通过生成函数, 用比较简便的公式表达数列的和

比如斐波那契数列的第 项为 的 项系数

求某一项系数

用 表示 中 的系数

我们有两个基本运算法则

one variable

three terms

对于

设

两边同乘 , 得到

即

所以

令 为 的两个根

则可以代入 , 把 求出

应用: 样条插值 Spline interpolation

对于 , 要构造一个函数 , 使得其在每一段 上的函数不同, 连续, 且

假设在 为

可以通过 个插值条件:

和 个连续条件:

找出这样的

不加证明的给出

其中

这个式子可以用上面的 的解来算出生成函数

这里

那么

可代入 解出

这样我们求出了所有的 , 即求出了

two variables

组合数

假设

我们想求出

可以构造

那么原式同乘 , 得到

得到

所以

现在对于 乘上 , 对 求和, 得到

即

同时, 对上式取 系数

所以

第二类斯特林数 stirling number of the second kind

把 个元素分成 个集合不同的方法数, 为第二类斯特林数, 记为

先求递推式

如果最大的元素 自己一个集合, 那么就将前 个元素分成 个集合, 再加上 即可, 方案数为

如果最大的元素 与其他元素在同一个集合, 相当于将前 个元素分成 组集合, 再将 插入到某一个集合内

个元素分出 组的方案数是 , 一共可以插 个集合, 所以一共

所以

这样我们可以像上面一样找出 个公式:

计算

先求第二个式子, 两边同乘 得到

注意边界条件是

所以有

得出

一串连乘的 可以拆成每一项相加, 即

为了得到 , 我们可以试探 来得到

看到右边的 , 我们想到令 使得某一项为

但是这样做只有 一项分母为

所以可以固定这个 , 两边同乘 , 并令

就得到

所以

计算

对于 的计算, 两边同乘 后有

所以由递推式 以及边界条件 得通项

expotential generating function

对于上面的第二类斯特林数, 如果固定 , 将 从 到 求和, 那么得出的为 Bell number, 记作

那么代入上面的第二类斯特林数公式:

对于这样的 函数, 我们构造另一种生成函数:

可以看到多了一个系数

这种形式的生成函数 区别于 , 称为 expotential generating function, 简称 EGF

普通的 称为 ordinary generating function, 简称 OGF

那么我们就可以计算出 的具体形式

注意

所以

由生成函数得到递推式

对于 , 我们想要借此找到 的递推式, 可以对 两边作用 算子

得到

对于左边, 可以得出 的系数为

对于右边, 需要将 展开, 两个级数相乘得到系数

计算过程略, 我们有:

Chapter 2

形式幂级数

我们可以用形式幂级数及其系数列来研究生成函数

一个形式幂级数长成如下形式

将序列 称为系数列

这样的形式幂级数满足普通的加法, 乘法法则 (对于乘法: )

所以构成了一个形式幂级数环

或者说, 定义了下面两种元后, 这样的幂级数构成一个环

0x00 倒数

我们利用乘法法则, 可以得到一个常用的式子:

那么对于幂级数 存在倒数

命题: 形式幂级数 存在倒数当且仅当

假设存在倒数 , 那么 , 即

所以有

同时

所以可以求出所有的

0x01 逆

与倒数不同, 幂级数 的逆是满足 的幂级数

我们想要确定何时 可以存在

具体展开 的每一项:

如果 , 那么

也就是说, 的计算只会与 的前 项有关, 因为 项以后只包含 以上的项

所以这样的 计算是有限的

相反, 如果 , 那么 的每一项 都会对 产生贡献, 计算是无限的, 除非 本身是多项式, 即 只有有限项

所以我们说 的逆有定义, 当且仅当 或 是多项式

命题: 如果 且 , 那么 存在当且仅当 , 即

假设 ,

那么 , 所以有 ,

同时可以发现

计算普通形式幂级数生成函数

0x00 定义

我们说

如果 是系数列 的普通形式幂级数生成函数, 即

• ordinary power series generating function = opsgf

0x01 下标迭代

计算

对于 , 将 减掉并除以 , 得到

拓展一下, 对于 , 有

具体推导略了罢

0x02 系数乘以下标

计算

看到这个 就想导一导

所以对 求导得到 , 再乘以 即可

将算子 定义成 , 则有

例1

对于递推式

右边为 , 即

左边对 求一次导后得到

所以加上 有

所以

拓展一下, 对于 有

例2

计算 , 它等于

也就是说, 对于一个关于 的多项式, 可以用 算子求出对应的幂级数, 即

例3

计算 的值

对于 , 它等于

所以可以构造

则 为原式的值

但是这个计算过程是否有问题?

我们前面所说的形式幂级数环并没有 “取 ” 这个操作, 形式幂级数是没有具体值代入操作的

所以说, 我们给出一个修正:

如果根据递推式计算形式幂级数后, 发现这个级数收敛到以复平面的某个域为定义域的分析函数上, 那么就可以将这个形式幂级数作为普通分析函数来操作

上面看起来啥也没做, 但其实是必要的

只有这样我们才能严谨地使用我们得出的分析函数来进行求值操作

例4

使用生成函数求

由上面的 式

所以

评价为多此一举, 但是豪丸

0x03 幂级数相乘

两个幂级数 相乘, 满足正常的多项式乘法法则

拓展一下有如下法则:

例5

计算将整数 分成 个非负整数的方案数

可以使用 , 那么

即

每个 的系数为

注意这是个常用的公式

0x04 前缀和幂级数

根据前面 式, 将 与 相乘, 得到

所以

即 生成了原序列前缀和的序列

例6 (例4++)

用前缀和的方式求

由 和 式, 有

左边等于

并且由 式

例7

求调和级数

令

例8

利用 Fibonacci 数列性质 求生成函数

左边等于

右边等于

可得

例9

你是一个旅客, 你要往许愿喷泉里 doinb (丢硬币)

一个硬币喷泉, 从下往上放硬币, 每行的硬币都连续; 从第二行开始每个硬币都要与下面两个硬币相邻, 即硬币数不比下面一行多

对于最下面一行 个硬币, 一共有 个硬币的喷泉, 称为 硬币喷泉

令 为最下面为 个硬币的喷泉数

如果第二行一个硬币没有, 则方案数为 ; 否则有 种方案

则有递推式

两边同乘 , 对 求和, 左边等于

右边第一项等于 与 相乘, 即

所以有

得到

序列 起始几项为

对, 这是隔项 Fibonacci 数列

练习

证明上面的

是 Fibonacci 数列

数学归纳法

首先 成立

假设 对 到 成立

那么由递推式

我们来凑

再凑

以此类推, 最后得到

最后一步是 例8 的那个式子

所以

证毕

用生成函数的方式来做

记

所以可以用 来展开 的每一项, 分别得到

第二个式子得到

代入一式得到

那么

这说明

所以

计算指数形式幂级数生成函数

0x00 定义

用 表示 是序列 的指数生成函数, 即

0x01 下标迭代

所以拓展一下

0x02 系数乘以下标

我们发现对 作用 算子, 得到

这与普通生成函数是一样的

所以类似于 式, 我们有

0x03 幂级数相乘

对于两个 相乘, 有

所以

即

这是很有趣的结果, 两项相乘后为二项展开

同时类似于 式, 有

例10

对于第一章的 Bell number 递推式:

求指数生成函数

对于递推式同乘 , 左边为 , 右边为 与 相乘

可以得到

例11

括号匹配方案数

设 表示 个括号的方案数

怎么求递推式呢?

我们发现 个括号组成的串可能在前 个括号都匹配后第一次闭合

如 在 时闭合

称第一次闭合组成的串为初级串, 即不能被拆成两个串拼接的串

那么只要知道前 个括号的初级串个数, 后 个括号任意组合, 就得到递推式

假设一共有 个括号, 表示初级串的方案数, 那么

这是因为初级串可以由任意串两端加一个括号组成, 所以方案数恰好等于

那么有递推式

的前几项为

对, 这是 Catalan 数

要想求 ops, 递推式两边乘 , 对 求和

左边等于 , 右边等于两个序列相乘

所以得到

有意思的是这个 号

将 代入, 我们只能选择

例12

完全错排

假设完全错排的指数生成函数是

对于全排列 有递推式

那么两边同乘

所以

求错位级数

有级数 ,我们想求

我们可以构造

因为 在 为奇数时为 , 偶数时为

所以这样的 满足条件

拓展一下, 我们想求

我们构造单位根

则

符合条件

计算 Dirichlet 幂级数生成函数

定义

为 Dirichlet 幂级数生成函数

(Dirichlet series generating function = Dsgf)

记为

注意是从 开始

0x00 幂级数相乘

每项系数等于

即

所以

进一步有

0x01 全 1 系数

对于 , 其不是一个简单函数, 而是 Riemann 函数

具体为

对于两个全 系数的生成函数相乘, 由 式, 其系数为

其中 表示 的因子个数

这是个很有趣的公式, 用这样看起来复杂的生成函数表示这样相对简单的函数

0x02 积性函数

如果一个函数满足

就说他是积性函数

并且一个数可以唯一分解成 , 所以

例如, 我们可以发现上面的 是一个积性函数

那么, 将积性函数的性质应用到生成函数上

0x03 分解定理

假设 Dsgf 的系数 , 我们有

将右边的式子展开:

如果我们要找出 这一项

由于

只需要从一行中挑出对应的 , 就可以唯一表示

同时, 每个 也只有一种表达方式 (唯一的分解方式)

所以 式的左边右边一一对应, 故等式成立

那么由 式得出 函数的一个更显式的表达式:

0x04 黎曼函数的倒数

我们想求 函数的倒数

可以构造积性函数

对于 , 有

即只有 时 不为

进一步, 对于任意的 , 如果 , 则

如果 , 则

如果 , 即有大于 的平方数因数 , 则

从这个定义可以看出 是积性函数

事实上它是莫比乌斯函数

那么由 式, 这样的函数满足

有趣的是, 这恰好是前面 式中 的倒数, 即

我们可以用这个式子来做莫比乌斯反演

具体地, 已知

我们想求出 的表达式

那么可以利用 式, 两边同乘 :

记 , 则

所以

展开得到

这就是莫比乌斯反演公式

于是, 黎曼 函数与莫比乌斯 函数很巧妙地通过倒数关系联系了起来

例13

我们说一个二进制串是原始串, 如果它不能拆成 个相同的串拼接而成

记 表示长度为 的原始串个数

并且长度为 的所有 个串, 每一个串都可以被任意数量的某个原始串拼接而成, 这样的原始串有且仅有一个

所以有

所以用 式:

• 注意这种将全集表示成子集的和的方法可以用来求出子集中包含的表达式, 上面的完全错排和下面的例子也是这样干的

例14

方程 的 个复数解称为 次单位根

记 次单位根的第 个根为

如果这个根 不能作为某个 次单位根 , 且 , 那么就说这个根是原始根

即满足 的根

这样的原始根恰好有 个, 是欧拉函数

假设这些原始单位根为

那么构造多项式

这个多项式称为分圆多项式

(cyclotimic = circle-cutting)

我们发现

这是因为任意一个单位根 都能且只能作为唯一的一个 的原始根

因为记 , 那么

所以 是 中的一个 次原始单位根

所以我们接着用 莫比乌斯反演

只不过先取对

那么

练习

试着用上面的式子导出:

其中第一个式子可以用来做欧拉反演

事实上由 式, 左边 的根的个数恰好为 , 右边跟的个数为 , 并且左边的所有根不重复地组成了右边的所有根

根据这一数量关系即得 式

进而对 式做莫比乌斯反演, 即得 式

或者你可以通过 式得到 式

先由 式得到

两边同除

---

参考