猫史档案馆

前言

 

翻了翻我以前发的帖子的记录，在我来编程猫的六年里，我的第一篇加精帖教程还是在 20 年的 5 月，这意味着我在猫站已经陆陆续续写了两年多教程了。这有可能是我在编程猫的最后一篇教程，也有可能不是。

 

本人也是正在学习生成函数这一块内容，因之我想将我在学习中的一些体会和总结分享给大家。由于作者的数学水平有限，有关多项式环 (Polynomial Ring)、形式幂级数 (Formal Power Series) 和解析函数 (Analytic Function) 的正式讨论留到之后再进行，或者也有可能不再介绍。

 

 

 

定义

 

生成函数 (Generating Function, GF) 是一类形式幂级数，由将一个序列作为其系数而产生：其中我们记：

表示取出次数为 n 的项的系数。

 

 

 

基本计数方法

 

例子

设有三类物品，分别有 A,B,C 个。每一类中第 i 个物品的价值分别为 ai​,bi​,ci​。从每类中各取一个。求取出的物品权值总和为 n 的方案数。

不妨设答案为 an​，则对于每一个 n，其为一个序列 {a0​,a1​,a2​,…,an​,…}，我们设这个序列的生成函数为 G(z)。

考虑任意一种情况：三种物品分别取出了 ak​,bk​,ck​ 这些价值的物品。这种情况贡献的项为：

 

等式右端的组合意义也很明显，即根据分布乘法原理，总的方案为三者选取方案之积。因之总方案的生成函数 G 为：

 

例子

下面我们修改上一个例子的条件，改为：

三种物品都有无限个，价值分别为 a,b,c，每种可以取任意个。

 

单独考虑每一个物品。不失一般性地，设取了 k 个物品 a。则其贡献为 z^(ka)，于是系数不为零的项的次数均为 a 的整数倍。设 Ga​(z)，删去系数为零的项我们得到：

类似可以得出 Gb​(z),Gc​(z)。从而最终结果的生成函数为：

 

 

 

二项卷积与指数生成函数

 

例子

下面讨论 n 个点的图连成恰不连通的两棵树的方案数。

 

引理（矩阵树定理的推论）

根据矩阵树定理 (matrix tree theorem)，n 个点的生成树数量为：

 

我们设其为：

再设恰不连通的两棵树的总方案数为 g(n)。

枚举第一棵树的个数 k，n 个点选取 k 划分到第一棵树中，其划分方案为 C(n,k)，而左右两棵树各自的方案为 f(k)​,f(n−k)​；这样对于每一种情况都计算了两次，需要除以二。因之：

 

右端这样的求和称之为二项卷积。对于二项卷积，我们拆开其中的二项式系数：

 

这个求和是一个非常整齐的卷积形式，即为两个相同的序列 f(k)/k!​​ 的生成函数的柯西乘积。事实上，我们对于这样的生成函数有一个特别的名字，称之为指数生成函数 (exponential generating function, EGF)。其一般形式为：

 

例如，序列 {1,1,1,…} 的指数生成函数是：

这就是 exp(z) 的 Taylor 级数的展开式。

 

 

 

带标号集合计数

 

例子：带标号生成树计数

下面讨论 n 个点生成恰好不连通的任意棵树的方案总数。从而最终答案的生成函数 G 与 F 有如下关系：

上述结论可以直接推广到将 n 个元素划分为若干集合的总方案数（g,G）与大小为 i 的集合的方案数（f,F）的一般情况。

 

 

 

无标号集合计数与欧拉变换

 

现在讨论无标号的情形，并引出欧拉变换 E。

下面讨论怎么计算欧拉变换 E。

 

 

 

总结

 

通过上述讨论，我们可以知道：如果我们对具有组合性质的数列建立起生成函数，那么其系数就将蕴含大量的组合意义。此时对这个幂级数进行操作，重要的计数问题就能够被简化和提炼。

 

 

 

后记

 

的确在这两年多的时间里我取得了一些成果：我发布的加精帖数量达到了将近五十篇，其中有六篇教程登上了“本周精选”和首页的教程推荐，我的教程还在去年的 12 月到今年 2 月这几个月的时间里持续“霸占”了论坛“本周精选”榜。看过我教程的人想必不在少数，我也由衷地希望我的教程能够给大家带来收获。我想：如果看教程的人能够从教程中学到知识技能，任何一个教程贴的作者都会为之感到高兴。

帖子标题前面那个【爵士】是有人让我以后写教程的时候挂上，方便下次检索的。当然我以后还会不会写教程本身就是个问题，毕竟我已经退猫半年多了，这次只是偶尔突然想回来再写一篇。

 

关于在哪里找我的教程其实大家看“训练时小课堂”模块的官方置顶帖里的这张图就可以了：

其中第一篇和第三篇帖子都是我的教程，排在第一位的是我的教程总集，排在第三位的帖子是我 2022 年的一篇比较火的教程，你也可以看作我的教程的众多代表作之一。