斯特林数

Template:NoteTA 在數學中，史特靈數用於解決各種數學分析和組合數學問題，史特靈數是兩組不同的數，均是18世紀由Template:Link-en引入並以其命名，以Template:En-link和Template:En-link的稱呼區分。此外，有時候也將Template:En-link稱爲第三類史特靈數。

第一類史特靈數

定義

Template:En-link可以定義爲對應遞降階乘展開式的各項係數，即 $$(x{)}_n=\sum _{k=0}^{n}s(n,k)x^k$$ 其中，$s(n,k)$（$0\le k\le n$）即爲第一類史特靈數。例如：

$$(x{)}_3=x(x-1)(x-2)$$

則

$$(x{)}_3=0\cdot x^0+2\cdot x-3\cdot x^2+1\cdot x^3$$

於是$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{array}{c}n\\ k\end{array}\right]$。例如：把$1$，$2$，$3$三個數排列成$0$個非空圓圈，顯然有零種方法；排列成$1$個非空圓圈，有$\left(\begin{array}{ccc}& 1& \\ 2& & 3\end{array}\right)$，$\left(\begin{array}{ccc}& 1& \\ 3& & 2\end{array}\right)$兩種方法；排列成$2$個非空圓圈，有$\left(\begin{array}{c}1\end{array}\right)$$\left(\begin{array}{cc}2& 3\end{array}\right)$，$\left(\begin{array}{cc}1& 2\end{array}\right)$$\left(\begin{array}{c}3\end{array}\right)$和$\left(\begin{array}{cc}1& 3\end{array}\right)$$\left(\begin{array}{c}2\end{array}\right)$三種方法；排列成$3$個非空圓圈，有$\left(\begin{array}{c}1\end{array}\right)$$\left(\begin{array}{c}2\end{array}\right)$$\left(\begin{array}{c}3\end{array}\right)$一種方法，所以$\left[\begin{array}{c}3\\ 0\end{array}\right]=0$$\left[\begin{array}{c}3\\ 1\end{array}\right]=2$，$\left[\begin{array}{c}3\\ 2\end{array}\right]=3$，$\left[\begin{array}{c}3\\ 3\end{array}\right]=1$。可以看到這和前面有符號史特靈數$s(n,k)$在$n=3$時的結果一致（只是符號差異）。

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

$$(x{)}^{\bar{n}}=\sum _{k=0}^n\left[\begin{array}{c}n\\ k\end{array}\right]x^k$$

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

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

$$s(n,k)=(-1{)}^{n-k}\left[\begin{array}{c}n\\ k\end{array}\right]$$

拓展示例

無符號史特靈數有更多的應用。例如，將$n$個元素分成$k$組，每組內的元素再進行排列的方法數目即可用無符號史特靈數$\left[\begin{array}{c}n\\ k\end{array}\right]$求得。以$\left[\begin{array}{c}4\\ 2\end{array}\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)

或用有向圖Template:來源請求表示如下：

s(4,2)=11

遞推關係式

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

$$\left[\begin{array}{c}n+1\\ k\end{array}\right]=n\left[\begin{array}{c}n\\ k\end{array}\right]+\left[\begin{array}{c}n\\ k-1\end{array}\right]$$

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

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

$$s(n+1,k)=-ns(n,k)+s(n,k-1)$$

第一類史特靈數表

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

$$s(n,k)=(-1{)}^{n-k}\left[\begin{array}{c}n\\ k\end{array}\right]$$

求得。

Template:Diagonal split header	0	1	2	3	4	5	6
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1

簡單性質

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

$\left[\begin{array}{c}0\\ 0\end{array}\right]=1$，$\left[\begin{array}{c}n\\ 0\end{array}\right]=0$（$n>0$）。

如果$k>0$，我們有

$\left[\begin{array}{c}0\\ k\end{array}\right]=0$；

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

$\left[\begin{array}{c}n\\ k\end{array}\right]=0$。

還有

