斯特灵数

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