万博manbetx体育安卓

斯特林数

声明:百科词条人人可编纂,词条建立和点窜均免费,毫不具有官方及代办署理商付费代编,请勿上当被骗。详情

可指两类数,第一类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数的概念由J.Stirling于1730年提出,并在他的著作《Methodous Differentialis》中初次利用。

Stirling数出此刻很多组合列举问题中。对第一类Stirling数

。暗示将 n 个分歧元素形成m个圆陈列的数目。又按照正负性分为无符号第一类Stirling数

。有无符号Stirling数别离表示为其升阶函数和降阶函数的各项系数[雷同于

。组合数学中的第一类Stirling数一般指无符号的第一类Stirling数。意义是n个分歧元素形成m个圆陈列的方案数。

(1)若是n个元素形成了m-1个圆陈列,那么第n+1个元素独自形成一个圆陈列。方案数:

(2)若是n个元素形成了m个圆陈列,将第n+1个元素插入到肆意元素的右边。方案数:

而有符号的第一类Stirling数能够从其暗示的降阶函数归纳证明(简单写如下):

能够形成一个杨辉三角(pascal三角形)。同样第一类Stirling数同样也能够形成一个三角,能够由此阐发其性质。

第一类Stirling除了暗示能够暗示升阶函数和降阶函数的系数之外还能够使用到一些现实问题上。例如很典范的解锁仓库问题。

问题申明如下:有n个仓库,每个仓库有两把钥匙,共2n把钥匙。同时又有n位官员。问若何放置钥匙使得所有官员都可以或许打开所有仓库?(只考虑钥匙怎样放到仓库中,而不考虑官员拿哪把钥匙。)那若是官员分成m个分歧的部,部中的官员数量和办理的仓库数量分歧。那么有几多方案使得,同部的所有官员能够打开所有本部办理的仓库,而无法打开其他部办理的仓库?(同样只考虑钥匙的放置。)

第一问很典范,2号仓库放3号钥匙……n号仓库放1号钥匙。这种环境相当于钥匙和仓库编号形成一个圆陈列方案数是

而第二问就对应的将n个元素分成m个圆陈列,方案数就是第一类无符号Stirling数

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

第二类Stirling数现实上是调集的一个拆分,暗示将n个分歧的元素拆分成m个调集的方案数,记为

。和第一类Stirling数分歧的是,调集内是不考虑次序的,而圆陈列是有序的。常常用于处理组合数学中几类放球模子。描述为:将n个分歧的球放入m个无不同的盒子中,要求盒子非空,有几种方案?

第二类Stirling数要求盒子是无区此外,所以能够获得其方案数公式:

第二类Stirling数的推导和第一类Stirling数雷同,能够从定义出发考虑第n+1个元素的环境,假设要把n+1个元素分成m个调集则阐发如下:

(1)若是n个元素形成了m-1个调集,那么第n+1个元素零丁形成一个调集。方案数

(2)若是n个元素曾经形成了m个调集,将第n+1个元素插入到肆意一个调集。方案数 m*S(n,m) 。

0 1 255 3025 7770 6951 2646 462 36 1

第二类Stirling数次要是用于处理组合数学中的几类放球模子。次要是针对于球之前有区此外放球模子:

②既然答应盒子为空,且盒子间有区别,那么对于每个球有m种选择,每个球彼此独立。无方案数:

②既然盒子有区别,那么先不考虑空盒,对于每个元素有m种选择,方式数是:

。明显包含了空盒的环境,且空盒数量是大于等于0的。为了便利申明,这边设具有空盒数是h的环境是

③天然想到计较空盒数大于等于1的环境就能求解。那么先选定一个空盒,残剩的再随便放置,方案数是:

。那么有h的空盒的环境被计较了几回?由于空盒必必要有一个出此刻被选定的位置,那么反复数量是:

起首,仍是一样先区分调集。因母函数一般是一维的项数,这边固定调集数量为m,设n为项数。则有:

两类Stirling数之间的递推式和现实寄义很雷同,现实上他们之间具有一个互为转置的转化关系:

更多精彩报道,尽在https://www.aploled.com

发表评论

电子邮件地址不会被公开。 必填项已用*标注