我们定义贝尔数\(Bn\)为：\(n\)个元素划分为任意个集合的方案数。
根据定义可以知道\(B_n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\)。根据这个式子计算单个贝尔数是\(O(nlogn)\)的
贝尔数还可以通过递推式计算。假设前\(n\)个元素已经任意划分，现在加入第\(n+1\)个元素；枚举新元素与前面i个元素分为一个集合，剩下的\(n-i\)个元素任意划分，就有：
\[
B_{n+1}=\sum_{i=0}^n{n\choose i}B_{n-i}=\sum_{i=0}^n{n\choose i}B_i
\]
这样可以\(O(n^2)\)计算前\(n\)个贝尔数的值。
贝尔数还可以写出生成函数。设\(f_n\)为n个元素划分为一个集合的方案数，显然\(f_n=1\)。写出\(f_n\)的指数型生成函数\(F(x)\)就是：
\[
F(x)=\sum_{n=1}\frac{x^n}{n!}=e^x-1
\]
那么\(n\)个数划分为i个集合的方案数就是：
\[
[x^n]F^i(x)
\]
枚举划分为多少个集合，那么贝尔数\(B\)的指数型生成函数\(B(x)\)就可以写成：
\[
B(x)=\sum_{n=0}\frac{F^n(x)}{n!}x^n=e^{F(x)}=e^{e^x-1}
\]
使用多项式exp，就可以\(O(nlogn)\)计算前\(n\)项贝尔数的值。
我还在知乎写过贝尔数的一些性质：贝尔数满足Touchard同余
原文：https://www.cnblogs.com/akura/p/12463127.html