第二类Stirling数

第二类斯特林数

第二类Stirling数:S2(p, k)
1.组合意义:第二类Stirling数计数的是把p个互异元素划分为k个非空集合的方法数
2.递推公式:
S2(0, 0) = 1
S2(p, 0) = 0 ( p >= 1)  显然p >= 1时这种方法不存在
S2(p, p) = 1  显然这时每个元素看为一个集合
S2(p, k) = k * S2(p - 1, k) + S2(p - 1, k - 1)
考虑将1,2,3,...,p划分为k个非空集合,考虑p
⑴将p单独划分为一个集合,此时的方案数等于将1,2,3,...,p -1划分为k - 1个非空集合的方案树,及S2(p - 1, k - 1)。
⑵将p和其他元素放一块,先考虑将1,2,3,..., p - 1划分为k个非空集合,此时p有k种放法,即k * S2(p - 1, k)。
故 S2(p, k) = k * S2(p - 1, k) + S2(p - 1, k - 1)
3.类pascal三角形:如二项式那样,可以构造这些Stiring数S2(p, k)的类pascal三角形。
  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  
...                
 
 
 
 
 
 
 
 
 
 
 
4.通项公式:
先把这k个集合看为互异的,则可以通过容斥原理计算将p个元素放入k个互异集合的个数,再除以k!即可(公式不好打。。。)
 
bell数:
1.组合意义:将p个元素划分为若干集合的方法数。
2.B(p) = S2(p, 0) + S2(p, 1) + S2(p, 2) + ... + S2(p, p)
集合数显然不能超过p,故bell数即为Stirling数求和
3.递推公式:其中C(n, m)表示n元集中m元子集的个数
B(p) = C(p - 1, 0) * B(0) + C(p - 1, 1) * B(1) + ... + C(p - 1, p - 1) * B(p - 1)
把集合{1, 2, 3, 4, ..., p}划分为若干集合的方法数,考虑元素p
若令p所在集合有p - k个元素,则剩下的元素为k个,在p - 1个元素中选k个,故此时有C(p - 1, k) * B(k) 个方案,求和即可
 
第一类Stirling数为把p个元素划分为k个非空循环排列的方案数。
S1(p, k) = (p - 1) * S1(p - 1, k) + S1(p - 1, k - 1)
//没有代码
 
 
 
 
上一篇:Android服务——Service


下一篇:python全栈开发day59-Django基础