跳至內容

斯特靈數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

在數學中,士他令數用於解決各種數學分析組合數學問題,士他令數是兩組不同的數,均是18世紀由占士·士他令英語James Stirling (mathematician)引入並以其命名,以第一類士他令數英語Stirling numbers of the first kind第二類士他令數英語Stirling numbers of the second kind的稱呼區分。此外,有時候也將拉赫數英語Lah number稱爲第三類士他令數[1]

第一類士他令數

[編輯]

定義

[編輯]

第一類士他令數英語Stirling numbers of the first kind可以定義爲對應遞降階乘展開式的各項系數,即 其中,)即爲第一類士他令數。例如:

於是

由此可知,代數數,或稱爲有符號(第一類)士他令數(英語:signed Stirling numbers of the first kind)。

有符號士他令數的絕對值可以看作(或直接定義爲)把個元素排列成個非空圓圈(循環排列)的方法數目。所以算術數,或稱爲無符號(第一類)士他令數(英語:unsigned Stirling numbers of the first kind)。無符號士他令數一般可以記爲。例如:把三個數排列成個非空圓圈,顯然有零種方法;排列成個非空圓圈,有兩種方法;排列成個非空圓圈,有三種方法;排列成個非空圓圈,有一種方法,所以。可以看到這和前面有符號士他令數時的結果一致(只是符號差異)。

與有符號士他令數類似,無符號士他令數可以定義爲對應遞進階乘展開式的各項系數,即

其中,)即爲無符號士他令數。不過要注意,這裏的記號有時候會用來表示高斯二項式係數

有符號士他令數和無符號士他令數有如下關係:

拓展示例

[編輯]

無符號士他令數有更多的應用。例如,將個元素分成組,每組內的元素再進行排列的方法數目即可用無符號士他令數求得。以爲例:

  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)

或用有向圖[來源請求]表示如下:

s(4,2)=11

遞推關係式

[編輯]

無符號士他令數有如下遞推關係式

其中,,且初始條件爲 )。

有符號士他令數有如下遞推關係式:

第一類士他令數表

[編輯]

下表其實是一部分無符號士他令數,要想獲得有符號士他令數,可以通過它們之間的關係式:

求得。

 k
n 
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

簡單性質

[編輯]

觀察前面的「第一類士他令數表」,我們可以得到一些簡單的性質:

)。

如果,我們有

或更一般地,如果,我們有

還有

註:這裏記號表示組合數

其他性質

[編輯]

第二類士他令數

[編輯]

定義

[編輯]

第二類士他令數英語Stirling numbers of the second kind與第一類士他令數類似,可以用遞降階乘定義爲

其中,[2][3]即爲第二類士他令數,也可以記爲[4]。例如:

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

比較等式兩邊系數,得

解得

第二類士他令數計算的是將含有個元素的集合拆分爲個非空子集的方法數目[5]。例如:對於集合,若拆分爲個非空子集,顯然有零種方法;拆分爲個非空子集,只有一種方法;拆分爲個非空子集,有三種方法;拆分爲個非空子集,有一種方法。於是

第二類士他令數可以使用以下公式進行計算:[6]

進行驗算,有

於是

拓展示例

[編輯]

個人分成組的分組方法的數目。例如有甲、乙、丙、丁四人,若所有人分成組,只能所有人在同一組,因此;若所有人分成組,只能每人獨立一組,因此;若分成組,可以是甲乙一組、丙丁一組,或甲丙一組、乙丁一組,或甲丁一組、乙丙一組,或其中三人同一組另一人獨立一組,即:

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

因此。同理,可以得到

遞推關係式

[編輯]

第二類士他令數有與第一類士他令數類似的遞推關係式:

其中,,且初始條件爲 )。

第二類士他令數表

[編輯]

下面爲部分第二類士他令數:

 k
n 
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

簡單性質

[編輯]

觀察前面的「第二類士他令數表」,我們可以得到一些簡單的性質:

)。

