一个早就听说过的东西，但一直不知道是啥。
今天刚好做到一道贝尔数裸题，就来学习了一下。
贝尔数\(B_n\)表示的是\(n\)个有标号元素的集合划分数目。
其中集合划分是指把一个集合不重不漏地分成若干子集。
首先推导一下贝尔数的递推式。
现在新增了一个元素\(B_{n+1}\)，我们去枚举与它不在同一集合中的元素个数\(i\)，由此得到公式：
此外，考虑到第二类斯特林数的定义：第二类斯特林数\(S_2(n,m)\)表示\(n\)个有标号元素划分为\(m\)个非空集合的方案数。（关于第二类斯特林数可见斯特林数的基础性质与斯特林反演的初步入门，后文还会对它的一些性质有所涉及）
显然根据它俩的定义就可以得出它们的关系：
然后我们考虑一下如何通过\(B_n\)和\(B_m\)得到\(B_{n+m}\)。
我们先枚举把\(m\)个元素划分成了\(j\)个集合，然后枚举\(n\)个元素中不与\(m\)合并的元素个数\(i\)，则剩下的\(n-i\)个元素每一个都可以随意放到这\(j\)个集合中的某一个里，由此得到公式：
一个非常重要的性质，使得在取模问题中能够快速求出某一贝尔数。
首先给出结论，对于一个质数模数\(p\)，满足：
接下来是证明。
根据之前的公式，可以直接把\(B_{n+p}\)拆开得到：
由于\(\forall j\in(1,p),S_2(p,j)\equiv0(mod\ p)\)，所以只有当\(j=1\)或\(p\)时\(S_2(p,j)\)才有值\(1\)，由此得到：
其中前者根据我们之前得到的递推式，就是\(B_{n+1}\)。
而后者中存在一项\(p^{n-i}\)，当\(i\not=n\)时\(p^{n-i}\equiv0(mod\ p)\)，所以只能取\(i=n\)，此时\(C_n^n=1\)，只剩\(B_n\)。
综上，我们得出结论：
顺便提一下它的一个扩展：
【BZOJ3501】[PA2008] Cliquers Strike Back
原文：https://www.cnblogs.com/chenxiaoran666/p/Bell.html