\(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

  1. \(b(0, 0) = 1\)
  2. \(b(i, 0) = b(i - 1, i - 1)\)
  3. \(b(i, j) = b(i, j - 1) + b(i - 1, j - 1)\)

证明:

\[ \begin{aligned} b(n, 0) &= b(n - 1, n - 1)\\ &= b(n - 1, n - 2) + b(n - 2, n - 2)\\ &= b(n - 1, n - 3) + 2b(n - 2, n - 3) + b(n - 3, n - 3)\\ &= \dots\\ &= \sum_{k = 0}^{n - 1}C(n - 1, k)b(k - 1, 0) \end{aligned} \]

1

2 1

5 3 2

15 10 7 5

32 37 27 20 15

  1. \(b(0, 0) = 1\)
  2. \(b(i, i) = b(i - 1, 0)\)
  3. \(b(i, j) = b(i, j + 1) + b(i - 1, j)\)

\(p\) 为任意素数

模运算性质:\(B_{p + n} \equiv B_n + B_{n + 1} \pmod p\)

模运算性质:\(B_{p^m + n} \equiv mB_n + B_{n + 1} \pmod p\)

周期:\(\frac{p^p - 1}{p - 1}\)

\(10\) 个 Bell 数:\(B_0 = 1\), \(B_1 = 1\), \(B_2 = 2\), \(B_3 = 5\), \(B_4 = 15\), \(B_5 = 52\), \(B_6 = 203\), \(B_7 = 877\), \(B_8 = 4140\), \( B_9 = 21147\)

Bell 数预处理:时间复杂度 \(O(n^2)\), 空间复杂度 \(O(n)\)

求第 \(n\) 个 Bell 数模任意素数 \(p\)

构造 \(p \times p\) 的矩阵,矩阵快速幂。时间复杂度 \(O(p^3log(n/p))\)

预处理 \(B_0\sim B_p\),将 \(n\) 转换成 \(p\) 进制,\(n = a_0 + a_1p + a_2p^2 + \dots + a_{lim}p^{lim}\),设 \(d_{i, j}(k)\) 表示 \(B_{jp^i + k + a_1p + \dots + a_{i - 1}p^{i - 1}}\),则答案为 \(d_{lim, a_{lim}}(a_0)\)。时间复杂度 \(O(p^2log_pn)\)

comments powered by Disqus