写在前面的

本博客基本不会讲解如何运用组合数和斯特林数,应该偏向于数学证明,各类恒等式,我先咕一咕。

更新日志

  • 11.17 基本的组合恒等式。
  • 11.18 反演原理(很多反演放在后面讲解)。
  • 11.18 第一类斯特林数。
  • 11.18 第二类斯特林数。
  • 11.18 二项式反演,斯特林反演。

定义

在未作特殊说明下。

  • 时,函数值为 ,其它的所有时候函数值都为

  • 表示组合数。

  • 表示第二类斯特林数。

  • 表示第一类斯特林数。

  • 表示 阶上升幂,等价于

  • 表示 阶下降幂,等价于

  • 表示第二类斯特林数。

组合数

表示从 个有标号的元素中选出 个物品, 个物品没有先后顺序。

  • 全集中选择补集和直接选取的方案是等价的。

  • 组合数的最基本的等式。考虑 个元素的全排列,为 ,我们固定选取前面的 个,那么除以重复的排列 ,前面重复的次数为 ,后面重复的次数为 。所以原式子得证。

  • 非常重要的等式,可以考虑组合意义。对于 那么我们考虑第 个元素是否选择,那么选择的方案为 中选 。不选的方案为 中选 个。

  • 二项式定理。可以考虑数学归纳法证明。

    • 时,显然成立。

    • 然后我们把 项合并,得到 项的系数为 得证。

  • 根据二项式定理就可以得到,取

  • 根据二项式定理就可以得到,取

  • 范德蒙德卷积,按照组合意义是非常明确的,左边选 个,右边选择 个,其实等价于在总共中选择 个。
    这里考虑用二项式定理来证明。

    然后系数相同就好了。

  • 根据范德蒙德卷积。 就好了。

  • 。这个可以通过组合意义证明,这个的组合意义为选取 个元素,贡献为集合大小,那么我们考虑一个数的贡献为 一共 个数,所以答案为

  • 。证明方法很多,可以通过 再结合上式就可以做。或者直接考虑组合意义,贡献就是有顺序的选择两个数的方案,那么如果我们选择的两个数为 。当 贡献为 ,如果 则 贡献为 ,两个相加

  • 非常好用的公式,画图非常好理解。我们认为 是从 只能向右或者向上走一步,最后到 的方案。而 这些点在坐标轴中画出来,是一条平行于 轴的直线,那么串过这个直线的方案显然是等价于到达 的方案,也就是

  • 这个组合意义也比较显然,因为从 个中选择 个,再从 中选 个,等同于在 中选 ,再在剩下中选 个。 证明可以暴力展开组合数。

第一类斯特林数

意义为, 个元素构成 个环的方案数。

  • 比较好理解的递推式。考虑第 个元素是加入以前的环中,还是自己单独成一个环。

  • 组合意义还是比较明显的一个排列可以拆除一个置换,而 就表示了所有置换方案。考虑证明,还是通过数学归纳证明。

    • 时,式子显然成立。
    • 时。
  • 比较常见的式子,一般幂转下降幂。比较容易证明,还是考虑数学归纳法。

    • 时,显然成立。
    • 时,考虑归纳。

第二类斯特林数

  • 表示 个数中选出 个非空集合的方案数。

  • 可以根据定义来理解。考虑第 个数,要么加入 个集合中的某一个,要么自己再开一个集合。

  • 。这个式子的组合意义比较明显。考虑 个有标号的球放入有标号的 个盒子中,那么总方案为 。那么现在枚举一下不是空的的盒子。那么左右的方案数应该是一样的。所以上式子成立,如果不组合分析,我们可以考虑归纳法证明

    • 时显然成立。

  • 。组合意义比较清晰,我们可以考虑容斥。枚举空盒子,剩下的球随便选择盒子,然后考虑选哪些就好了。如果要证明的话,通过上面的恒等式,结合二项式反演就可以了(大雾)。

反演

反演原理

我们现在有 。那么我们考虑要满足 。则 要满足什么条件。

那么对于上式只要满足 即可。基本所有的反演都是基于这个性质的,同理只要某一个函数满足上式,就可以直接套用反演公式。

二项式反演

我们来证明一个东西。 。下面的推导用到了上面的组合恒等式和二项式定理。

那么喜闻乐见的,我们可以把这个式子代入反演公式,可以得到。

可能这个式子不太常见,我们把 做为 代入就可以得到。

这个形式就比较常见了。再稍稍变一下形式,本质上还是由于 。这也是比较常用的三种反演公式了。

  • 来个小例题,错位排序问题。我们定义 满足有 个元素满足 的排列数。那么我们根据全排列公式有 那么套用二项式反演, 。化简之后得到 这个和容斥分析出来的答案其实是一样的。而二项式反演的本质其实就是容斥。

  • 集合计数

    • 题意:一个有 个元素的集合有 个不同子集(包含空集),现在要在这 个集合中取出若干集合(至少一个),使得它们的交集的元素个数为 ,求取法的方案数。
    • 分析:我们可以先得到选 个交集中元素的方案为 。那么我们定义 为集合的交集的元素恰好为 的方案数,那么 ,还是套用二项式反演。

斯特林反演

引理

  • 。暴力展开式子左式子为 。而右式子为 。然后容易发现左式等于右式。

  • 。证明同上。

  • 反转公式。

由于多项式同类项系数相同,所以 时后面才会为 。也就是 由此得证。

  • 同理我们还可以得到另一个反转公式

  • 将得到的反转公式代入反演公式我就可以得到,斯特林反演的公式,为

稍微变形就可以得到另一个公式,但一般还是上式用的比较多。

  • 例题,通过斯特林反演我们可以轻松得到一般幂,下降幂和上升幂的关系了,非常简单,留给大家思考。