第二類 Stirling 數與貝爾數

本文的閱讀等級:中級

考慮這個組合數學問題:包含 n 個元素的集合 \Psi=\{1,2,\ldots,n\} 劃分為 k 個等價類的方法數是多少?也就是說,總共有多少種方式將集合 \Psi 劃分為 k 個兩兩不交集的非空子集?以符號 \begin{Bmatrix}n\\k\end{Bmatrix}S(n,k) 代表此數,稱之為第二類 Stirling 數 (因蘇格蘭數學家 James Stirling 而得名[1])。明顯地,\begin{Bmatrix} n\\ 1 \end{Bmatrix}=\begin{Bmatrix} n\\ n \end{Bmatrix} =1。看一個 k=2 的例子,\{1,2,3,4\} 劃分為 2 類的所有可能方式如下:

\displaystyle\begin{array}{llll} \{12\}\cup\{34\},&\{13\}\cup\{24\},&\{14\}\cup\{23\},&\{123\}\cup\{4\},\\ \{124\}\cup\{3\},&\{134\}\cup\{2\},&\{1\}\cup\{234\};&\end{array}

因此,\begin{Bmatrix}4\\2\end{Bmatrix} =7。考慮集合 \{1,2,3,4\} 加入數字 5,區分為兩個情況:數字 5 單獨構成一類,只有 \{1234\}\cup\{5\} 一種劃分法;數字 5 加入上面的 7 種劃分的其中一個等價類,共有 2\times 7=14 種可能。所以,\begin{Bmatrix} 5\\2 \end{Bmatrix} =1+2\cdot 7=15。重複此程序可以歸納出 \begin{Bmatrix} n\\2\end{Bmatrix} =2^{n-1}-1。不過,這個演繹過程不容易推廣至 k>2。下面我們運用母函數 (生成函數,generating function) 方法推導第二類 Stirling 數的顯式表達式。

 
首先我們找出 \begin{Bmatrix}n\\k\end{Bmatrix} 的遞迴關係式。令 \Psi=\{1,2,\ldots,n\}p\in\Psi。集合 \Psi 劃分為 k 類可分開兩種情況討論:若 p 單獨構成一類,則 \Psi-\{p\} 劃分出 k-1 類的方法數為 \begin{Bmatrix}n-1\\k-1\end{Bmatrix};若 p 與其他元素構成一類,先令 \Psi-\{p\} 劃分出 k 類,再讓 p 加入其中任一類,故共有 k\begin{Bmatrix} n-1\\k\end{Bmatrix} 種可能。合併以上結果,可得遞迴關係式

\displaystyle \begin{Bmatrix} n\\ k \end{Bmatrix}=\begin{Bmatrix} n-1\\ k-1 \end{Bmatrix}+k\begin{Bmatrix} n-1\\ k \end{Bmatrix},~~k>0

定義初始值 \begin{Bmatrix} 0\\ 0 \end{Bmatrix} =1,且若 n>0\begin{Bmatrix} n\\ 0 \end{Bmatrix}=\begin{Bmatrix} 0\\ n \end{Bmatrix} =0

 
應用母函數方法於解析遞迴關係式的顯式表達式的標準程序如下 (見“遞迴關係式的母函數解法”):

  1. 定義母函數 G(x)
  2. 遞迴關係式等號兩邊同乘 x^n,再將所有定義良好的 n 加總。
  3. 將等號左邊和右邊分別以母函數 G(x) 明確表示,解出未知的 G(x)
  4. 利用部分分式分解或其他方法 (如泰勒展開式) 將 G(x) 展開成冪級數。

 
第一步要定義數列 \begin{Bmatrix}n\\k\end{Bmatrix} 的普通母函數,有兩種選擇:

\displaystyle\begin{aligned} A_n(x)&=\sum_{k=0}^\infty\begin{Bmatrix} n\\ k\end{Bmatrix}x^k\\ B_k(x)&=\sum_{n=0}^\infty\begin{Bmatrix} n\\ k\end{Bmatrix}x^n.\end{aligned}

