第二类斯特林数

表示不同元素分为个非空集合的方案数。

递推:

容斥:

第一类斯特林数

表示不同元素分为个非空环排列的方案数。

递推:

贝尔数

表示个不同元素划分成若干非空集合的方案数。

根据定义:

枚举新增集合的元素个数:

贝尔数的指数型生成函数:

通常幂与下降幂转换公式

斯特林数反演

更广泛地:

当取时即为通常幂与下降幂转换公式

栗子

丢一个CF 932 E

这一场当场A了这题,但是因为一些不可告人的原因被ban了。

求:

范围是,初步猜测复杂度是

推一推:

发现斯特林数预处理是,下降幂预处理是,后面的计算是

再丢一个BZOJ 2159

题意是给一棵树,求:

范围是

看到这个结构就先通常幂转下降幂(组合数)

拆成两部分,其中表示子树对的贡献,表示非子树的贡献。

同理,

自下至上DP,把自上至下DP,然后统计答案即可。