不同的对象进入相同的容器
不同的对象放入相同的容器中是一个问题组合其中的目标是计算有多少可能的对象分布到容器中,这样就不需要每个对象进入哪个容器,但需要将哪些对象组合在一起。这个问题通常比相关的放置问题更棘手不同的对象进入不同的容器.
假设有4朵不同的玫瑰插在2个相同的花瓶里。玫瑰有多少种排列方式?
如果一个规则的产品如果我们尝试一种方法,问题就变成了:“第一、第二、第三或第四朵花去了哪里?”然而,这并不能解释有相同的花瓶,因为不管所有的花都被放在了第一个花瓶还是第二个花瓶。无论哪种情况,最终结果都是一样的。
既然对如何进行没有明确的想法,就简单地列出所有的方法。请注意,在总共8种方法中,有7种方法涉及两个花瓶:
在这个wiki中,目标是理解如何以合理的方式处理一般情况。列出案例是极其乏味的,并且可能导致重复计算或遗漏案例。不像将不同的对象计数到不同的容器中,它有一个简单的双射论证,这个过程稍微复杂一些,会把你引向递归.
考虑以下两种情况:
- 不同的对象进入相同的垃圾箱,没有空的垃圾箱-第二类斯特林数字
- 不同的对象放入任意数量相同的容器-贝尔号
第二类斯特灵数的基本情况
一个第二类斯特灵数,表示 或 ,是一组方法的个数 元素可以被划分成 非空集。
同样地,第二类Stirling数可以确定在相同的非空容器中有多少种不同的对象可以分布。在本节中,我们将探讨第二类斯特林数的基本情况,以便更好地理解如何解决“不同对象放入相同容器”的问题。
让 是要分布在其中的不同对象的数量 相同的垃圾箱。
考虑以下箱子数量与对象数量接近的情况:
1.>对象数量:
显然,由于每个箱子至少需要1个对象,所以没有足够的对象来分配。因此,这样做的方法的数量是 .2.bin的数量=对象的数量:
显然,每个箱子必须恰好有一个物体。因为箱子是相同的,所以每个箱子都包含1个对象,箱子的顺序并不重要。因此,只有 道路3.容器数量=对象数量- 1:
有一个容器包含2个对象,其余的容器都包含1个对象。因此,找到选择2个对象并将其放入一个容器的方法的数量就足够了,而其余的将进入相同的容器。因此,有 做这个的方法。4.容器数量=对象数量- 2:
有2个“额外的”物体要放置。有两种可能的情况:
- 3个对象在一个箱子:有 选择3个对象进入这个箱子的方法。
- 两个对象在一个箱子里,发生两次:首先,有 选择4个物体的方法,然后有 将它们放入2个物品的2个箱子。因此,有 的方式。
因此,有 的方式。
这个过程可以继续下去,但随着需要研究的病例数量的增加,它很快变得复杂起来。
将7个不同的对象放入5个非空相同的容器有多少种方法?
这些对象要么位于 或 注意,对象的顺序并不重要,重要的是哪些对象被组合在一起。对于第一种情况,有 方法选择分组的3个对象。然后,在第二种情况下,有 从7个对象中选择4个对象的方法,然后有 将这四个物体分成两组,每组2个。排列对象的方法总数为
注意,这也可以用上面的公式来计算。
现在考虑箱子数量很小的情况。
箱数= 1:
显然,如果箱子的数量是1,那么所有的对象都必须在这个箱子里。因此,只有 做得好。箱数= 2:
考虑一个稍微不同的场景,其中有 把球放在两个箱子里。如果箱子不一样,则有 球的分布,因为每个球可以进入任何一个箱子。然而,其中两种分布涉及将所有的球放入一个容器中。因此,有 这些球可以被放入 不相同的箱子,没有一个箱子是空的。现在考虑如何修改这个场景,以反映相同的容器。要有球 在第一个箱子和球 在第二个箱子里。球的分布是相同的 在第一个箱子和球 在第二个箱子里。有 将不同的对象分配到不同的容器中 将不同的对象分布到相同的容器中。因此,分发到相同的容器两倍计算,所以总数是:
现在已经考虑了几个基本情况,策略转移到如何使用这些基本情况来发展递归关系 对于任何 对象的数量和 箱子的数量。
第二类斯特林数的一般情况
这是一个总结使用斯特林表示法计算上一节的结果:
要有 要分配的不同对象 相同的垃圾箱。然后
- .
- .
- .
- .
- .
从这些基本情况来看,的任何值 可以通过递归关系:
要发展这种关系,先考虑一个固定的对象,然后再考虑其余对象的去向。有两种情况:
- 案例1:固定对象在它自己的容器中。
有 其余要分发到的对象 箱,给 这种情况下的分布。- 案例2:固定对象与其他对象在同一个容器中。
剩下的 对象分布到 箱,给 分布。对于每个发行版,都有 将固定对象与其他对象分组的方法。因此,有 这种情况下的分布。把这两种情况加起来就得到了结果
递归关系允许人们从基本情况计算第二类斯特林数。
有多少种方法可以将5朵花放入3个相同的箱子(这样没有一个箱子是空的)?
目标是找到 .根据递归关系,
的值 和 从基本情况可以得出: 和 .因此,
现在考虑一个多次使用递归关系的例子:
将7朵花放入4个箱子有多少种方法?
目标是找到 .根据递归关系,
这些值不能从基本情况中得出,但可以利用递归关系再次分别计算。
根据递归关系,基本情况,以及前面的例子,
从递归关系,基本情况,和前面的例子,
把这个放在一起,
这些例子显示了递归关系的威力,它允许人们计算的任意值 从其他价值观 .为了参考,这里有一个列表 为
身高不同的人都想拍照。它们形成完全 垂直行,使每一行按照高度的顺序排列。有多少种方法可以做到这一点?
这开始看起来像是在安排 人们进入 行。验证第二类斯特林数可以解决问题:
- 是的,这些人的身高各不相同。
- 相同的盒子:是的,行的顺序无关紧要。
- 装箱:是的,物品的顺序无关紧要,因为只有 按照高度递增的顺序排列。
因此,它等于 (从上表中获得)。
证明了感应那 .
基本情况: , . .因此,基本情况得到了验证。
归纳假设:假设它对某些人是正确的 .通过递归关系:
因此,通过数学归纳法,这种说法是正确的。
贝尔的数字
前面的示例要求将对象放置在特定数量的非空容器中。还有一个相关的问题,即对象可以放置在任意数量的非空容器中。考虑一下这个例子:
有 不同的花。有多少种方法可以将它们种植到相同的花瓶中?
这些花可以放在 , , ,或 花瓶。因此,花瓶中鲜花的分布数量将是第二类斯特灵数的总和:
的贝尔的数字数一数有多少种方法 不同的对象可以分布到 相同的非空箱子。在集合语言中,贝尔数计算一组的分区 对象转换为非空的不相交子集,这些子集的并集是整个集合。
斯特灵数表示排列方式的数量
不同的对象
相同的盒子,
贝尔数表示排列方式的数量
把不同的物体分成
相同的对象。
因此,贝尔数被计算为斯特林数的和:
从斯特灵数的表中,下列贝尔数被计算为每个贝尔数的和 行:
贝尔数有它们自己的递归关系:
这可以用组合学来证明。考虑如何 元素是分区。假设有 元素不在它的盒子里,然后就有了 选择这些的方法 元素,其后就有了 排列这些的方法 元素放入相同的盒子中。因此,有 这样的安排。所得到的贝尔数是所有这些排列的所有可能值的总和 .
有趣的是指数生成函数贝尔号码是
证明这一点的最简单的方法是证明前面的递归关系解释了原因 ,通过求解得到结果微分方程和评估 .
假设 是 不同的素数。有多少种写法 是正整数的乘积 在美国,术语的顺序不重要?
考虑如何将 不同的质数在相同的方框里给了我们一种写法 是正整数的乘积。首先,找出乘积中每一项的质因数分解,并将每一项的因数放入框中。然后,自 是不同质因数的乘积,每个质因数出现在一个唯一的方框中。因为这些项的乘积是 ,每个质因数必须在一个方框中。
相反地,给定这些的任何排列 不同质数进 相同的方框,将方框中的质数相乘得到一项,这些项的乘积得到值 .这就建立了双射。因此,方法的数量是