$\left[\begin{array}{c}n\\ 1\end{array}\right]=(n-1)!$，

$\left[\begin{array}{c}n\\ n\end{array}\right]=1$，

$\left[\begin{array}{c}n\\ n-1\end{array}\right]=(\genfrac{}{}{0ex}{}{n}{2})$，

$\left[\begin{array}{c}n\\ n-2\end{array}\right]=\frac{1}{4}(3n-1)(\genfrac{}{}{0ex}{}{n}{3})$，

$\left[\begin{array}{c}n\\ n-3\end{array}\right]=(\genfrac{}{}{0ex}{}{n}{2})(\genfrac{}{}{0ex}{}{n}{4})$。

注：這裏記號$(\genfrac{}{}{0ex}{}{n}{k})$表示组合数。

第二類史特靈數

定義

Template:En-link與第一類史特靈數類似，可以用遞降階乘定義爲

$$x^n=\sum _{k=0}^n\left\{\begin{array}{c}n\\ k\end{array}\right\}(x{)}_k$$

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

$$x^3=\left\{\begin{array}{c}3\\ 0\end{array}\right\}(x{)}_0+\left\{\begin{array}{c}3\\ 1\end{array}\right\}(x{)}_1+\left\{\begin{array}{c}3\\ 2\end{array}\right\}(x{)}_2+\left\{\begin{array}{c}3\\ 3\end{array}\right\}(x{)}_3$$

即

$$x^3=\left\{\begin{array}{c}3\\ 0\end{array}\right\}+\left\{\begin{array}{c}3\\ 1\end{array}\right\}x+\left\{\begin{array}{c}3\\ 2\end{array}\right\}x(x-1)+\left\{\begin{array}{c}3\\ 3\end{array}\right\}x(x-1)(x-2)$$

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

$$x^3=\left\{\begin{array}{c}3\\ 0\end{array}\right\}+(\left\{\begin{array}{c}3\\ 1\end{array}\right\}-\left\{\begin{array}{c}3\\ 2\end{array}\right\}+2\left\{\begin{array}{c}3\\ 3\end{array}\right\})x+(\left\{\begin{array}{c}3\\ 2\end{array}\right\}-3\left\{\begin{array}{c}3\\ 3\end{array}\right\})x^2+\left\{\begin{array}{c}3\\ 3\end{array}\right\}{x}^3$$

比較等式兩邊係數，得

