斯特林数备忘录

这个真的只是一个备忘录
而且基本上是从维基百科上 copy 的

第一类斯特林数

第一类 Stirling 数是有正负的,其绝对值是 $n$ 个元素的项目分作 $k$ 个环排列的方法数目。常用的表示方法有 $s(n,k)$
换个较生活化的说法,就是有 $n$ 个人分成 $k$ 组,每组内再按特定顺序围圈的分组方法的数目。例如 $s(4,2)=11$

第二类斯特林数

是将 $n$ 个元素划分为 $k$ 个无差异非空集合的方案数
常用 $S(n,k)$ 表示
递推关系
$$ S(n,k)=S(n-1,k-1)+kS(n-1,k) $$
递推式说明:考虑前面的 $n-1$ 个已经放完,现在考虑第 $n$ 个应该怎么放,可以单独新开一个集合自己单独放($S(n-1,k-1)$),或者将当前这个放到之前 $n-1$ 个已经放好了的 $k$ 个集合里,有 $k$ 种放法 ($kS(n-1,k)$)
第二类斯特林数公式:
$$ S(n,k)=\frac{1}{k!}\sum_{i=0}^{k}(-1)^i C_k^i (k-i)^n $$
公式说明:枚举空集合个数做容斥原理,设有 $\geq i$ 个空集合,那么答案 $=ans_{\geq 0 个空集}-ans_{\geq 1 个空集} +ans_{\geq 2 个空集}\dots$ 最后由于这样算出的是有差异集合的方案数,所以要除去差异的影响

引用资料

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注