“n个球放入m个盒子是否为空”的方案数
如题:n个小球放到m个盒子里的方案数
1、球相同,盒子不同,不允许空
分成m段,n-1个空选m-1个放隔板 , C n − 1 m − 1 C_{n-1}^{m-1} Cn−1m−1。
2、球相同,盒子不同,允许空
(1) 加入m个球变成不允许空(假设m个盒子先每个都放1个球)
(2) m-1个隔板和球放在一起,从中选m-1个做隔板, C n + m − 1 m − 1 C_{n+m-1}^{m-1} Cn+m−1m−1
3、球相同,盒子相同,不允许空
就是整数划分问题啊…n个数写成m个数的和的形式的方案数
f[i][j]=f[i−1][j−1]+f[i−j][j]
有1的话就是f[i−1][j−1],没有1的话就拿出j个1先放上再分剩下的,f[i−j][j]
4、球相同,盒子相同,允许空
∑ j = 1 m f [ n ] [ j ] \sum_{j=1}^mf[n][j] ∑j=1mf[n][j]
5、球不同,盒子相同,不允许空
第二类Stirling数:n个不同的元素分成m个集合的方案数 S ( n , m ) S(n,m) S(n,m)
S(i,j)=S(i−1,j−1)+S(i−1,j)∗j
,S(n,n)=1n≥0, S(n,0)=0,n≥1
考虑一个元素可以放入一个空集合或者已经有元素的集合(j种选择)
6、球不同,盒子相同,允许空
枚举非空盒子数量
∑ j = 1 m S ( n , j ) \sum_{j=1}^mS(n,j) ∑j=1mS(n,j)
7、球不同,盒子不同,不允许空
盒子全排列标号就行了
S ( n , m ) ∗ m ! S(n,m)∗m! S(n,m)∗m!
8、球不同,盒子不同,允许空
不能简单的全排列标号,因为空盒子标号没有意义
所以枚举非空盒子数量的时候乘上个组合数和全排列标号
∑ j = 1 m S ( n , j ) ∗ A ( m , j ) \sum_{j=1}^mS(n,j)*A(m,j) ∑j=1mS(n,j)∗A(m,j),其中A是排列 A ( m , j ) = C ( m , j ) ∗ j ! A(m,j)=C(m,j)*j! A(m,j)=C(m,j)∗j!
文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。
原文链接:gwj1314.blog.csdn.net/article/details/82991224
- 点赞
- 收藏
- 关注作者
评论(0)