随笔 - 68  文章 - 57  trackbacks - 0
<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用链接

留言簿(8)

随笔分类(74)

随笔档案(68)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

  假设现在有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 阅读(471) 评论(0)  编辑 收藏 引用 所属分类: Algorithm - Combinatorics

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理