两类Stirling Number的简介与区别(参考自ACdreamer的CSDN

Stirling Number I --- s(n,k):将n个物体排成k个非空循环排列(环)的方法数。

递推式:s(n, k) = (n-1)*s(n-1, k) + s(n-1, k-1); 1<= k<n

解释:考虑第n个元素1、单独形成循环排列,剩下的有s(n-1, k-1)种方法

            2、和别的元素一起形成循环排列,n-1个元素形成k个循环排列的方法数是s(n-1,k),插入时共有n种方法,共n*s(n-1,k)种

边界条件:s(i, 0) = 0, i>=1
     s(i, i ) = 1, i>=0

Stirling Number II --- S(n,k):n个元素放到k个集合内的方法总数(将n个人分进k个非空的无差别房间的方法数)

             k!S(p,k):把n个人分进k间有差别(如:被标有房号)的房间(无空房)的方法数。

递推式:S(n, k) = k*S(n-1,k)+S(n-1,k-1) ,1<= k<n
边界条件:s(i, 0) = 0, i>=1 
     s(i, i ) = 1, i>=0

Stirling Number I 和Stirling Number II 有相同的初始条件,但递推关系不同。

拓展

Bell Number --- B[n]

B是基数为n的集合的划分方法的数目。集合S的一个划分是定义为S的两两不相交的非空子集的族,它们的并是S

每个Bell Number都是Stirling Number II的和。

05-02 04:21