相同的对象进入不同的容器
相同的对象放入不同的容器中是组合学中的一个问题,其目标是找出若干相同对象在若干不同容器中的分布数量。这个问题的措辞与问题类似不同的对象进入不同的容器和不同的对象放入相同的容器中,但解决这类问题的方法却大不相同。
假设有4个相同的球要分配给3个孩子。球有多少种分配方式?
在这个问题中,球被建模为相同的对象,而子容器被建模为不同的容器。分布可以详细列出如下:
总之,有 分布。
在这一页列出的各种问题中,每个分布的对象都是相同的,但每个对象分配给每个人或地方的数量是有关系的。一个相关的例子是,假设所有拨款都是相同的,研究主管会计算有多少种方式可以分配给研究小组。分配较少的研究小组肯定会注意到,但是研究主任在决定分配时也必须考虑她的组织的目标。对所有可能的拨款分配情况进行统计,可以让研究主任了解如何分配资金。
星条旗法
在介绍的例子中,分布被详尽地映射出来并作为一个集合列出。不幸的是,这不是一种非常有效的计算分布的方法。想出一种有效的计算分布的方法需要一些创造性的思维。这种方法,称为恒星和酒吧,也用于其他领域组合.
想象4个物体排成一条线,这里用星星表示:
通过在星星之间或星星的末端放置一根横杆,这些物体可以被分成若干个箱子:
放置1条杠创建2个不同的组。将条形条放置在其中一端将创建一个0星的组。
放置2根棒子将创建3个不同的组:
相邻放置条形图将创建一个0星的组。
一般来说,如果我们把星星分成 这需要不同的群体 酒吧。
回到把4个相同的物体分配给3个不同的组的问题上。模型为星和条,将有4颗星和2条条。有 需要放置的东西,其中2个位置被选为条形图。因此,有 在3个不同的组中4个相同的物体可能的分布。这与之前的答案是一致的。
一般情况下,相同的对象进入不同的组
分配到非空容器中
前面的问题和示例介绍了容器可以空的情况。现在考虑一下,当容器被要求为非空时,问题会发生什么变化。幸运的是,可以使用类似的方法。
考虑这样一个问题,我们试图在5个不同的容器中找到8个相同对象的分布数量,而容器不能是空的。将问题建模为星形和条形,一开始看起来是这样的:
就像前面的例子一样,条形图的数量是 小于箱子的数量。所以我们有 酒吧到另一个地方。它们可以放在哪里?如果您还记得前面的示例,如果将条形图放在末端或其他条形图旁边,则会创建空组。所以为了有没有空组,条形只能放置在星星之间,一对星星之间只能放置一个条形。
有完全 符合这些标准的潜在位置。换句话说, 小于对象的数量。这些 潜在的位置, 酒吧被放置。因此,有 8个相同的对象可能分布到5个不同的非空容器中。
假设有 要分配的相同对象 不同的非空桶,与 .这是完全可以做到的 的方式。
对于这类问题, 必须是真实的。如果 ,则没有足够的对象来填充每个容器至少一个对象。
有星星和条形的模型 明星和 酒吧到另一个地方。为了使组非空,条形条只能放置在星星之间,一对星星之间只能放置一个条形条。因此,有 酒吧的可能位置。从这些 可能的位置, 被选为酒吧。因此,恒星和棒的可能排列的数量是 .同样,有 分布的 相同的对象 不同的非空垃圾箱。
一个老师有12支相同的铅笔,分发给由9个不同的学生组成的教室。分配12支铅笔的方法有多少种使每个学生至少得到一支铅笔?
在本例中,有 要分配的相同对象 不同的垃圾箱。利用上面的公式,可能分布的数目为 .