Stirling數

在數學中，**史特靈數**用於解決各種數學分析和組合數學問題，史特靈數是兩組不同的數，均是 18 世紀由詹姆士・史特靈引入並以其命名，以**第一類史特靈數**和**第二類史特靈數**的稱呼區分。此外，有時候也將**拉赫數**稱爲第三類史特靈數。

## 第一類史特靈數

### 定義

**第一類史特靈數**可以定義爲對應遞降階乘展開式的各項係數，即

其中， $s(n,k)\,$ （ $0\leq k\leq n\,$ ）即爲第一類史特靈數。例如：

　
:

則

　
:

於是 $s(3,0)=0\,$ ，
 $s(3,1)=2\,$ ，
 $s(3,2)=-3\,$ ，
 $s(3,3)=1\,$ 。

由此可知， $s(n,k)\,$ 是代數數，或稱爲有符號（第一類）史特靈數（英語：signed Stirling numbers of the first kind）。

有符號史特靈數的絕對值 $|s(n,k)|\,$ 可以看作（或直接定義爲）把 $n\,$ 個元素排列成 $k\,$ 個非空圓圈（循環排列）的方法數目。所以 $|s(n,k)|\,$ 是算術數，或稱爲無符號（第一類）史特靈數（英語：unsigned Stirling numbers of the first kind）。無符號史特靈數一般可以記爲 $c(n,k)\,$ 或 $\left[{\begin{matrix}n\\k\end{matrix}}\right]\,$ 。例如：把 $1\,$ ， $2\,$ ， $3\,$ 三個數排列成 $0\,$ 個非空圓圈，顯然有零種方法；排列成 $1\,$ 個非空圓圈，有 $\left({\begin{matrix}&1&\\2&&3\end{matrix}}\right)\,$ ， $\left({\begin{matrix}&1&\\3&&2\end{matrix}}\right)\,$ 兩種方法；排列成 $2\,$ 個非空圓圈，有 $\left({\begin{matrix}1\end{matrix}}\right)\,$ $\left({\begin{matrix}2&3\end{matrix}}\right)\,$ ， $\left({\begin{matrix}1&2\end{matrix}}\right)\,$ $\left({\begin{matrix}3\end{matrix}}\right)\,$ 和 $\left({\begin{matrix}1&3\end{matrix}}\right)\,$ $\left({\begin{matrix}2\end{matrix}}\right)\,$ 三種方法；排列成 $3\,$ 個非空圓圈，有 $\left({\begin{matrix}1\end{matrix}}\right)\,$ $\left({\begin{matrix}2\end{matrix}}\right)\,$ $\left({\begin{matrix}3\end{matrix}}\right)\,$ 一種方法，所以 $\left[{\begin{matrix}3\\0\end{matrix}}\right]=0\,$ $\left[{\begin{matrix}3\\1\end{matrix}}\right]=2\,$ ， $\left[{\begin{matrix}3\\2\end{matrix}}\right]=3\,$ ， $\left[{\begin{matrix}3\\3\end{matrix}}\right]=1\,$ 。可以看到這和前面有符號史特靈數 $s(n,k)\,$ 在 $n=3\,$ 時的結果一致（只是符號差異）。

與有符號史特靈數類似，無符號史特靈數可以定義爲對應遞進階乘展開式的各項係數，即

　
:

其中， $\left[{\begin{matrix}n\\k\end{matrix}}\right]\,$ （ $0\leq k\leq n\,$ ）即爲無符號史特靈數。不過要注意，這裏的記號 $\left[{\begin{matrix}n\\k\end{matrix}}\right]\,$ 有時候會用來表示高斯二項式係數。

有符號史特靈數和無符號史特靈數有如下關係：

　
:

### 拓展示例

無符號史特靈數有更多的應用。例如，將 $n\,$ 個元素分成 $k\,$ 組，每組內的元素再進行排列的方法數目即可用無符號史特靈數 $\left[{\begin{matrix}n\\k\end{matrix}}\right]\,$ 求得。以 $\left[{\begin{matrix}4\\2\end{matrix}}\right]=11\,$ 爲例：

1. (A,B)(C,D)
2. (A,C)(B,D)
3. (A,D)(B,C)
4. (A)(B,C,D)
5. (A)(B,D,C)
6. (B)(A,C,D)
7. (B)(A,D,C)
8. (C)(A,B,D)
9. (C)(A,D,B)
10. (D)(A,B,C)
11. (D)(A,C,B)

或用有向圖表示如下：