$$\{\begin{array}{c}\left\{\begin{array}{c}3\\ 0\end{array}\right\}=0\\ \left\{\begin{array}{c}3\\ 1\end{array}\right\}-\left\{\begin{array}{c}3\\ 2\end{array}\right\}+2\left\{\begin{array}{c}3\\ 3\end{array}\right\}=0\\ \left\{\begin{array}{c}3\\ 2\end{array}\right\}-3\left\{\begin{array}{c}3\\ 3\end{array}\right\}=0\\ \left\{\begin{array}{c}3\\ 3\end{array}\right\}=1\end{array}$$

解得

$\left\{\begin{array}{c}3\\ 0\end{array}\right\}=0$，$\left\{\begin{array}{c}3\\ 1\end{array}\right\}=1$，$\left\{\begin{array}{c}3\\ 2\end{array}\right\}=3$，$\left\{\begin{array}{c}3\\ 3\end{array}\right\}=1$。

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

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

$$\left\{\begin{array}{c}n\\ k\end{array}\right\}=\frac{1}{k!}\sum _{i=0}^k(-1{)}^i\left(\begin{array}{c}k\\ i\end{array}\right)(k-i{)}^n$$

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

$$\left\{\begin{array}{c}3\\ 2\end{array}\right\}=\frac{1}{2!}\sum _{i=0}^2(-1{)}^i\left(\begin{array}{c}2\\ i\end{array}\right)(2-i{)}^3$$

即

$$\left\{\begin{array}{c}3\\ 2\end{array}\right\}=\frac{1}{2}(\left(\begin{array}{c}2\\ 0\end{array}\right)\times 2^3-\left(\begin{array}{c}2\\ 1\end{array}\right)\times 1^3+\left(\begin{array}{c}2\\ 2\end{array}\right)\times 0^3)$$

於是

$$\left\{\begin{array}{c}3\\ 2\end{array}\right\}=\frac{1}{2}(1\times 8-2\times 1+1\times 0)=3$$

拓展示例

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

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

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

遞推關係式

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

$$\left\{\begin{array}{c}n+1\\ k\end{array}\right\}=k\left\{\begin{array}{c}n\\ k\end{array}\right\}+\left\{\begin{array}{c}n\\ k-1\end{array}\right\}$$

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

第二類史特靈數表

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

Template:Diagonal split header	0	1	2	3	4	5	6
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1

簡單性質

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

$\left\{\begin{array}{c}0\\ 0\end{array}\right\}=1$，$\left\{\begin{array}{c}n\\ 0\end{array}\right\}=0$（$n>0$）。

如果$k>0$，我們有

$\left\{\begin{array}{c}0\\ k\end{array}\right\}=0$；

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

$\left\{\begin{array}{c}n\\ k\end{array}\right\}=0$。

還有

$\left\{\begin{array}{c}n\\ 1\end{array}\right\}=1$，

$\left\{\begin{array}{c}n\\ 2\end{array}\right\}=2^{n-1}-1$，

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

$\left\{\begin{array}{c}n\\ n\end{array}\right\}=1$，

$\left\{\begin{array}{c}n\\ n-1\end{array}\right\}=(\genfrac{}{}{0ex}{}{n}{2})$，

$\left\{\begin{array}{c}n\\ n-2\end{array}\right\}=(\genfrac{}{}{0ex}{}{n}{3})+3(\genfrac{}{}{0ex}{}{n}{4})$，

$\left\{\begin{array}{c}n\\ n-3\end{array}\right\}=(\genfrac{}{}{0ex}{}{n}{4})+10(\genfrac{}{}{0ex}{}{n}{5})+15(\genfrac{}{}{0ex}{}{n}{6})$。

其他性質

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

$$B_n=\sum _{k=0}^n\left\{\begin{array}{c}n\\ k\end{array}\right\}$$

兩類之間的關係

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

$$\sum _{j\ge 0}s(n,j)S(j,k)=\sum _{j\ge 0}(-1{)}^{n-j}\left[\begin{array}{c}n\\ j\end{array}\right]\left\{\begin{array}{c}j\\ k\end{array}\right\}={\delta }_{nk}\sum _{j\ge 0}s(n,j)S(j,k)=\sum _{j\ge 0}(-1{)}^{n-j}\left[\begin{array}{c}n\\ j\end{array}\right]\left\{\begin{array}{c}j\\ k\end{array}\right\}={\delta }_{nk}$$

以及

$$\sum _{j\ge 0}S(n,j)s(j,k)=\sum _{j\ge 0}(-1{)}^{j-k}\left\{\begin{array}{c}n\\ j\end{array}\right\}\left[\begin{array}{c}j\\ k\end{array}\right]={\delta }_{nk}\sum _{j\ge 0}S(n,j)s(j,k)=\sum _{j\ge 0}(-1{)}^{j-k}\left\{\begin{array}{c}n\\ j\end{array}\right\}\left[\begin{array}{c}j\\ k\end{array}\right]={\delta }_{nk}$$

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

拉赫數

定義

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

$$x^{(n)}=\sum _{k=0}^{n}L(n,k)(x{)}_k$$

或

$$(x{)}_n=\sum _{k=0}^n(-1{)}^{n-k}L(n,k)x^{(k)}$$

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

$$x^{(3)}=\sum _{k=0}^{3}L(3,k)(x{)}_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)$

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

$$0\cdot x^0+2\cdot x+3\cdot x^2+1\cdot x^3=L(3,0)+[L(3,1)-L(3,2)+2L(3,3)]\cdot x+[L(3,2)-3L(3,3)]\cdot x^2+L(3,3)\cdot x^3$$

