假设现在有p个球放入k个盒子中,对于球和盒子的属性分别做限制,然后询问方法数。这里的属性限制分别包括:球是不是相同的,盒子是不是相同的,盒子是否为空。
首先看最简单的情况:盒子可以为空,球和盒子都是不同的。那么一共有k ^ p种放法。如果规定盒子是非空的,那么就需要利用容斥原理,设第i个盒子是空的为一种属性,那么分别计算一个盒子为空的方法数,两个盒子为空。。。然后利用容斥原理就行了。
现在规定球是不同的,盒子是相同的且盒子不能为空。这是第二类stirling数,S(p, k) = k * S(p - 1, k) + S(p - 1, k - 1)。如果规定盒子可以为空,那么就是第p个Bell数,也就是对第二类stirling数k从0到k求和。
如果盒子相同,球也相同,这时候盒子空不空都无所谓了,就是一个整数划分问题,非空的话先给每个盒子装一个球再算就行了。
最后一种情况是盒子不同,球相同,如果盒子可以为空,那么问题就变成了经典的x1 + x2 + ... + xk = p,x取值范围0到p的解的个数。这是经典的组合数学问题,利用隔板法求得答案是C(k + p - 1, p)。如果盒子非空,那么就是把x的取值范围变成1到p就行了,答案是C(p - 1, p - k)。
posted on 2009-06-04 16:13
sdfond 阅读(494)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Combinatorics