### 遞推關係式

無符號史特靈數有如下遞推關係式：

　
:

其中， $k>0$ ，且初始條件爲 $\left[{\begin{matrix}0\\0\end{matrix}}\right]=1\,$ ， $\left[{\begin{matrix}n\\0\end{matrix}}\right]=\left[{\begin{matrix}0\\n\end{matrix}}\right]=0\,$ （ $n>0$ ）。

有符號史特靈數有如下遞推關係式：

　
:

### 第一類史特靈數表

下表其實是一部分無符號史特靈數，要想獲得有符號史特靈數，可以通過它們之間的關係式：

　
:

求得。

### 簡單性質

觀察前面的「第一類史特靈數表」，我們可以得到一些簡單的性質：

　
: $\left[{\begin{matrix}0\\0\end{matrix}}\right]=1\,$ ， $\left[{\begin{matrix}n\\0\end{matrix}}\right]=0\,$ （ $n>0\,$ ）。

如果 $k>0\,$ ，我們有

　
: $\left[{\begin{matrix}0\\k\end{matrix}}\right]=0\,$ ；

或更一般地，如果 $k>n\,$ ，我們有

　
: $\left[{\begin{matrix}n\\k\end{matrix}}\right]=0\,$ 。

還有

　
: $\left[{\begin{matrix}n\\1\end{matrix}}\right]=(n-1)!\,$ ，

　
: $\left[{\begin{matrix}n\\n\end{matrix}}\right]=1\,$ ，

　
: $\left[{\begin{matrix}n\\n-1\end{matrix}}\right]={n \choose 2}\,$ ，

　
: $\left[{\begin{matrix}n\\n-2\end{matrix}}\right]={\frac {1}{4}}(3n-1){n \choose 3}\,$ ，

　
: $\left[{\begin{matrix}n\\n-3\end{matrix}}\right]={n \choose 2}{n \choose 4}\,$ 。

註：這裏記號 ${n \choose k}\,$ 表示組合數。

### 其他性質

## 第二類史特靈數

### 定義

**第二類史特靈數**與第一類史特靈數類似，可以用遞降階乘定義爲

　
:

其中， $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}\,$ 即爲第二類史特靈數，也可以記爲 $S(n,k)\,$ 。例如：

　
:

即

　
:

將遞降階乘展開並合併同類項，得

　
:

比較等式兩邊係數，得

　
:

解得

 $\left\{{\begin{matrix}3\\0\end{matrix}}\right\}=0\,$ ， $\left\{{\begin{matrix}3\\1\end{matrix}}\right\}=1\,$ ， $\left\{{\begin{matrix}3\\2\end{matrix}}\right\}=3\,$ ， $\left\{{\begin{matrix}3\\3\end{matrix}}\right\}=1\,$ 。

第二類史特靈數計算的是將含有 $n\,$ 個元素的集合拆分爲 $k\,$ 個非空子集的方法數目。例如：對於集合 $\left\{1,2,3\right\}\,$ ，若拆分爲 $0\,$ 個非空子集，顯然有零種方法；拆分爲 $1\,$ 個非空子集，只有 $\left\{1,2,3\right\}\,$ 一種方法；拆分爲 $2\,$ 個非空子集，有 $\left\{1\right\}\,$ $\left\{2,3\right\}\,$ ， $\left\{1,2\right\}\,$ $\left\{3\right\}\,$ ， $\left\{2\right\}\,$ $\left\{1,3\right\}\,$ 三種方法；拆分爲 $3\,$ 個非空子集，有 $\left\{1\right\}\,$ $\left\{2\right\}\,$ $\left\{3\right\}\,$ 一種方法。於是 $\left\{{\begin{matrix}3\\0\end{matrix}}\right\}=0\,$ ， $\left\{{\begin{matrix}3\\1\end{matrix}}\right\}=1\,$ ， $\left\{{\begin{matrix}3\\2\end{matrix}}\right\}=3\,$ ， $\left\{{\begin{matrix}3\\3\end{matrix}}\right\}=1\,$ 。

第二類史特靈數可以使用以下公式進行計算：

　
:

取 $\left\{{\begin{matrix}3\\2\end{matrix}}\right\}\,$ 進行驗算，有

　
:

即

　
:

於是

　
:

### 拓展示例

