相同的对象放入相同的箱子
相同的对象放入相同的箱子是组合学中的一类问题,其目标是计算将若干相同的物体放入相同的箱子的方法的个数。
尽管类似的问题不同的对象放到不同的箱子里和相同的对象放入不同的箱子有封闭形式的解决方案在美国,“将相同的对象放入相同的箱子”这个问题提出了一些特殊的挑战,需要有效地找到解决方案。
在这类问题中,对象是相同的。这意味着将哪些对象分组在一起并不重要;只关心每个箱子里有多少个物体。除此之外,箱子是相同的。这意味着箱子的顺序无关紧要,而且箱子必须是非空的。
有5个相同的球。这些球有多少种组合方式?可以有任意数量的组,并且组可以是除0以外的任何大小。
这个问题要求我们找出5个相同物体在任意数量的相同箱子中的分布数目。这些分布情况如下:
总共有 把球分组的方法。
“相同的物体放入相同的箱子”问题与的问题密切相关整数分割.将使用许多相同的解决问题的策略。“将相同的对象放入任意数量的相同容器”类型的问题等价于整数问题的划分。
与整数分区的关系
相同的对象 相同的箱子
到目前为止,本页所讨论的问题都属于“将相同的对象放入任意数量的相同箱子”的类型。这些问题可以简单地通过查找来解决 ,在那里 是对象的数量。
“相同的对象放入相同的容器”类型的问题有些不同,因为它们需要特定数量的非空容器。幸运的是,可以使用许多用于整数分区的相同问题解决策略。这个问题可以被认为是找到一个数字被分割成特定数量的部分的数量。
6个相同的球分成3组有多少种方法?
这个问题可以建模为查找的分区 到完全 部分。下面列出了这些分区:
总共有 如何把 球进 组。
如果 和 相对较小,那么很容易列出所有发行版,如上所述。对于更大的 和 ,就需要采取不同的方法递归.需要以下定理:
整数的分区数 成 的分区数是相同的 其中最大的部分是 .
配分函数的最大部分是 记为 .
这个定理的证明在整数分区页面。这个定理的好处是,它允许在一个更大的范围内找到分区可预测的的方式。
是什么 ?
根据上面的定理,这个问题的答案应该和前面的例子一样。的分区 的 其最大的部分如下所列:
和以前一样,有 分区的 的 是最大的部分。然而,有人可能会说这个版本的问题更容易解决一些。与 作为最大的一部分,有 左分区。因此,答案与 .
如果 ,然后
导致分区中第一部分总是 ,其余部分是整数的分区 .
当 , .因此,分区 在 将所有的分区 .
因此, 当 .
前面的定理适用于 的 是最大的部分。这等价于 到完全 所以前面的定理也可以应用于这类问题。
有多少种划分方法 到完全 正整数吗?
这道题的答案等于 的分区数 的 是最大的部分。
,所以
,所以有 划分的方法 成 正整数。
相同对象放入相同箱子的基本情况
让 是要在其中分配的相同对象的数量 相同的垃圾箱。关于分布的数量,有几个相对简单的例子。这些在将来会很有用,因为递归将被用来找到更复杂问题的解决方案。
案例1:
没有足够的物品可以放入每个箱子。因此,分布的数量为 .
案例2:
确实有 对象。因此,只有 分布。
案例3:
确实有 对象,和 还有更多的东西有待放置。它被放在哪个箱子里并不重要,所以有确切的 分布。
案例4:
只有一个箱子可以放这些东西,所以只有 分布。
例5:
如果 是奇数,那么分布的个数是 .如果 是偶数,那么分布的个数是多少 .
你有987美元你想存入两个相同的储蓄账户。把钱分成两组有多少种方法?
假设钱被分配成整美元。这可以建模为 相同的对象分布到 相同的垃圾箱。
的基本情况 可以使用。 是奇数,那么分布的个数是多少 .
因此,有 把钱分成两组的方法。
使用递归解决问题
当 和 变得足够大,找到的分布的数量的问题 相同的物体 相同的箱子会让人望而生畏。幸运的是,有一种方法可以使用递归把问题分解成更简单的部分。下面的定理将是解决这些问题的关键。
当各部分按从大到小排序时,每个分区按 总是以整数开头 .分割中的其余整数本身是的分割 .这些分区 能有一个最大的整数吗 和 、包容。因此, 等于所有的和 ,在那里 是一个介于 和 、包容。
解决“相同的对象放入相同的箱子”的策略将是使用上述定理,以及本页上的所有其他定理和基本情况,以尽可能有效地得到解决方案。不可能总是通过几个步骤就得到解决方案,但是递归可以将一个复杂的问题分解成更简单的问题。
把12个相同的立方体分成3组有多少种方法?每组必须至少有一个立方体,组的顺序无关紧要。
这个问题可以被认为是一个发现 .利用上述定理,
根据基本情况4, .
根据基本情况5, .
现在我们可以再用上面的定理来求 :
根据基本情况4, .
根据基本情况5, .
为 , .根据之前的定理, .
所以,
因此,有 将12个相同的立方体分成3组的方法。
的值作为参考 为 如下所列。