如果,我們有

或更一般地,如果,我們有

還有

其他性質

[編輯]

貝爾數和第二類士他令數有如下關係:

兩類之間的關係

[編輯]

第一類和第二類士他令數可以看作互爲逆矩陣的關係:

以及

其中,克羅內克爾δ

拉赫數

[編輯]

定義

[編輯]

拉赫數英語Lah number是由伊沃·拉赫英語Ivo Lah在1954年發現的[7][8],因爲拉赫數與士他令數關係密切,所以有時拉赫數也被稱爲第三類士他令數。可以用遞進階乘和遞降階乘定義爲

其中, 即爲拉赫數。例如:

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

比較等式兩邊系數,得

解得

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

比較等式兩邊系數,得

解得

以上定義的拉赫數是無符號拉赫數(英語: signed Lah numbers),有符號拉赫數(英語:signed Lah numbers)的定義如下:

無符號拉赫數計算的是將含有個元素的集合拆分爲個非空線性有序子集的方法數目[9]。例如:對於集合,若拆分爲個非空線性有序子集,顯然有零種方法;拆分爲個非空線性有序子集,有六種方法;拆分爲個非空線性有序子集,有六種方法;拆分爲個非空線性有序子集,有一種方法。於是

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

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

拓展示例

[編輯]
無符號拉赫數(nk取1到4)

遞推關係式

[編輯]

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

其中,),

拉赫數表

[編輯]

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

 k
n 
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

簡單性質

[編輯]

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

如果,有

還有

其他性質

[編輯]

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

無符號拉赫數與兩類士他令數都有關係[10],關係如下:

進行驗算,有

於是

由無符號拉赫數與兩類士他令數之間的關係,考慮到兩類士他令數之間的關係,有

其中,克羅內克爾δ

三類之間的關係

[編輯]

三類士他令數以及乘方、階乘之間的關係可以用下圖表示:

參考資料

[編輯]
  1. ^ Sándor, Jozsef; Crstici, Borislav. Handbook of Number Theory II. Kluwer Academic Publishers. 2004: 464. ISBN 9781402025464. 
  2. ^ Transformation of Series by a Variant of Stirling's Numbers. Imanuel Marx, The American Mathematical Monthly 69, #6 (June–July 1962). : 530–532,. JSTOR 2311194.. 
  3. ^ Antonio Salmeri (編). Introduzione alla teoria dei coefficienti fattoriali, Giornale di Matematiche di Battaglini 90 (1962). : pp. 44–54. 
  4. ^ Knuth, D.E. (1992) (編). "Two notes on notation", Amer. Math. Monthly, 99. : 403-422. JSTOR 2325085. arXiv:math/9205211可免費查閱. doi:10.2307/2325085. 
  5. ^ Brualdi,R.A. (編). 组合数学(原书第5版). 由馮速等人翻譯. 北京: 機械工業出版社. 2012.4: 176頁. ISBN 978-7-111-37787-0. 
  6. ^ Weisstein, Eric W. (編). "Stirling Number of the Second Kind". at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2019-06-06]. (原始內容存檔於2019-06-06) (英語). 
  7. ^ Lah, Ivo. A new kind of numbers and its application in the actuarial mathematics 9. 1954: 7–15.  |journal=被忽略 (幫助)
  8. ^ John Riordan, Introduction to Combinatorial Analysis頁面存檔備份,存於互聯網檔案館), Princeton University Press (1958, reissue 1980) ISBN 978-0-691-02365-6 (reprinted again in 2002 by Dover Publications).
  9. ^ Petkovsek, Marko; Pisanski, Tomaz. Combinatorial Interpretation of Unsigned Stirling and Lah Numbers 12. Fall 2007: 417–424. JSTOR 24340704.  |journal=被忽略 (幫助); |number=被忽略 (幫助)
  10. ^ Comtet, Louis. Advanced Combinatorics. Dordrecht, Holland: Reidel. 1974: 156.