两类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的和。