下面先嘗試推導 A_n(x)n\ge 0。固定 n,遞迴關係式等號兩邊乘以 x^k,再將所有的 k 加總,可得

\displaystyle\begin{aligned} A_n(x)&=\sum_{k=0}^\infty\begin{Bmatrix} n-1\\ k-1 \end{Bmatrix}x^k+\sum_{k=0}^\infty k\begin{Bmatrix} n-1\\ k \end{Bmatrix}x^k\\ &=xA_{n-1}(x)+\left(x\frac{d}{dx}\right)A_{n-1}(x)\\ &=\left[x(1+D_x)\right]A_{n-1}(x),\end{aligned}

其中 D_x=\frac{d}{dx} 是微分算子。因為 A_0(x)=1

\displaystyle A_n(x)=[x(1+D_x)]^n1,~~n\ge 0

計算可得

\displaystyle\begin{aligned} A_1(x)&=x\\ A_2(x)&=x+x^2\\ A_3(x)&=x+3x^2+x^3\\ A_4(x)&=x+7x^2+6x^3+x^4\\ &\vdots\end{aligned}

為便利說明,定義母函數 G(x)=\sum_{r=0}^\infty a_rx^r 的係數提取算子為 [x^r](G(x))=a_r。從母函數 A_n(x) 可知 \begin{Bmatrix} n\\ k \end{Bmatrix} =[x^k]\left(A_n(x)\right)。例如,\begin{Bmatrix} 4\\ 2 \end{Bmatrix} =[x^2](A_4(x))=7\begin{Bmatrix} 4\\ 3 \end{Bmatrix} =[x^3](A_4(x))=6。遺憾的是,我們並沒有解出 A_n(x) 的代數式,因此未能得到 \begin{Bmatrix} n\\ k \end{Bmatrix} 的顯式表達式。

 
考慮第二種普通母函數 B_k(x)k\ge 0。固定 k,遞迴關係式等號兩邊同乘以 x^n,再將所有的 n 加總在一起,即有

\displaystyle\begin{aligned} B_k(x)&=\sum_{n=0}^\infty\begin{Bmatrix} n-1\\ k-1 \end{Bmatrix}x^n+\sum_{n=0}^\infty k\begin{Bmatrix} n-1\\ k \end{Bmatrix}x^n\\ &=xB_{k-1}(x)+kxB_k(x).\end{aligned}

因為 B_0(x)=1,對於 k\ge 1

\displaystyle B_k(x)=\frac{x}{1-kx}B_{k-1}(x)=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}

利用部分分式分解,

\displaystyle \frac{1}{(1-x)(1-2x)\cdots(1-kx)}=\sum_{j=1}^k\frac{c_j}{1-jx}

欲解出未知係數 c_j1\le j\le k,等號兩邊同乘以 1-jx,代入 x=1/j,可得

\displaystyle\begin{aligned} c_j&=\prod_{i=1,i\neq j}^k\frac{1}{1-i/j}=\prod_{i=1,i\neq j}^k\frac{j}{j-i}\\ &=j^{k-1}\prod_{1\le i<j}\frac{1}{j-i}\prod_{j<i\le k}\frac{(-1)}{i-j}\\ &=(-1)^{k-j}\frac{j^{k-1}}{(j-1)!(k-j)!}.\end{aligned}

使用以上結果,對於 n\ge k,第二類 Stirling 數為

