写在前面的
本博客基本不会讲解如何运用组合数和斯特林数,应该偏向于数学证明,各类恒等式,我先咕一咕。
更新日志
- 11.17 基本的组合恒等式。
- 11.18 反演原理(很多反演放在后面讲解)。
- 11.18 第一类斯特林数。
- 11.18 第二类斯特林数。
- 11.18 二项式反演,斯特林反演。
定义
在未作特殊说明下。
在 时,函数值为 ,其它的所有时候函数值都为 。
表示组合数。
表示第二类斯特林数。
表示第一类斯特林数。
表示 的 阶上升幂,等价于 。
表示 的 阶下降幂,等价于 。
表示第二类斯特林数。
组合数
表示从 个有标号的元素中选出 个物品, 个物品没有先后顺序。
全集中选择补集和直接选取的方案是等价的。
组合数的最基本的等式。考虑 个元素的全排列,为 ,我们固定选取前面的 个,那么除以重复的排列 ,前面重复的次数为 ,后面重复的次数为 。所以原式子得证。
非常重要的等式,可以考虑组合意义。对于 是 选 那么我们考虑第 个元素是否选择,那么选择的方案为 中选 。不选的方案为 中选 个。
二项式定理。可以考虑数学归纳法证明。
或 时,显然成立。
时
然后我们把 项合并,得到 项的系数为 得证。
根据二项式定理就可以得到,取 。
根据二项式定理就可以得到,取 。
范德蒙德卷积,按照组合意义是非常明确的,左边选 个,右边选择 个,其实等价于在总共中选择 个。
这里考虑用二项式定理来证明。然后系数相同就好了。
根据范德蒙德卷积。 就好了。
。这个可以通过组合意义证明,这个的组合意义为选取 个元素,贡献为集合大小,那么我们考虑一个数的贡献为 一共 个数,所以答案为 。
。证明方法很多,可以通过 再结合上式就可以做。或者直接考虑组合意义,贡献就是有顺序的选择两个数的方案,那么如果我们选择的两个数为 。当 贡献为 ,如果 则 贡献为 ,两个相加 。
非常好用的公式,画图非常好理解。我们认为 是从 只能向右或者向上走一步,最后到 的方案。而 这些点在坐标轴中画出来,是一条平行于 轴的直线,那么串过这个直线的方案显然是等价于到达 的方案,也就是 。
这个组合意义也比较显然,因为从 个中选择 个,再从 中选 个,等同于在 中选 ,再在剩下中选 个。 证明可以暴力展开组合数。
第一类斯特林数
意义为, 个元素构成 个环的方案数。
比较好理解的递推式。考虑第 个元素是加入以前的环中,还是自己单独成一个环。
组合意义还是比较明显的一个排列可以拆除一个置换,而 就表示了所有置换方案。考虑证明,还是通过数学归纳证明。
- 时,式子显然成立。
- 时。
比较常见的式子,一般幂转下降幂。比较容易证明,还是考虑数学归纳法。
- 当 时,显然成立。
- 当 时,考虑归纳。
第二类斯特林数
表示 个数中选出 个非空集合的方案数。
可以根据定义来理解。考虑第 个数,要么加入 个集合中的某一个,要么自己再开一个集合。
。这个式子的组合意义比较明显。考虑 个有标号的球放入有标号的 个盒子中,那么总方案为 。那么现在枚举一下不是空的的盒子。那么左右的方案数应该是一样的。所以上式子成立,如果不组合分析,我们可以考虑归纳法证明
- 当 时显然成立。
- 当 时
- 。组合意义比较清晰,我们可以考虑容斥。枚举空盒子,剩下的球随便选择盒子,然后考虑选哪些就好了。如果要证明的话,通过上面的恒等式,结合二项式反演就可以了(大雾)。
反演
反演原理
我们现在有 。那么我们考虑要满足 。则 要满足什么条件。
那么对于上式只要满足 即可。基本所有的反演都是基于这个性质的,同理只要某一个函数满足上式,就可以直接套用反演公式。
二项式反演
我们来证明一个东西。 。下面的推导用到了上面的组合恒等式和二项式定理。
那么喜闻乐见的,我们可以把这个式子代入反演公式,可以得到。
可能这个式子不太常见,我们把 做为 代入就可以得到。
这个形式就比较常见了。再稍稍变一下形式,本质上还是由于 。这也是比较常用的三种反演公式了。
来个小例题,错位排序问题。我们定义 满足有 个元素满足 的排列数。那么我们根据全排列公式有 那么套用二项式反演, 。化简之后得到 这个和容斥分析出来的答案其实是一样的。而二项式反演的本质其实就是容斥。
-
- 题意:一个有 个元素的集合有 个不同子集(包含空集),现在要在这 个集合中取出若干集合(至少一个),使得它们的交集的元素个数为 ,求取法的方案数。
- 分析:我们可以先得到选 个交集中元素的方案为 。那么我们定义 为集合的交集的元素恰好为 的方案数,那么 ,还是套用二项式反演。 。
斯特林反演
引理
。暴力展开式子左式子为 。而右式子为 。然后容易发现左式等于右式。
。证明同上。
反转公式。
由于多项式同类项系数相同,所以 时后面才会为 。也就是 由此得证。
同理我们还可以得到另一个反转公式 。
将得到的反转公式代入反演公式我就可以得到,斯特林反演的公式,为
稍微变形就可以得到另一个公式,但一般还是上式用的比较多。
- 例题,通过斯特林反演我们可以轻松得到一般幂,下降幂和上升幂的关系了,非常简单,留给大家思考。