4、第二类Stirling数
问题一:放置小球
n个有不同的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用S(n,m)表示,称为第二类Stirling数 ,求S(n,m)。
设有n个不同的球,分别用b1,b2,……bn表示。从中取出一个球bn,bn的放法有以下两种:
1)bn独自占一个盒子;那么剩下的球只能放在m-1个盒子中,方案数为
S(n-1,m-1)
2)bn与别的球共占一个盒子;那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中,然后再将球bn可以放入其中一个盒子中,方案数为
mS(n-1,m)
S(n,m)=mS(n-1,m)+S(n-1,m-1)
2022-03-04 14:37:06
228KB
acm
1