跳转到内容

斯特灵数

本页使用了标题或全文手工转换
维基百科,自由的百科全书

在数学中,斯特林数用于解决各种数学分析组合数学问题,斯特林数是两组不同的数,均是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.