將 $n\,$ 個人分成 $k\,$ 組的分組方法的數目。例如有甲、乙、丙、丁四人，若所有人分成 $1\,$ 組，只能所有人在同一組，因此 $\left\{{\begin{matrix}4\\1\end{matrix}}\right\}=1\,$ ；若所有人分成 $4\,$ 組，只能每人獨立一組，因此 $\left\{{\begin{matrix}4\\4\end{matrix}}\right\}=1\,$ ；若分成 $2\,$ 組，可以是甲乙一組、丙丁一組，或甲丙一組、乙丁一組，或甲丁一組、乙丙一組，或其中三人同一組另一人獨立一組，即：

1. {甲，乙}{丙，丁}
2. {甲，丙}{乙，丁}
3. {甲，丁}{乙，丙}
4. {甲}{乙，丙，丁}
5. {乙}{甲，丙，丁}
6. {丙}{甲，乙，丁}
7. {丁}{甲，乙，丙}

因此 $\left\{{\begin{matrix}4\\2\end{matrix}}\right\}=7\,$ 。同理，可以得到 $\left\{{\begin{matrix}4\\3\end{matrix}}\right\}=6\,$ 。

### 遞推關係式

第二類史特靈數有與第一類史特靈數類似的遞推關係式：

　
:

其中， $k>0$ ，且初始條件爲 $\left\{{\begin{matrix}0\\0\end{matrix}}\right\}=1\,$ ， $\left\{{\begin{matrix}n\\0\end{matrix}}\right\}=\left\{{\begin{matrix}0\\n\end{matrix}}\right\}=0\,$ （ $n>0$ ）。

### 第二類史特靈數表

下面爲部分第二類史特靈數：

### 簡單性質

觀察前面的「第二類史特靈數表」，我們可以得到一些簡單的性質：

　
: $\left\{{\begin{matrix}0\\0\end{matrix}}\right\}=1\,$ ， $\left\{{\begin{matrix}n\\0\end{matrix}}\right\}=0\,$ （ $n>0\,$ ）。

如果 $k>0\,$ ，我們有

　
: $\left\{{\begin{matrix}0\\k\end{matrix}}\right\}=0\,$ ；

或更一般地，如果 $k>n\,$ ，我們有

　
: $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=0\,$ 。

還有

　
: $\left\{{\begin{matrix}n\\1\end{matrix}}\right\}=1\,$ ，

　
: $\left\{{\begin{matrix}n\\2\end{matrix}}\right\}=2^{n-1}-1\,$ ，

　
: $\left\{{\begin{matrix}n\\3\end{matrix}}\right\}={\frac {1}{2}}(3^{n-1}+1)-2^{n-1}\,$ ，

　
: $\left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1\,$ ，

　
: $\left\{{\begin{matrix}n\\n-1\end{matrix}}\right\}={n \choose 2}\,$ ，

　
: $\left\{{\begin{matrix}n\\n-2\end{matrix}}\right\}={n \choose 3}+3{n \choose 4}\,$ ，

　
: $\left\{{\begin{matrix}n\\n-3\end{matrix}}\right\}={n \choose 4}+10{n \choose 5}+15{n \choose 6}\,$ 。

### 其他性質

貝爾數和第二類史特靈數有如下關係：

　
:

## 兩類之間的關係

第一類和第二類史特靈數可以看作互爲逆矩陣的關係：

　
:

以及

　
:

其中， $\delta _{nk}\,$ 是克羅內克爾 δ。

## 拉赫數

### 定義

**拉赫數**是由伊沃・拉赫在 1954 年發現的，因爲拉赫數與史特靈數關係密切，所以有時拉赫數也被稱爲**第三類史特靈數**。可以用遞進階乘和遞降階乘定義爲

　
:

或

　
:

其中， $L(n,k)\,$ 即爲拉赫數。例如：

　
:

即

　
: $x(x+1)(x+2)=L(3,0)\cdot 1+L(3,1)\cdot x+L(3,2)\cdot x(x-1)+L(3,3)\cdot x(x-1)(x-2)\,$

等式兩邊展開並合併同類項，得

　
:

比較等式兩邊係數，得

　
:

解得 $L(3,0)=0\,$ ， $L(3,1)=6\,$ ，
 $L(3,2)=6\,$ ， $L(3,3)=1\,$ 。

或

　
:

即

　
: $x(x-1)(x-2)=L(3,0)\cdot 1+L(3,1)\cdot x+L(3,2)\cdot x(x+1)+L(3,3)\cdot x(x+1)(x+2)\,$

等式兩邊展開並合併同類項，得

　
:

比較等式兩邊係數，得

　
:

