貝爾數

\(B_n\) 是集合大小為 \(n\) 的集合的劃分數目，注意這里劃分成多少個集合都是可以的。根據貝爾數的定義我們就可以得到貝爾數和第二類斯特林數之間的關系：

\[\sum\limits_{i=0}^nS(n,i)=B_n \]

遞推公式

貝爾數有遞推公式：

\[B_n=\sum\limits_{i=0}^{n-1}\dbinom{n-1}{i}B_i \]

考慮如何證明這個式子。我們考慮第 \(n\) 個元素，如果它與 \(k\) 個元素劃分到一個集合中去，那么我們要做的就是把剩下的 \(n-k-1\) 個元素進行劃分，方案數就是 \(\binom{n-1}{k}B_{n-k-1}=\binom{n}{n-k-1}B_{n-k-1}\) 由此不難得出原式。

性質

\(B_{n+m}=\sum_{j=0}^m\sum_{i=0}^nj^{n-i}\left\{ m\atop j \right\}\binom{n}{i}B_i\)

證明：我們考慮這個式子的組合意義，這 \(m\) 個元素怎么分配，枚舉 \(j\) 表示分配到 \(j\) 個集合里，然后考慮這 \(n\) 個元素如何分配，我們枚舉 \(i\) 個單獨分配，分配方案就是 \(B_i\)，然后把剩下的放在那 \(j\) 個集合里，方案數為 \(j^{n-i}\)。所以這個式子成立。

Touchard 同余：\(B_{p+n}\equiv B_n+B_{n+1}\bmod p\)

根據第二類斯特林數的遞推公式：

\[\left\{ n\atop m \right\} = \frac{1}{m!}\sum\limits_{i=0}^m(-1)^i\binom{m}{i}(m-i)^n \]

我們可以得到，當 \(n\) 為質數時，\(1<m<n\) 時有 \(\left\{ n\atop m \right\}\equiv 0\bmod n\) 成立。具體證明在博主的另一篇博客《斯特林數與斯特林反演中》提到，這里不再贅述。

我們用第一條性質把 \(B_{n+p}\) 展開得到：

\[\begin{aligned} B_{n+p}=\sum\limits_{i=0}^n\sum\limits_{j=0}^pj^{n-i}\left\{ p\atop j \right\}\binom{n}iB_i\\ =\sum\limits_{j=0}^p\left\{ p\atop j \right\}\sum\limits_{i=0}^nj^{n-i}\binom{n}iB_i\\ \end{aligned} \]

根據第二類斯特林數上面所述的性質，在 \(\bmod\ p\) 意義下，當 \(1<j<p\) 時為 \(0\)，而當 \(j=0\) 時根據第二類斯特林數的定義，也為 \(0\)，所以上面這個式子可以化簡如下：

\[\begin{aligned} &\equiv \left\{ p\atop 1 \right\}\sum\limits_{i=0}^n\binom{n}{i}B_i+\left\{ p\atop p\right\}\sum\limits_{i=0}^np^{n-i}\binom{n}{i}B_i\\ &\equiv B_{n+1}+B_n \end{aligned} \]

后面那個式子之所以成立是因為當且僅當 \(i=n\) 的時候后面那個式子才不會被 \(\bmod\ p\) 給模掉。

\(\sum_{r=0}^k(-1)^r\binom{k}{r} B_{n-r+1}=\sum_{r=0}^{n-k}\binom{n-k}{r}B_{n-r}\)

注意到 \(k=0\) 時的情況是平凡的。我們考慮對 \(k\) 歸納證明，我們分別讓 \(F(n,k)\) 等于等號兩邊的式子，通過對兩邊都進行證明 \(F(n,k)-F(n-1,k)=F(n,k+1)\) 就可以證明。

這里只證明等號左邊滿足這個式子，等號右邊同理。

設 \(F(n,k)=\sum_{r=0}^k(-1)^r\binom kr B_{n-r+1}\)，那么我們可以得到：

\[\begin{aligned} &F(n-1,k)+F(n,k+1)\\&=\sum\limits_{r=0}^k(-1)^r\binom kr B_{n-r}+\sum\limits_{r=0}^{k+1}(-1)^r\binom { k+1}{r}G_{n-r+1}\\ &=G_{n+1}+\sum\limits_{r=1}^{k+1}(-1)^r\binom kr G_{n-r+1}=F(n,k) \end{aligned} \]

\(B_{n+p^m}\equiv mB_n+B_{n+1}\bmod p\)

