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