比較等式兩邊係數，得

$$\{\begin{array}{c}L(3,0)=0\\ L(3,1)-L(3,2)+2L(3,3)=2\\ L(3,2)-3L(3,3)=3\\ L(3,3)=1\end{array}$$

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

或

$$(x{)}_3=\sum _{k=0}^3(-1{)}^{3-k}L(3,k)x^{(3)}$$

即

$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)$

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

$$0\cdot x^0+2\cdot x-3\cdot x^2+1\cdot x^3=-L(3,0)+[L(3,1)-L(3,2)+2L(3,3)]\cdot x+[-L(3,2)+3L(3,3)]\cdot x^2+L(3,3)\cdot x^3$$

比較等式兩邊係數，得

$$\{\begin{array}{c}L(3,0)=0\\ L(3,1)-L(3,2)+2L(3,3)=2\\ -L(3,2)+3L(3,3)=-3\\ L(3,3)=1\end{array}$$

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

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

$$x^{(n)}=(-1{)}^n\sum _{k=0}^{n}L(n,k)(x{)}_k$$

或

$$(x{)}_n=\sum _{k=0}^n(-1{)}^{k}L(n,k)x^{(k)}$$

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

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

$$L(n,k)=(\genfrac{}{}{0ex}{}{n-1}{k-1})\frac{n!}{k!}$$

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

$$L^{\prime }(n,k)=(-1{)}^n(\genfrac{}{}{0ex}{}{n-1}{k-1})\frac{n!}{k!}$$

拓展示例

無符號拉赫數（n和k取1到4）

遞推關係式

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

$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$

拉赫數表

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

Template:Diagonal split header	0	1	2	3	4	5	6
0	1
1	0	1
2	0	2	1
3	0	6	6	1
4	0	24	36	12	1
5	0	120	240	120	20	1
6	0	720	1800	1200	300	30	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\ge k}L(n,k)\frac{x^n}{n!}=\frac{1}{k!}{\left(\frac{x}{1-x}\right)}^k$

其他性質

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

$L(n,k)=(\genfrac{}{}{0ex}{}{n-1}{k-1})\frac{n!}{k!}=(\genfrac{}{}{0ex}{}{n}{k})\frac{(n-1)!}{(k-1)!}=(\genfrac{}{}{0ex}{}{n}{k})(\genfrac{}{}{0ex}{}{n-1}{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(n,k)=\sum _{j=0}^n\left[\begin{array}{c}n\\ j\end{array}\right]\left\{\begin{array}{c}j\\ k\end{array}\right\}$$

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

$$L(3,2)=\sum _{j=0}^3\left[\begin{array}{c}3\\ j\end{array}\right]\left\{\begin{array}{c}j\\ 2\end{array}\right\}$$

即

$$L(3,2)=\left[\begin{array}{c}3\\ 0\end{array}\right]\left\{\begin{array}{c}0\\ 2\end{array}\right\}+\left[\begin{array}{c}3\\ 1\end{array}\right]\left\{\begin{array}{c}1\\ 2\end{array}\right\}+\left[\begin{array}{c}3\\ 2\end{array}\right]\left\{\begin{array}{c}2\\ 2\end{array}\right\}+\left[\begin{array}{c}3\\ 3\end{array}\right]\left\{\begin{array}{c}3\\ 2\end{array}\right\}$$

於是

$$L(3,2)=\left[\begin{array}{c}3\\ 2\end{array}\right]\left\{\begin{array}{c}2\\ 2\end{array}\right\}+\left[\begin{array}{c}3\\ 3\end{array}\right]\left\{\begin{array}{c}3\\ 2\end{array}\right\}=3\times 1+1\times 3=6$$

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

$$\sum _{j\ge 0}L(n,j)L(j,k)={\delta }_{nk}$$

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

三類之間的關係

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