這個式子可以看作是上面那個式子的一個擴展，我們同樣利用第一條性質把這個東西展開得到：

\[B_{n+p^m}=\sum_{j=0}^{n}\sum_{i=0}^{p^m}j^{p^m-i}\left\{ n\atop j \right\}\binom{p^m}{i}B_i \]

根據盧卡斯定理，我們可以得到 \(\binom{p^m}{r}\equiv 0\bmod p(0<r<p^m)\)，所以上面這個式子在 \(\bmod \ p\) 意義下就可以寫成：

\[\begin{aligned} B_{n+p^m}&\equiv\sum\limits_{j=0}^n \left\{ n\atop j \right\}(j^{p^m}B_0+B_{p^m})\\ &\equiv \sum\limits_{j=0}^n\left\{ n\atop j \right\}(j+B_{p^m}) \end{aligned} \]

通過讓性質 \(1\) 的 \(n=1\) 我們可以得到一個式子：

\[B_{1+m}=\sum\limits_{j=0}^m(j+1)\left\{ m\atop j \right\} \]

所以我們可以得到：

\[\begin{aligned} B_{n+p^m}&\equiv (B_{p^n}-1)\sum\limits_{j=0}^n\left\{ n\atop j \right\}+\sum\limits_{j=0}^n(j+1)\left\{ n\atop j \right\}\\ &=(B_{p^m}-1)\sum\limits_{j=0}^n\left\{ n\atop j \right\}+B_{n+1}\\ &=(B_{p^m}-1)B_n+B_{n+1} \end{aligned} \]

所以現在我們只需要證明下面這個結論：

\[B_{p^m}\equiv m+1 \bmod p \]

我們考慮如何證明，這里會用得到一點抽象代數中的定義，不過基本還是初等方法。

這里 \(\Bbb{Z}/p^m\Bbb{Z}\) 指的是 \(p^m\) 的完全剩余系。對于 \(x,y \in \Bbb{Z}/p^m\Bbb{Z}\)，定義 \(f_y(x)=x+y\bmod p^m\)，設 \(P\) 是這個剩余系的一個劃分，那么 \(f_y(P)\) 表示的就是對這個劃分中的每一個集合的每一個元素進行操作所得到的劃分，于是 \(f_y(P)\) 就可以理解成一個類似于置換的東西。設 \(X=\{f_y(x)|y\in \Bbb{Z} \}\)，定義一個劃分 \(P\) 為不動的指的是 \(\forall f_y(x)\in X,P=f_y(P)\) .其實這個東西等價于 \(P=f_y(P)\)。同樣我們也可以定義不動的劃分，有以下性質：任何非不動的劃分必然屬于一個大小為 \(P\) 的正整數冪的軌道。

容易發現這個軌道的大小就是最小的 \(k\) 滿足 \(f_k(P)=P\)，我們已經知道有 \(f_{p^m}=P\)，這其實就是一個不斷執行 \(p^m\) 次 \(f_1\) 的過程，我們可以形象的把這個過程看做一個環，那么我們在這個環上走 \(p^m\) 次一定能夠走回源點，那么這也就是說，環的長度一定能夠乘除 \(p^m\)，而在非不動的意義下，我們也可以得到 \(f_1(P)\not=P\)，所以我們最終可以得到以上性質，這告訴我們，所有非不動的劃分的數量可以被 \(p\) 整除，這也就是說，總的劃分數量，即 \(B_{p^m}\)，和不動的劃分的數量在模 \(p\) 的意義下相等。

假設一個劃分 \(P\) 是不動的，\(a,b\) 分別在這個劃分的某個集合中 \(A,B\) 中，明顯 \(f_{b-a}(a)=b\) 又因為這個劃分是不動的，所以我們有 \(f_{b-a}(A)=B\)，因此在一個不動的劃分中，所有劃分出的集合大小都相等，不妨設為 \(p^j\)，我們考慮證明這個劃分有以下性質：在一個集合中的所有元素模 \(p^{m-j}\) 都相同。

