\(B_n\) 表示将 \(n\) 个不同的元素划分为若干非空集合的方案数。
递推式:\(B_{n + 1} = \sum_{k = 0}^nC(n, k)B_k\)
证明:考虑第 \(n+1\) 个元素,可以把它和 \(k\) 个其他元素划分在一起,那么剩余 \(n - k\) 个元素有 \(B_{n - k}\) 种划分。
递推式:\(B_n = \sum_{k = 0}^n Stirling2(n, k)\)
证明:\(Stirling2(n, k)\) 表示将 \(n\) 个不同的元素划分为 \(k\) 个非空集合的方案数。
Bell 三角
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
- \(b(0, 0) = 1\)
- \(b(i, 0) = b(i - 1, i - 1)\)
- \(b(i, j) = b(i, j - 1) + b(i - 1, j - 1)\)