斯特林数的介绍

在组合数学，Stirling数可指两类数，***类Stirling数和第二类Stirling数，都是由18世纪数学家James Stirling提出的。Stirling数有两种，***类和第二类Stirling数，它们自18世纪以来一直吸引许多数学家的兴趣，如欧拉、柯西、西尔沃斯特和凯莱等。后来哥本哈根（Copenhagen）大学的尼尔森（Niels Nielsen，1865-1931）提出了Stirlingschen Zahlen erster Art [***类Stirling数]和Stirlingschen Zahlen zweiter Art [第二类Stirling数]，首次把这两类数冠以「Stirling数」之名 。因为苏格兰数学家斯特林（J. Stirling, 1692-1770）首次发现这些数并说明了它们的重要性。

斯特林数的第二类Stirling数

第二类Stirling数的推导和***类Stirling数类似，可以从定义出发考虑第n+1个元素的情况，假设要把n+1个元素分成m和集合则分析如下：

（1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数 。

（2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 。

综合两种情况得： ①

②

③

④

⑤

⑥

⑦

⑧

⑨ ， 是贝尔数 。 第二类Stirling数主要是用于解决组合数学中的几类放球模型。主要是针对于球之前有区别的放球模型：

（1）n个不同的球，放入m个无区别的盒子，不允许盒子为空。

方案数： 。这个跟第二类Stirling数的定义一致。

（2）n个不同的球，放入m个有区别的盒子，不允许盒子为空。

方案数： 。因盒子有区别，乘上盒子的排列即可。

（3）n个不同的球，放入m个无区别的盒子，允许盒子为空。

方案数： 。枚举非空盒的数目便可。

（4）n个不同的球，放入m个有区别的盒子，允许盒子为空。

①方案数： 。同样可以枚举非空盒的数目，注意到盒子有区别，乘上一个排列系数。

②既然允许盒子为空，且盒子间有区别，那么对于每个球有m中选择，每个球相互独立。有方案数： 。

上述式子可以应用于第二类Stirling数通项的求解。 这个通项公式有多种方法推导。常用的有容斥原理，母函数和等式求解等。

一、容斥原理。

容斥原理最为通俗易懂。

①为了区分集合，给集合上个标号顺序，最后答案再除 即可。

②既然盒子有区别，那么先不考虑空盒，对于每个元素有m种选择，方法数是： 。显然包含了空盒的情况，且空盒数量是大于等于0的。为了方便说明，这边设存在空盒数是h的情况是 种。那么便有 ，以及 。

③自然想到计算空盒数大于等于1的情况就能求解。那么先选定一个空盒，剩余的再随便放置，方案数是： 。那么有h的空盒的情况被计算了几次？因为空盒必须要有一个出现在被选定的位置，那么重复数量是： 。

④对于更一般情况，计算空盒数不小于k的情况有 ，而产生h空盒的重复次数是 。那么就有 。

⑤要消除掉这种组合数为系数的项要利用到容斥原理。 。那么就有：

交换一些累加符号顺序得： 右边=

解得：

二、母函数

母函数解法最为简便。

首先，还是一样先区分集合。因母函数一般是一维的项数，这边固定集合数量为m，设n为项数。则有：

对于每个集合因为元素之间不同，且集合非空，生成函数（母函数）为： 。

因为有m个集合，且互不相同，利用乘法法则和二项式展开有：

对上式中的 使用泰勒张开（指数型母函数）：

提取出上述等式两边 的系数有：

同样可以求得：

三、利用等式求解

这是应用举例中的一个等式：

显然看到，要消除系数，尝试不同的m值有：

发现排列数发生变化，为了抵消其变化等式两边同时乘上 得：

要消去组合数系数 利用一正一负累加：

交换求和顺序有：

右边

同样可以求得通项公式：

斯特林数的***类Stirling数

***类Stirling数表示表示将 n 个不同元素构成m个圆排列的数目。又根据正负性分为无符号***类Stirling数 和带符号***类Stirling数 。有无符号Stirling数分别表现为其升阶函数和降阶函数的各项系数[类似于二项式系数 ]，形式如下：

对于有无符号Stirling数之间的关系有 。组合数学中的***类Stirling数一般指无符号的***类Stirling数。意思是n个不同元素构成m个圆排列的方案数。 无符号***类Stirling数的递推式可以从其定义来推导：

考虑其定义如果要将n+1元素构成m个圆排列，考虑第n+1个元素：

（1）如果n个元素构成了m-1个圆排列，那么第n+1个元素独自构成一个圆排列。方案数：

（2）如果n个元素构成了m个圆排列，将第n+1个元素插入到任意元素的左边。方案数：

综合两种情况得：

而有符号的***类Stirling数可以从其表示的降阶函数归纳证明（简单写如下）：

依次把 在左右两边的系数提取出来得：

无符号Stirling数有如下性质：

①

②

③

④

⑤

⑥

⑦

⑧ 证明可令升阶函数中的x=1，比较两边系数。

有符号stirling性质类似：

①

⑧ ，注意 。证明可令降阶函数中的x=1，比较两边系数。 ***类Stirling除了表示可以表示升阶函数和降阶函数的系数之外还可以应用到一些实际问题上。例如很经典的解锁仓库问题。

问题说明如下：有n个仓库，每个仓库有两把钥匙，共2n把钥匙。同时又有n位官员。问如何放置钥匙使得所有官员都能够打开所有仓库？（只考虑钥匙怎么放到仓库中，而不考虑官员拿哪把钥匙。）那如果官员分成m个不同的部，部中的官员数量和管理的仓库数量一致。那么有多少方案使得，同部的所有官员可以打开所有本部管理的仓库，而无法打开其他部管理的仓库？（同样只考虑钥匙的放置。）

***问很经典，就是打开将钥匙放入仓库构成一个环：1号仓库放2号钥匙，2号仓库放3号钥匙……n号仓库放1号钥匙。这种情况相当于钥匙和仓库编号构成一个圆排列方案数是 种。

而第二问就对应的将n个元素分成m个圆排列，方案数就是***类无符号Stirling数 。如要要考虑官员的情况，只需再乘上 即可。 固定m将n看作是项数，母函数表示如下：

该式子的通项公式求解略微繁琐，这边仅给出其生成函数。更具体的参考维基中的通项定义。

关于斯特林数和斯特林数的应用的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。