我們用反證法來證明這個性質，設 \(P\) 是一個不動的劃分，\(A\in P\) 且 \(a,b\in A\)，并且 \(a\not\equiv b\bmod p^{m-j}\) 所以 \(f_{b-a}(a)=b\)，所以 \(f_{b-a}\) 是一個把 \(A\) 映射到 \(A\) 的映射，因此對于任意的正整數 \(r\)，我們有 \(f_{r(b-a)}(a)\) 為 \(A\) 中的某個元素，顯然 \(f_{r(b-a)}(a)\equiv f_{s(b-a)}(a)\bmod p^{m}\)，當且僅當 \(a+r(b-a)\equiv a+s(b-a)\bmod p^m\)，有假設可知 \(r\equiv s\)，因此對于 \(1\le r\le p^{j+1}\) \(f_{r(b-a)}(a)\) 都是不同的元素，這表明 \(|A|>p^j\) 矛盾。

于是這告訴我們，對于劃分中的集合大小都為 \(p^j\) 的不動的劃分，它是唯一的。于是這樣的集合個數就為 \(m+1\) 個，于是我們可以得到 \(B_{p^m}\equiv m+1\)。由此上面的性質得以證明。

設 \(B^n=B_n\) 也就是說我們規定了一個符號。

我們考慮證明一個更強的性質：\(B_{kp^s+n}\equiv B^n(B+s)^k\)

我們考慮證明當 \(s\) 固定的時候，對于所有的 \(k\) 和 \(n\) 上面這個式子成立，我們考慮對 \(k\) 進行歸納，當 \(k=1\) 的時候我們已經證明這個是對的，則：

\[B_{(k+1)p^s+n}\equiv B_{kp^s+p^s+n}\equiv B^{p^s+n}(B+s)^k\equiv B^n(B+s)^{k+1} \]

由此我們可以得到這個性質成立。

其實如果我們不知道 \(k=1\) 的時候式子成立也可以證明，我們考慮這個式子在 \(s=0\) 的時候顯然成立，我們考慮取 \(k=1\) 對 \(s\) 進行歸納也可以證明這個式子的正確性。

由此我們可以在把這個同余性質加強一下，貝爾數滿足：

\[G_{\sum k_rp^r}\equiv \prod(G+r)^{k_r} \]

證明這個式子，只需要把上面那個更強的式子進行迭代使用。

由此我們可以得到這樣的一個式子：

\[G_{\frac{p^p-1}{p-1}+n}\equiv G_n\bmod p \]

證明：

\[G_{\frac{p^p-1}{p-1}+n}\equiv G_{p^{p-1}+p^{p-2}+...1+n}\equiv G^{n+1}(G+p-1)...(G+1) \]

不難發現這就是一個下降冪的形式，根據第二類斯特林數的性質，我們可以得到：

\[G^{n+1}(G^{p-1}-1)=G^{n+p}-G^{n+1}=G_n \]

所以我們可以得到以下的性質：

貝爾數模素數 \(p\) 的周期為 \(\frac{p^p-1}{p-1}\)

貝爾三角形

我們可以通過構造貝爾三角形來得到貝爾數，具體方法如下：\(b_{1,1}=1\)，\(b_{k,1}=b_{k-1,k-1}\)，\(b_{x,y}=b_{x,y-1}+b_{x-1,y-1}\)。

這樣構造，每一行的第一個數就是貝爾數，即 \(b_{k,1}=B_k\)。

這樣構造的原因如下：

我們知道：\(\Delta B_m=B_{m+1}-B_m\)，不難發現并證明：

\[\Delta^n B_m=\sum\limits_{k=0}^n(-1)^{n-k}\binom{n}{k}B_{m+k} \]

我們令 \(m=1\) 可以得到：

\[\begin{aligned} \Delta^nB_1&=\sum\limits_{k=0}^n(-1)^{n-k}\binom{n}{k}B_{k+1}\\ &=\sum\limits_{k=0}^n(-1)^{n-k}\binom{n}{k}\sum\limits_{j=0}^k\binom{k}{j}B_j\\ &=\sum\limits_{j=0}^n\sum\limits_{k=j}^n(-1)^{n-k}\binom{n}{k}\binom{k}{j}B_j\\ &=\sum\limits_{j=0}^nB_j\binom{n}{j}\sum\limits_{k=j}^n(-1)^{n-k}\binom{n-k}{k-j}\\ &=\sum\limits_{j=0}^nB_j\binom nj \sum\limits_{j=0}^{n-k}(-1)^j\binom{n-k}j\\ &=\sum\limits_{j=0}^nB_j\binom nj [k=n]=B_n \end{aligned} \]

那么我們就可以利用差分公式計算貝爾數。

