不同的对象进入不同的容器
不同的对象进入不同的容器是一种类型的问题组合其中的目标是计算可能分布到容器中的对象的数量。
一个分布将对象放入容器是对这些对象的安排,这样每个对象都被放入其中一个容器中。在这种类型的问题中,对象和容器是截然不同的.这意味着在计数分布时,哪个对象进入哪个容器很重要。
德里克正和他的朋友爱德华和弗朗辛一起吃午饭。德里克的午餐里有一个苹果、一根香蕉和一颗樱桃,他想和大家分享。德里克可以把他的一些、全部或一点水果都捐出去(例如,他可以把水果留给自己)。德里克可以用多少种方式分配他的水果?
在这个问题中,“不同的对象”是水果,而它们被分配到的“不同的箱子”是人。
这个问题可以通过列出所有的可能性来解决,但更有效的解决这个问题的方法是使用规则的产品.苹果有3个可能的目的地,香蕉有3个可能的目的地,樱桃有3个可能的目的地。因为这些对象是同时分布的,所以使用了乘积规则,因此存在 水果的可能分布。
不同对象进入不同容器的基本情况
在前面的例子中,当决定水果的可能分配时,没有考虑公平。一种可能的分配方式是让德里克把所有的水果都留给自己。另一种可能的分配是德里克把所有的水果都给了弗朗辛。在“不同的对象放入不同的容器”问题的基本情况下,每个对象都是独立放置的,这允许使用规则的产品.
假设有 要在其中分配的不同对象 不同的垃圾箱。这是完全可以做到的 的方式。
对于每个对象,有 可以放入它的箱子。这个位置发生在每一个 对象。由规则的产品,这可以在 的方式。
我们有8根不同大小的胡萝卜和2只可爱的兔子。我们可以用多少种方式喂兔子?(兔子们非常饿,所以他们将吃掉所有的8根胡萝卜。)
在这个问题中,我们可以将胡萝卜建模为对象,将兔子建模为垃圾箱。因为它们都是不同的,所以上面的公式成立。因此,兔子可以被喂养的方式的总数是 .
注意:如果你对二进制很熟悉,你可以这样想。假设我们有一个8位的二进制数字——数字的数量对应胡萝卜的数量,数字的底数对应兔子的数量。如果数字为0,则表示给第一个兔子一根胡萝卜;如果一位数字是1,这意味着第二只兔子将得到一根胡萝卜。例如,数字01100001表示 和 胡萝卜给了第二只兔子。总共有 8位二进制数,所以答案是256。
有多少方法可以 球,每个不同的颜色,分配 不同的骨灰盒?
在这个问题中,球是物体,瓮是箱子。由于每个球都有不同的颜色,它们是不同的,瓮也是不同的。因此,我们可以使用上面的公式,看到这可以在 的方式。
分配对象集的一部分
前面的示例和问题涵盖了以下情况所有对象的分布。然而,如果只是一些哪些对象是分布式的?这开启了一些有趣的可能性。
假设有 不同的对象,其中 要分配给谁 不同的垃圾箱。这是完全可以做到的 的方式。
注意: 表示二项式系数.
有 组合的 对象选择从 不同的对象。这些 对象然后被分配到 不同的垃圾箱。对于每个组合,有 分布的 对象中 箱里。因此,总共有 分布的 对象,选择从 不同的对象, 不同的垃圾箱。
爷爷乔 他正在考虑送给他的礼物 孙子。然而,他决定要留下来 为自己的礼物。他有多少种方式可以分发剩下的礼物?
在这个问题中,有 不同的对象,其中 要分配给谁 不同的垃圾箱。利用上述定理,这可以精确地做到 的方式。
这个结果实际上是更多的而不是分布的数量 不同的对象 不同的箱子, .
分发到非空容器中
更有趣和更具挑战性的问题可以通过附加条件产生。这种类型的一般公式,
有多少方法可以 球,每个不同的颜色,分配 独特的骨灰盒,没有骨灰盒是空的?
没有瓮是空的这一限制似乎无害,但它使问题比之前的问题和本wiki中的示例复杂得多。
如果我们用通式,我们直接得到 .因此 .
或
另一种解决这个问题的方法是使用包容和排斥原则.
首先,考虑如果没有这些限制会出现什么问题。让 的所有分布的集合 不同的对象 不同的垃圾箱。 .
现在我们 的所有分布的集合 不同的对象 和 箱里。同样,让 是所有分布的集合 和 垃圾箱,让 是所有分布的集合 和 箱里。
将是其中的所有分布的集合至少有一个Bin是空的。
我们的目标是找出分布的数量没有Bin是空的。这将是 .
由包容和排斥原则,
的分布数是多少 不同的对象 不同的垃圾箱。这是 .不失一般性, .
的分布数是多少 不同的对象 不同的垃圾箱。这是 .不失一般性, .
这三个容器不可能都是空的,所以 .
利用包含和排除原理公式,
因此,分布的数量 不同的球进 不同的骨灰盒,其中没有骨灰盒是空的