\displaystyle\begin{aligned} \begin{Bmatrix} n\\ k \end{Bmatrix}&=[x^n]\left(B_k(x)\right)=[x^n]\left(\frac{x^k}{\prod_{j=1}^k(1-jx)}\right)\\ &=[x^{n-k}]\left(\frac{1}{\prod_{j=1}^k(1-jx)}\right)=[x^{n-k}]\left(\sum_{j=1}^k\frac{c_j}{1-jx}\right)\\ &=\sum_{j=1}^kc_j[x^{n-k}]\left(\frac{1}{1-jx}\right)=\sum_{j=1}^kc_jj^{n-k}\\ &=\sum_{j=1}^k(-1)^{k-j}\frac{j^{k-1}}{(j-1)!(k-j)!}j^{n-k}=\sum_{j=1}^k(-1)^{k-j}\frac{j^n}{j!(k-j)!}. \end{aligned}

 
第二類 Stirling 數可以用來計算劃分 \Psi=\{1,2,\ldots,n\} 的所有可能方法數,稱為貝爾數 (Bell number,因 Eric Temple Bell 而得名[2]):

\displaystyle b_n=\sum_{k=0}^n\begin{Bmatrix} n\\ k \end{Bmatrix},~~n\ge 0

注意,b_0=1,我們默認空集合有一種劃分法,即其自身。貝爾數 \{b_n\}_0^\infty 的前幾項如下:

\displaystyle 1, 1, 2, 5, 15, 52, 203, \ldots

套用先前導出的 \begin{Bmatrix} n\\ k \end{Bmatrix} 計算公式,並設 0\le k\le m,這裡 m 可以是任一正整數,只要滿足 m\ge n>0 即可 (因為 \begin{Bmatrix} n\\ k \end{Bmatrix} =0,若 k>n)。對於 n>0,詳細的推演步驟如下:

\displaystyle\begin{aligned} b_n&=\sum_{k=1}^m\begin{Bmatrix} n\\ k \end{Bmatrix}=\sum_{k=1}^m\sum_{j=1}^k(-1)^{k-j}\frac{j^n}{j!(k-j)!}\\ &=\sum_{j=1}^m\frac{j^{n-1}}{(j-1)!}\sum_{k=j}^m\frac{(-1)^{k-j}}{(k-j)!}\\ &=\sum_{j=1}^m\frac{j^{n-1}}{(j-1)!}\left(\sum_{r=0}^{m-j}\frac{(-1)^{r}}{r!}\right).\end{aligned}

固定 nj,令 m\to\infty。因為 1/e=\sum_{r=0}^\infty (-1)^r/r!,可得貝爾數的無窮級數表達式

\displaystyle b_n=\frac{1}{e}\sum_{j=0}^\infty\frac{j^n}{j!},~~n>0

上式中,我們從 j=0 開始計數,因為當 n>00^n/0!=0/1=0

Eric Temple Bell (1883-1960) From http://www.daviddarling.info/images/Bell_Eric.jpg

 
貝爾數的無窮級數表達式並不適用於實際計算,不過它倒是提示了另一種母函數的表現形式。因為 e=\sum_{n=0}^\infty \frac{1}{n!},我們稱下列無窮級數為貝爾數 \{b_n\}_0^\infty 的指數母函數:

\displaystyle EG(x)=\sum_{n=0}^\infty \frac{b_n}{n!}x^n

b_n 的無窮級數表達式代入上式,化簡過程如下:

\displaystyle\begin{aligned} EG(x)&=1+\sum_{n=1}^\infty \frac{b_n}{n!}x^n=1+\frac{1}{e}\sum_{n=1}^\infty\frac{x^n}{n!}\sum_{j=1}^\infty\frac{j^{n-1}}{(j-1)!}\\ &=1+\frac{1}{e}\sum_{j=1}^\infty\frac{1}{j!}\sum_{n=1}^\infty \frac{(jx)^n}{n!}=1+\frac{1}{e}\sum_{j=1}^\infty\frac{1}{j!}(e^{jx}-1)\\ &=1+\frac{1}{e}\sum_{j=1}^\infty\frac{1}{j!}((e^x)^j-1)=1+\frac{1}{e}(e^{e^x}-e)=e^{e^x-1}.\end{aligned}

