貝爾數(shù) Bell NumbersOI 中的集合劃分計(jì)數(shù)與高效計(jì)算【免費(fèi)下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內(nèi)含炫酷算術(shù)魔法項(xiàng)目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki貝爾數(shù) $B_n$ 是組合數(shù)學(xué)中一組以數(shù)學(xué)家埃里克·坦普爾·貝爾Eric Temple Bell命名的整數(shù)數(shù)列刻畫的是「將 $n$ 個(gè)互不相同的元素劃分為若干非空子集」的方案總數(shù)。本文圍繞 docs/math/combinatorics/bell.md 的核心內(nèi)容展開系統(tǒng)梳理貝爾數(shù)的定義、遞推公式、貝爾三角形構(gòu)造以及基于指數(shù)生成函數(shù)與多項(xiàng)式 $\exp$ 的 $O(n\log n)$ 計(jì)算方法并補(bǔ)充倉庫中第二類斯特林?jǐn)?shù)、EGF 與多項(xiàng)式運(yùn)算的源碼級(jí)依據(jù)幫助讀者在 OI/ICPC 競賽中快速識(shí)別、推導(dǎo)并實(shí)現(xiàn)貝爾數(shù)相關(guān)問題。定義集合劃分的計(jì)數(shù)貝爾數(shù)$B_n$ 是基數(shù)為 $n$ 的集合的劃分方法數(shù)目OEIS A000110數(shù)列開頭為$$ B_0 1,B_1 1,B_22,B_35,B_415,B_552,B_6203,\dots $$所謂「集合 $S$ 的一個(gè)劃分」是指 $S$ 的兩兩不相交的非空子集的族且它們的并恰好是 $S$。以 $B_3 5$ 為例3 個(gè)元素的集合 ${a, b, c}$ 共有 5 種不同的劃分方法$$ \begin{aligned} { {a},{b},{c}} \ { {a},{b,c}} \ { {b},{a,c}} \ { {c},{a,b}} \ { {a,b,c}} \ \end{aligned} $$注意劃分中的子集之間互不區(qū)分因此 ${{a},{b,c}}$ 與 ${{b,c},{a}}$ 被視為同一種劃分同時(shí)每個(gè)子集必須非空。$B_0 1$ 是因?yàn)榭占『弥挥?1 種劃分即不劃分任何子集的空族。遞推公式及其組合證明貝爾數(shù)滿足如下的遞推公式$$ B_{n1}\sum_{k0}^n\binom{n}{k}B_{k} $$證明組合意義設(shè) $B_n$ 對(duì)應(yīng)的集合為 ${b_1,b_2,b_3,\dots,b_n}$$B_{n1}$ 對(duì)應(yīng)的集合為 ${b_1,b_2,b_3,\dots,b_n,b_{n1}}$即 $B_{n1}$ 是在 $B_n$ 的基礎(chǔ)上增添了一個(gè)新元素 $b_{n1}$。圍繞新元素 $b_{n1}$ 的歸屬分類討論若它被單獨(dú)分到一類剩余 $n$ 個(gè)元素的劃分?jǐn)?shù)為 $\dbinom{n}{n}B_{n}$若它和某 1 個(gè)元素分到一類先從 $n$ 個(gè)元素中選出這 1 個(gè)元素$\binom{n}{n-1}$ 種選擇等價(jià)于選出與它同組的元素后剩余 $n-1$ 個(gè)元素自由劃分方案數(shù)為 $\dbinom{n}{n-1}B_{n-1}$若它和某 2 個(gè)元素分到一類方案數(shù)為 $\dbinom{n}{n-2}B_{n-2}$……對(duì) $k$ 從 $0$ 到 $n$ 求和即得遞推公式。該公式本質(zhì)上是按新元素所在塊的規(guī)模進(jìn)行分類的計(jì)數(shù)是貝爾數(shù)一切遞推性質(zhì)的基石。與第二類斯特林?jǐn)?shù)的關(guān)系每個(gè)貝爾數(shù)都是相應(yīng)第二類斯特林?jǐn)?shù)之和$$ B_{n} \sum_{k0}^n{n\brace k} $$這是因?yàn)榈诙愃固亓謹(jǐn)?shù) $\begin{Bmatrix}n\ k\end{Bmatrix}$也稱斯特林子集數(shù)見 docs/math/combinatorics/stirling.md恰好表示「將基數(shù)為 $n$ 的集合劃分為正好 $k$ 個(gè)非空子集的方法數(shù)目」。由于集合的劃分可以包含任意數(shù)量的非空塊把 $k 0, 1, \dots, n$ 的所有方案數(shù)累加就得到了不分塊數(shù)的總劃分?jǐn)?shù) $B_n$。第二類斯特林?jǐn)?shù)自身滿足遞推$$ \begin{Bmatrix}n\ k\end{Bmatrix}\begin{Bmatrix}n-1\ k-1\end{Bmatrix}k\begin{Bmatrix}n-1\ k\end{Bmatrix} $$其組合含義為插入新元素時(shí)要么單獨(dú)放入一個(gè)新子集$\begin{Bmatrix}n-1\ k-1\end{Bmatrix}$要么放入某個(gè)已有的非空子集$k\begin{Bmatrix}n-1\ k\end{Bmatrix}$。借助該遞推可以在 $O(nk)$ 時(shí)間內(nèi)先算出同一行的斯特林?jǐn)?shù)再對(duì) $k$ 求和得到貝爾數(shù)這也為不引入生成函數(shù)時(shí)的樸素實(shí)現(xiàn)提供了思路。貝爾三角形逐行遞推的實(shí)用構(gòu)造貝爾數(shù)還可以通過一種形式類似楊輝三角形的三角矩陣來遞推求出。構(gòu)造規(guī)則如下$a_{0,0} 1$對(duì)于 $n \ge 1$第 $n$ 行首項(xiàng)等于上一行的末項(xiàng)即 $a_{n,0}a_{n-1,n-1}$對(duì)于 $m,n \ge 1$第 $n$ 行第 $m$ 項(xiàng)等于它左邊和左上角兩個(gè)數(shù)之和即 $a_{n,m}a_{n,m-1}a_{n-1,m-1}$。部分結(jié)果如下$$ \begin{aligned} 1 \ 1\quad\qquad 2 \ 2\quad\qquad 3\quad\qquad 5 \ 5\quad\qquad 7\quad\qquad 10,,,\qquad 15 \ 15,,,\qquad 20,,,\qquad 27,,,\qquad 37,,,\qquad 52 \ 52,,,\qquad 67,,,\qquad 87,,,\qquad 114\qquad 151\qquad 203\ 203\qquad 255\qquad 322\qquad 409\qquad 523\qquad 674\qquad 877 \ \end{aligned} $$每行的首項(xiàng) $a_{n,0}$ 就是貝爾數(shù) $B_n$因此利用該三角形可以從 $O(n)$ 的空間、$O(n^2)$ 的時(shí)間逐行推出前 $n$ 個(gè)貝爾數(shù)。注意每一行的末項(xiàng)恰好等于下一行的首項(xiàng)這正是三角形「行首接行尾」的鋸齒狀銜接結(jié)構(gòu)。參考實(shí)現(xiàn)來自 docs/math/combinatorics/bell.md 的參考實(shí)現(xiàn)適用于 $n \le 2000$ 左右、值在所選類型范圍內(nèi)的情況數(shù)值更大時(shí)需換用高精度或模意義下的寫法constexpr int MAXN 2000 5; int bell[MAXN][MAXN]; void f(int n) { bell[0][0] 1; for (int i 1; i n; i) { bell[i][0] bell[i - 1][i - 1]; for (int j 1; j i; j) bell[i][j] bell[i - 1][j - 1] bell[i][j - 1]; } }MAXN 2000 5 bell [[0 for i in range(MAXN 1)] for j in range(MAXN 1)] def f(n): bell[0][0] 1 for i in range(1, n 1): bell[i][0] bell[i - 1][i - 1] for j in range(1, i 1): bell[i][j] bell[i - 1][j - 1] bell[i][j - 1]實(shí)現(xiàn)要點(diǎn)外層循環(huán)第 $i$ 行先利用上一行末項(xiàng)確定行首再逐列按「左 左上」遞推最終 $B_n$ 位于bell[n][0]。若只需輸出一行可將二維數(shù)組滾動(dòng)優(yōu)化為一維但需注意行首值取自上一行末項(xiàng)滾動(dòng)時(shí)需暫存該值。指數(shù)生成函數(shù)封閉形式的推導(dǎo)貝爾數(shù)求和式與 $\binom{n}{k}$ 的卷積結(jié)構(gòu)暗示了使用**指數(shù)生成函數(shù)EGF**的動(dòng)機(jī)——指數(shù)生成函數(shù)的定義與乘法性質(zhì)參見 docs/math/poly/egf.md序列 $\langle a_n\rangle$ 的 EGF 定義為 $\hat F(x)\sum_n a_n \frac{x^n}{n!}$其乘法對(duì)應(yīng)二項(xiàng)卷積 $\sum_{i0}^n\binom{n}{i}a_i b_{n-i}$。設(shè)貝爾數(shù)的指數(shù)生成函數(shù)為$$ \hat B(x) \sum_{n 0}^{\infty}\frac{B_n}{n!}x^n $$展開并求導(dǎo)得$$ \begin{aligned} \hat B(x) 1 \sum_{n 0}^{\infty}\frac{B_{n1}}{(n 1)!}x^{n 1} \ \hat B(x) \sum_{n 0}^{\infty}\frac{B_{n1}}{n!}x^{n} \end{aligned} $$由貝爾數(shù)的遞推公式 $B_{n1}\sum_{k0}^n\binom{n}{k}B_k$兩邊同除以 $n!$ 可得$$ \frac{B_{n1}}{n!} \sum_{k 0}^{n}\frac{1}{(n-k)!}\frac{B_{k}}{k!} $$右側(cè)正是序列 $\left\langle \dfrac{1}{n!} \right\rangle$ 與 $\left\langle \dfrac{B_n}{n!} \right\rangle$ 的卷積因此$$ \hat B(x) \mathrm{e}^x \hat B(x) $$解這個(gè)一階常微分方程$$ \hat B(x) \exp\left(\mathrm{e}^x C\right) $$利用初值條件當(dāng) $x 0$ 時(shí) $\hat B(0) B_0 1$代入得 $C -1$最終得到貝爾數(shù)指數(shù)生成函數(shù)的封閉形式$$ \boxed{\ \hat B(x) \exp\left(\mathrm{e}^x - 1\right)\ } $$高效計(jì)算多項(xiàng)式 exp 與 O(n log n) 算法由封閉形式 $\hat B(x)\exp(\mathrm{e}^x-1)$ 可以得到一條計(jì)算貝爾數(shù)前 $n$ 項(xiàng)的高效路徑預(yù)處理$\mathrm{e}^x - 1$ 的前 $n$ 項(xiàng)即序列 $\langle 0, 1, \frac{1}{2!}, \frac{1}{3!}, \dots \rangle$因?yàn)?$\mathrm{e}^x\sum_{n\ge0}\frac{x^n}{n!}$常數(shù)項(xiàng) $1$ 減去后首項(xiàng)為 $0$——這恰好滿足多項(xiàng)式 $\exp$ 對(duì)常數(shù)項(xiàng)必須為 $0$ 的收斂條件對(duì)該多項(xiàng)式做一次多項(xiàng)式 $\exp$得到 $\hat B(x)$ 的前 $n$ 項(xiàng)系數(shù) $\dfrac{B_n}{n!}$逐項(xiàng)乘以 $n!$ 還原出 $B_0, B_1, \dots, B_{n-1}$。其中多項(xiàng)式 $\exp$ 的實(shí)現(xiàn)可見 docs/math/poly/elementary-func.md通過求導(dǎo)得到 $\frac{\mathrmlkmzxhr \exp{f(x)}}{\mathrmvyanpor x} \equiv \exp{f(x)}f(x)\pmod{x^{n}}$比較系數(shù)后使用Newtons Method牛頓迭代求解時(shí)間復(fù)雜度為 $O(n\log n)$普通分治 FFT 做法為 $O(n\log^2 n)$。從該文檔的參考實(shí)現(xiàn)可以看到polyexp的核心是迭代式$$ f f_0\left(1 - \ln f_0 h\right) $$其中每一步需要調(diào)用一次多項(xiàng)式求 $\ln$求導(dǎo) 求逆 卷積。因此求貝爾數(shù)前 $n$ 項(xiàng)的時(shí)間復(fù)雜度瓶頸正是多項(xiàng)式 $\exp$總復(fù)雜度可做到 $O(n\log n)$。數(shù)值范圍與競賽實(shí)戰(zhàn)提醒貝爾數(shù)增長極快從首項(xiàng) $B_01, B_11, B_22, B_35, B_415, B_552, B_6203$ 可見其增長速度遠(yuǎn)超指數(shù)級(jí)實(shí)際應(yīng)用中 $B_n$ 通常需要取模OI 中常用模數(shù)如 $998244353$其原根為 $3$見 docs/math/combinatorics/stirling.md 中多項(xiàng)式類的取模設(shè)定或使用高精度。方法選型$n$ 較小如 $n \le 2000$時(shí)貝爾三角形遞推 $O(n^2)$ 簡單可靠$n$ 較大如 $n \ge 10^5$時(shí)應(yīng)使用生成函數(shù) 多項(xiàng)式 $\exp$ 的 $O(n\log n)$ 做法。與斯特林?jǐn)?shù)的聯(lián)動(dòng)題目若給出「恰好劃分成 $k$ 個(gè)塊」的約束應(yīng)轉(zhuǎn)向第二類斯特林?jǐn)?shù)只有不限制塊數(shù)時(shí)才退化為貝爾數(shù)。兩者結(jié)合可覆蓋絕大多數(shù)「集合劃分」類計(jì)數(shù)問題。參考文獻(xiàn)docs/math/combinatorics/bell.md貝爾數(shù)定義、遞推、貝爾三角形與 EGF 推導(dǎo)的原始出處docs/math/combinatorics/stirling.md第二類斯特林?jǐn)?shù)的遞推式、通項(xiàng)公式與同一行計(jì)算docs/math/poly/egf.md指數(shù)生成函數(shù)的定義與乘法二項(xiàng)卷積性質(zhì)docs/math/poly/elementary-func.md多項(xiàng)式對(duì)數(shù)/指數(shù)函數(shù)的求解與牛頓迭代實(shí)現(xiàn)維基百科 Bell number 詞條原文所引用的外部參考資料【免費(fèi)下載鏈接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戲線上攻略內(nèi)含炫酷算術(shù)魔法項(xiàng)目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考