相同的对象放入不同的箱子

相同的物体放入不同的箱子是组合学中的一个问题，其目标是找出若干相同对象在若干不同容器中的分布数量。这个问题的表述与以下问题类似不同的对象放入不同的箱子而且不同的物品放入相同的箱子，但解决这类问题的方法是完全不同的。

假设有4个相同的球分配给3个孩子。球有多少种分配方式?

---

在这个问题中，球被建模为相同的物体，而孩子被建模为不同的箱子。这些分布可以详尽地列出如下:

总之，有 $\盒装{15}$分布。

在这一页所列出的问题中，每一个被分配的物体都是一样的，但是每个物体给每个人或地方的数量是有关系的。一个相关的例子是，假设所有的拨款分配都是相同的，研究主任会计算分配给研究小组的拨款分配有多少种方式。得到较少拨款的研究小组肯定会注意到这一点，但是研究主任在决定拨款时也必须考虑她的组织的目标。对所有可能分配的拨款进行核算，将使研究主任对如何分配资金有一个大致的了解。

在介绍中的示例中，详细地列出了分布并作为一个集合列出。不幸的是，这不是一种非常有效的计算分布的方法。要想出一种有效的方法来计算分布需要一些创造性的思维。这种方法,称为恒星和酒吧，也用于其他领域组合．

想象这4个物体排成一条直线，如图所示为星星:

$\ \大星\星\星\星$

通过在星星之间或在星星的末端放置条条，这些物体可以被分成箱子:

$\ \大星\星\星| \星$

$大| \ \星\星\星\星$

放置1条创建2个不同的组。将条放在其中一端将创建一个0星的组。

放置2个条将创建3个不同的组:

$\ \大星| \星\星| \星$

$\ \大明星| | \星\星\明星$

将条形图相邻放置可以创建一个0星组。

一般来说，如果我们想把恒星分成 $r$不同的群体，这将需要 $r 1$酒吧。

回到将4个相同的对象分布到3个不同组的问题。以星星和杠为模型，将有4颗星星和2根杠。有 $4 + 2 = 6$需要放置的东西，其中两个位置被选为木条。因此,有 $\ binom {6} {2} = 15$4个相同的物体可能分布在3个不同的组中。这和前面的答案是一致的。

假设有 $n$要分布在其中的相同对象 $r$不同的垃圾箱。这可以精确地做到 $\ binom {n + r 1} {r 1}$的方式。

像星星和棒子一样，有 $n$星星排成一行 $r 1$把他们分成 $r$不同的组。总共有 $n + r 1$东西会被放置，和 $r 1$在这些位置中选择了杠杠。星星将被放在其余的位置上。因此,有 $\ binom {n + r 1} {r 1}$可能的位置。同样,有 $\ binom {n + r 1} {r 1}$可能的分布 $n$相同的对象之一 $r$不同的垃圾箱。

有10个相同的香蕉将分配给5只不同的猴子。香蕉有多少种分配方式?

---

在本例中，有 $n = 10$相同的对象和 $r = 5$不同的垃圾箱。用上面的公式，有 $\ binom{14}{4} = \盒装{1001}$香蕉的分配方法。

前面的问题和示例涵盖了垃圾箱可能被空着的情况。现在考虑当箱子被要求为非空时，问题会发生怎样的变化。幸运的是，可以使用类似的方法。

考虑这样一个问题:我们试图找出5个不同的容器中8个相同对象的分布数量，且容器不能为空。将问题建模为星形和条形，它会像这样开始:

$\ \大明星\星\星\星\星\明星\星\星$

就像前面的例子一样，格数将是 $1$少于箱子的数量。所以我们有 $4$酒吧到另一个地方。它们可以放在哪里?回想一下前面的例子，如果将条放在末尾或相邻的条，则会创建空组。所以为了有没有空组，条形图只能放置在星星之间，一对星星之间只能放置一个条形图。

$\ \大星| \星| \星\星| \星\星| \星\星$

有完全 $7$符合这些标准的潜在地点。换句话说, $1$小于对象的数量。这些 $7$潜在的位置, $4$酒吧被放置。因此,有 $\ binom {7} {4} = 35$8个相同的物体可能分布到5个不同的非空箱子。

假设有 $n$要分布在其中的相同对象 $r$不同的非空的垃圾箱，与 $n \通用电气r$．这可以精确地做到 $\ binom {n} {r 1}$的方式。

对于这类问题， $n \通用电气r$必须是真实的。如果 $n < r$，那么就没有足够的对象来至少用一个对象填满每个箱子。

像星星和棒子一样，有 $n$明星和 $r 1$酒吧到另一个地方。为了使组不为空，条形图只能放在星星之间，一对星星之间只能放一个条形图。因此,有 $n - 1$酒吧的可能位置。从这些 $n - 1$可能的位置, $r 1$被选为杠。因此，星星和棒子可能的排列方式是 $\ binom {n} {r 1}$．同样,有 $\ binom {n} {r 1}$分布的 $n$相同的对象 $r$不同的非空垃圾箱。

一个老师有12支相同的铅笔要分配给9个不同的学生。有多少种方法可以分配这12支铅笔，让每个学生至少得到一支铅笔?

---

在本例中，有 $n = 12$要分布在其中的相同对象 $r = 9$不同的垃圾箱。利用上述公式，可能的分布数为 $\ binom{11}{8} = \盒装{165}$．