這個公式提示我們，如果我們按照上面的方式去構造貝爾數的話，不難發現前幾項的規律，把沒一行的最后一個數往前拆，就會發現這個東西其實就是 \(\Delta^n B_1\)。其實就是不斷往下做差分的過程。我們看這個三角形的局部：

  1
  1 2
  2 3 5
  5 7 10 15
  15 20 27 37 52

就會發現下一行的差分是這一行。

那么這個三角形怎么理解呢？我們這樣來理解，設 \(a_{i,j}\) 表示第 \(i\) 行的第 \(j\) 個數，我們首先來看第一列，不難發現，這一列數全部是 \(\Delta^n B_1\)，然后第二列數，不難發現，這一列數全是 \(\Delta^n B_2\)，后面依次類推，那么它是怎么保持這種性質的呢？原因在于：

\[B_n=\Delta B_{n-1}+B_{n-1}\Rightarrow \Delta^{n} B_n=\Delta^{n+1} B_{n-1}+\Delta^n B_{n-1} \]

注意我們消除而加上 \(\Delta\) 算子必須要滿足的條件是我們應用的式子沒有依靠于這個數列的特殊性質。

由上面這個式子可以知道遞推式子成立，再由 \(\Delta^n B_1=B_n\) 就可以知道我們把每一行的最后一個數抄下來當做第一行的第一個數的原因了。

生成函數

設貝爾數的 EGF 為 \(f(x)\)，由此我們可以得到：

\[f(x)=\sum\limits_{i\ge0}\frac{B_i}{i!}x^i \]

我們對上面這個東西進行求導可以得到：

\[\begin{aligned} f'(x)&=\sum\limits_{i\ge 0}\frac{B_{i+1}}{i!}x^i\\ &=\sum\limits_{i\ge 0}\frac{x^i}{i!}\sum\limits_{i\ge j}\binom{i}{j}B_j\\ &=\sum\limits_{j\ge 0}\frac{B_jx^j}{j!}\sum\limits_{i\ge j}\frac{x^{i-j}}{(i-j)!}\\ \end{aligned} \]

眾所周知，我們把 \(e^x\) 在原點處的泰勒展開式寫出來可以得到：

\[e^x=\sum\limits_{i\ge 0}\frac{x^i}{i!} \]

把 \(e^{ix}\) 在原點處的泰勒展開式寫出來可以得到：

\[e^{ix}=\sum\limits_{j\ge 0}\frac{x^ji^j}{j!} \]

所以原式我們可以繼續寫得到：

\[LHS=\sum\limits_{j\ge 0}\frac{B_jx_j}{j!}e^x=f(x)e^x \]

由此我們可以得到 \(f(x)\) 的封閉形式為 \(f(x)=e^{e^x+c}\)。由 \(f(0)=1\) 我們可以得到 \(c=-1\)，所以 \(f(x)=e^{e^x-1}\)。

至此我們得到貝爾數 EGF 的封閉形式。

設 \(g(x)=e^{e^x}\)，我們把指數上的 \(e^x\) 看做一個整體，然后我們可以得到 \(e^{e^x}=\sum_{i\ge 0}\frac{e^{xi}}{i!}\)

所以我們可以得到 \(f(x)=\frac 1e g(x)=\frac 1e \sum_{i\ge 0}\frac{e^{xi}}{i!}\)。

我們繼續推可以得到：

\[\begin{aligned} LHS&=\frac 1e \sum\limits_{i\ge 0}\frac{e^{xi}}{i!}\\ &=\frac 1e \sum\limits_{i\ge 0}\frac{1}{i!}\sum\limits_{j\ge 0}\frac{i^jx^j}{j!}\\ &=\frac 1e \sum\limits_{j\ge 0}\frac{x^j}{j!}\sum\limits_{i\ge 0}\frac{i^j}{i!} \end{aligned} \]

我們去式子兩邊 \(\frac{x^n}{n!}\) 的系數，就可以得到：\(B_n=\frac 1e\sum_{i\ge 0}\frac{i^n}{i!}\)（Dobinski公式）。

引用

知乎回答
高等組合學筆記(七): Bell數,第一,二類Stirling數及其遞推關系_zorchp-CSDN博客
論文《AN ELEMENTARY (NUMBER THEORY) PROOF OF TOUCHARD’S CONGRUENCE》
論文《numbers generated by the function \(e^{e^x-1}\)》

posted @ 2023-07-13 21:06 NuclearReactor 閱讀(337) 評論(0) 收藏舉報

刷新頁面返回頂部

HeNuclearReactor

貝爾數

遞推公式

性質

貝爾三角形

生成函數

引用

公告