有趣的是,雖然貝爾數本身非常複雜,但它的指數母函數卻很簡單。

 
以往我們總是從遞迴關係式出發,透過推導母函數求出數列的顯式表達式。現在我們討論相反方向的論述──從貝爾數的無窮級數表達式出發,通過指數母函數來推導遞迴關係式。寫出

\displaystyle \sum_{n=0}^\infty \frac{b_n}{n!}x^n=e^{e^x-1}

為了簡化上式,等號兩邊計算對數,

\displaystyle \ln\left(\sum_{n=0}^\infty \frac{b_n}{n!}x^n\right)=e^x-1

緊接著我們希望去除對數運算。運用一點代數技巧,等號兩邊求導,並且通乘 x

\displaystyle \sum_{n=0}^\infty n\frac{b_n}{n!}x^n\left(\sum_{n=0}^\infty \frac{b_n}{n!}x^n\right)^{-1}=xe^x

也就有

\displaystyle \sum_{n=0}^\infty \frac{b_n}{(n-1)!}x^n=(xe^x)\sum_{n=0}^\infty \frac{b_n}{n!}x^n= x\left(\sum_{n=0}^\infty \frac{b_n}{n!}x^n\right)\left(\sum_{n=0}^\infty\frac{x^{n}}{n!}\right)

設法乘開上式等號右邊。使用柯西乘積 (Cauchy product,見“摺積與離散傅立葉轉換”)

\displaystyle \left(\sum_{n}p_nx^n\right)\left(\sum_nq_nx^n\right)=\sum_n\left(\sum_kp_kq_{n-k}\right)x^n

可得

\displaystyle \sum_{n=0}^\infty \frac{b_n}{(n-1)!}x^n=x\sum_{n=0}^\infty\left(\sum_{k=0}^n\frac{b_k}{k!(n-k)!}\right)x^n=\sum_{n=0}^\infty\left(\sum_{k=0}^n\binom{n}{k}\frac{b_k}{n!}\right)x^{n+1}

比較等號兩邊的 x^n 係數,即得貝爾數 \{b_n\}_0^\infty 的遞迴關係式

\displaystyle b_n=\sum_{k=0}^{n-1}\binom{n-1}{k}b_k,~~n\ge 1

上式可以如此解讀:從集合 \Psi=\{1,2,\ldots,n\} 移除一個包含數字 p (p\in\Psi) 的等價類,剩下的部分還有 k 個數字,範圍是 0\le k\le n-1。對於每一 k,我們有 \binom{n-1}{k} 種選擇 (因為必定不含 p),而每一種選擇又有 b_k 個可能的劃分方式。

 
以上演繹過程揭示了從指數母函數推演一數列的遞迴關係式的執行步驟:

  1. 等式 \sum_{n=0}^\infty \frac{b_n}{n!}x^n=EG(x) 兩邊取對數。
  2. 等號兩邊求導,並同乘 x
  3. 通乘分母項以清除分式,比較等號兩邊的 x^n 係數即得遞迴關係式。

 
最後我們用下圖總結本文的推論路徑,其中 S(n,k)= \begin{Bmatrix} n\\ k \end{Bmatrix} 是第二類 Stirling 數,B_k(x) 為其普通母函數,b_n 是貝爾數,EG(x) 為其指數母函數,RR (recurrence relation) 表示遞迴關係式,Formula 表示顯式表達式。這個例子清楚地展示了普通母函數和指數母函數在組合數學中扮演的重要角色。通過母函數,我們得以雙向聯繫一數列的遞迴關係式和顯式表達式。

Stirling

 
參考來源:
[1] 維基百科:Stirling numbers of the second kind
[2] 維基百科:Bell number

This entry was posted in 特別主題 and tagged , , , , . Bookmark the permalink.

2 則回應給 第二類 Stirling 數與貝爾數

  1. 陈潞芳 說:

    《第二类Stirling 数与贝尔数》一文中,有些符号和文字错位的地方。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s