贝尔数
贝尔数 𝐵𝑛Bn
以埃里克·坦普尔·贝尔命名，是组合数学中的一组整数数列，开首是（OEIS A000110）：
𝐵0=1,𝐵1=1,𝐵2=2,𝐵3=5,𝐵4=15,𝐵5=52,𝐵6=203,…B0=1,B1=1,B2=2,B3=5,B4=15,B5=52,B6=203,…
𝐵𝑛Bn 是基数为 𝑛n 的集合的划分方法的数目．集合 𝑆S 的一个划分是定义为 𝑆S 的两两不相交的非空子集的族，它们的并是 𝑆S．例如 𝐵3 =5B3=5 因为 3 个元素的集合 𝑎,𝑏,𝑐a,b,c 有 5 种不同的划分方法：
{{𝑎},{𝑏},{𝑐}}{{𝑎},{𝑏,𝑐}}{{𝑏},{𝑎,𝑐}}{{𝑐},{𝑎,𝑏}}{{𝑎,𝑏,𝑐}}{{a},{b},{c}}{{a},{b,c}}{{b},{a,c}}{{c},{a,b}}{{a,b,c}}
𝐵0B0 是 1 因为空集正好有 1 种划分方法．
递推公式
贝尔数适合递推公式：
𝐵𝑛+1=𝑛∑𝑘=0(𝑛𝑘)𝐵𝑘Bn+1=∑k=0n(nk)Bk
证明：
𝐵𝑛+1Bn+1 是含有 𝑛 +1n+1 个元素集合的划分个数，设 𝐵𝑛Bn 的集合为 {𝑏1,𝑏2,𝑏3,…,𝑏𝑛}{b1,b2,b3,…,bn}，𝐵𝑛+1Bn+1 的集合为 {𝑏1,𝑏2,𝑏3,…,𝑏𝑛,𝑏𝑛+1}{b1,b2,b3,…,bn,bn+1}，那么可以认为 𝐵𝑛+1Bn+1 是有 𝐵𝑛Bn 增添了一个 𝑏𝑛+1bn+1 而产生的，考虑元素 𝑏𝑛+1bn+1．
- 假如它被单独分到一类，那么还剩下 𝑛n 个元素，这种情况下划分数为 (𝑛𝑛)𝐵𝑛(nn)Bn;
- 假如它和某 1 个元素分到一类，那么还剩下 𝑛 −1n−1 个元素，这种情况下划分数为 (𝑛𝑛−1)𝐵𝑛−1(nn−1)Bn−1；
- 假如它和某 2 个元素分到一类，那么还剩下 𝑛 −2n−2 个元素，这种情况下划分数为 (𝑛𝑛−2)𝐵𝑛−2(nn−2)Bn−2；
- ……
以此类推就得到了上面的公式．
每个贝尔数都是相应的 第二类斯特林数 的和． 因为第二类斯特林数是把基数为 𝑛n 的集合划分为正好 𝑘k 个非空集的方法数目．
𝐵𝑛=𝑛∑𝑘=0{𝑛𝑘}Bn=∑k=0n{nk}
贝尔三角形
用以下方法构造一个三角矩阵（形式类似杨辉三角形）：
- 𝑎0,0 =1a0,0=1；
- 对于 𝑛 ≥1n≥1，第 𝑛n 行首项等于上一行的末项，即 𝑎𝑛,0 =𝑎𝑛−1,𝑛−1an,0=an−1,n−1；
- 对于 𝑚,𝑛 ≥1m,n≥1，第 𝑛n 行第 𝑚m 项等于它左边和左上角两个数之和，即 𝑎𝑛,𝑚 =𝑎𝑛,𝑚−1 +𝑎𝑛−1,𝑚−1an,m=an,m−1+an−1,m−1．
部分结果如下：
11223557101515202737525267871141512032032553224095236748771122355710151520273752526787114151203203255322409523674877
每行的首项是贝尔数．可以利用这个三角形来递推求出贝尔数．
参考实现
C++Python
---|---
---|---
指数生成函数
考虑贝尔数的指数生成函数及其导函数：
ˆ𝐵(𝑥)=+∞∑𝑛=0𝐵𝑛𝑛!𝑥𝑛=1++∞∑𝑛=0𝐵𝑛+1(𝑛+1)!𝑥𝑛+1ˆ𝐵′(𝑥)=+∞∑𝑛=0𝐵𝑛+1𝑛!𝑥𝑛B^(x)=∑n=0+∞Bnn!xn=1+∑n=0+∞Bn+1(n+1)!xn+1B^′(x)=∑n=0+∞Bn+1n!xn
根据贝尔数的递推公式可以得到：
𝐵𝑛+1𝑛!=𝑛∑𝑘=01(𝑛−𝑘)!𝐵𝑘𝑘!Bn+1n!=∑k=0n1(n−k)!Bkk!
这是一个卷积的式子，因此有：
ˆ𝐵′(𝑥)=e𝑥ˆ𝐵(𝑥)B^′(x)=exB^(x)
这是一个微分方程，解得：
ˆ𝐵(𝑥)=exp(e𝑥+𝐶)B^(x)=exp(ex+C)
最后当 𝑥 =0x=0 时 ˆ𝐵(𝑥) =1B^(x)=1，带入后解得 𝐶 = −1C=−1，得到贝尔数指数生成函数的封闭形式：
ˆ𝐵(𝑥)=exp(e𝑥−1)B^(x)=exp(ex−1)
预处理出 e𝑥 −1ex−1 的前 𝑛n 项后做一次 多项式 exp 即可得出贝尔数前 𝑛n 项，时间复杂度瓶颈在多项式 exp，可做到 𝑂(𝑛log𝑛)O(nlogn) 的时间复杂度．
参考文献
<https://en.wikipedia.org/wiki/Bell_number>
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Tiphereth-A, Enter-tainer, Xeonacid, ksyx, Great-designer, iamtwz, Ir1d, LDlornd, Menci, Running-Turtle1, ShaoChenHeng, shawlleyw, StudyingFather, untitledunrevised, ZnPdCo 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用