解得 $L(3,0)=0\,$ ， $L(3,1)=6\,$ ，
 $L(3,2)=6\,$ ， $L(3,3)=1\,$ 。

以上定義的拉赫數是無符號拉赫數（英語： signed Lah numbers），有符號拉赫數（英語：signed Lah numbers）的定義如下：

　
:

或

　
:

無符號拉赫數計算的是將含有 $n\,$ 個元素的集合拆分爲 $k\,$ 個非空線性有序子集的方法數目。例如：對於集合 $\left\{1,2,3\right\}\,$ ，若拆分爲 $0\,$ 個非空線性有序子集，顯然有零種方法；拆分爲 $1\,$ 個非空線性有序子集，有 $\left\{(1,2,3)\right\}\,$ ， $\left\{(1,3,2)\right\}\,$ ， $\left\{(2,1,3)\right\}\,$ ， $\left\{(2,3,1)\right\}\,$ ， $\left\{(3,1,2)\right\}\,$ ， $\left\{(3,2,1)\right\}\,$ 六種方法；拆分爲 $2\,$ 個非空線性有序子集，有 $\left\{(1)\right\}\,$ $\left\{(2,3)\right\}\,$ ， $\left\{(1)\right\}\,$ $\left\{(3,2)\right\}\,$ ， $\left\{(2)\right\}\,$ $\left\{(1,3)\right\}\,$ ， $\left\{(2)\right\}\,$ $\left\{(3,1)\right\}\,$ ， $\left\{(3)\right\}\,$ $\left\{(1,2)\right\}\,$ ， $\left\{(3)\right\}\,$ $\left\{(2,1)\right\}\,$ 六種方法；拆分爲 $3\,$ 個非空線性有序子集，有 $\left\{(1)\right\}\,$ ， $\left\{(2)\right\}\,$ ， $\left\{(3)\right\}\,$ 一種方法。於是 $L(3,0)=0\,$ ， $L(3,1)=6\,$ ，
 $L(3,2)=6\,$ ， $L(3,3)=1\,$ 。

無符號拉赫數可以使用以下公式進行計算：

　
:

有符號拉赫數可以使用以下公式進行計算：

　
:

### 拓展示例

### 遞推關係式

無符號拉赫數有如下遞推關係：

　
: $L(n,k+1)={\frac {n-k}{k(k+1)}}L(n,k)$

或

　
: $L(n+1,k)=(n+k)L(n,k)+L(n,k-1)\,$

其中， $L(n,0)=0\,$ ， $L(n,0)=0\,$ ， $L(n,k)=0\,$ （ $k>n\,$ ）， $L(1,1)=1\,$

### 拉赫數表

下面爲部分無符號拉赫數：

### 簡單性質

觀察前面的「拉赫數表」，我們可以得到一些簡單性質：

 $L(0,0)=1$ ，
 $L(n,0)=0$ （ $n>0$ ）

如果 $k>n$ ，有 $L(0,0)=1$ ， $L(n,k)=0$

還有

　
: $L(n,1)=n!$

　
: $L(n,2)={\frac {(n-1)n!}{2}}$

　
: $L(n,3)={\frac {(n-2)(n-1)n!}{12}}$

　
: $L(n,n-1)=n(n-1)$

　
: $L(n,n)=1$

　
: $\sum _{n\geq k}L(n,k){\frac {x^{n}}{n!}}={\frac {1}{k!}}\left({\frac {x}{1-x}}\right)^{k}$

### 其他性質

無符號拉赫數計算公式可以作進一步拓展：

　
: $L(n,k)={n-1 \choose k-1}{\frac {n!}{k!}}={n \choose k}{\frac {(n-1)!}{(k-1)!}}={n \choose k}{n-1 \choose k-1}(n-k)!$

　
: $L(n,k)={\frac {n!(n-1)!}{k!(k-1)!}}\cdot {\frac {1}{(n-k)!}}=\left({\frac {n!}{k!}}\right)^{2}{\frac {k}{n(n-k)!}}$

無符號拉赫數與兩類史特靈數都有關係，關係如下：

　
:

取 $L(3,2)\,$ 進行驗算，有

　
:

即

　
:

於是

　
:

由無符號拉赫數與兩類史特靈數之間的關係，考慮到兩類史特靈數之間的關係，有

　
:

其中， $\delta _{nk}\,$ 是克羅內克爾 δ。

## 三類之間的關係

三類史特靈數以及乘方、階乘之間的關係可以用下圖表示：

　
:

## 參考資料