相同的对象进入相同的容器

相同的对象放入相同的容器中是组合学中的一类问题，其目标是计算将若干相同对象放入相同容器的方法的数量。

虽然类似的问题不同的对象进入不同的容器和相同的对象放入不同的容器中有封闭形式的解决方案在美国，“相同的对象放入相同的容器”问题提出了一些特别的挑战，以有效地找到解决方案。

在这种类型的问题中，对象是相同的。这意味着将哪些对象组合在一起并不重要;它只与每个容器中有多少对象有关。除此之外，容器是相同的。这意味着容器的顺序无关紧要，容器必须是非空的。

有5个相同的球。这些球有多少种分组方式?可以有任意数量的组，组的大小可以是除0之外的任意大小。

---

这个问题要求我们找出5个相同对象在任意数量相同容器中的分布数量。这些分布如下所示:

总的来说，有 $\盒装{7}$把球分组的方法。

“相同的对象放入相同的容器”问题与问题密切相关分区一个整数．将使用许多相同的解决问题的策略。“相同的对象进入任意数量相同的容器”类型的问题等同于整数问题的划分。

如果你去过整数分割Wiki页面，那么之前的问题似乎很熟悉。事实上，有一个双射在5个对象的分布和整数5的分区之间。这对分布也是成立的 $n$将相同的对象放入任意数量的相同容器中。

的分布数 $n$相同的对象放入任意数量相同的容器中 $p (n)$,在那里 $p (n)$是配分函数。

供参考，配分函数的值为 $n \勒7$下面列出。注意，函数定义为值为 $1$在 $n = 0$：

$\{数组}{c | c}开始n和p (n) \ \ \线0 & 1 \ \ 1 & 1 \ \ 2 & 2 \ \ 3 & 3 \ \ 4 & 5 \ \ 5 & 7 \ \ 6 & 11 \ \ 7 & 15 \ \ \{数组}结束$

到目前为止，本页讨论的问题都是“相同的对象放入任意数量的相同容器”。这些问题可以简单地通过寻找来解决 $p (n)$,在那里 $n$为对象的数量。

“相同的对象放入相同的容器”类型的问题有些不同，因为它们需要特定数量的非空容器。幸运的是，可以使用许多用于整数分区的相同问题解决策略。这个问题可以认为是找出一个数字分成特定数量的部分的分区数。

6个相同的球分成3组有多少种方法?

---

这个问题可以建模为找到的分区 $6$到完全 $3.$部分。下面列出了这些分区:

$4 + 1 + 1$ $3 + 2 + 1$ $2 + 2 + 2$

总的来说，有 $\盒装{3}$表达方式 $6$球进 $3.$组。

如果 $n$和 $r$是相对较小的，那么就很容易列出所有的分布，如上所述。对于更大的 $n$和 $r$，则需要采取不同的方法递归．需要下面的定理:

一个整数的分区数 $n$成 $r$的分区数与分区数相同 $n$最大的部分是 $r$．

配分函数的最大部分是 $r$表示为 $p (n, r)$．

这个定理的证明在整数分区页面。这个定理的好处是它允许在更大的范围内找到分区可预测的的方式。

是什么 $p (6,3)$？

---

根据上述定理，这个问题的答案应该与前面的例子相同。的分区 $6$的 $3.$最大的部分如下所列:

$3 + 3$ $3 + 2 + 1$ $3 + 1 + 1 + 1$

和以前一样，有 $\盒装{3}$分区的 $6$的 $3.$是最大的部分。然而，有人可能会说，这个版本的问题更容易解决。与 $3.$作为最大的部分，有 $3.$分区。因此，答案是一样的 $(3页)$．

如果 $n \ le 2 r$,然后 $p (n, r) = p (n-r)$

$p (n, r)$导致分区的第一部分总是 $r$，其余部分是整数的分区 $n-r$．
当 $n \ le 2 r$， $n-r le r \$．因此，分区 $n-r$在 $p (n, r)$将所有划分 $n-r$．
因此, $p (n, r) = p (n-r)$当 $n \ le 2 r$．

上述定理适用于的划分 $n$的 $r$是最大的部分。这等价于分割 $n$到完全 $r$因此，上述定理也可以应用于这类问题。

有多少种划分方法 $1729$到完全 $1726$正整数吗?

---

这个问题的答案等于 $p(1729、1726)$，分区数 $1729$的 $1726$是最大的部分。

$1729 \ \ times1726 le 2$,所以 $p(1729、1726)= p (1729 - 1726) = (3)$

$p (3) = 3$，所以有 $\盒装{3}$分区的方法 $1729$成 $1726$正整数。

让 $n$是分配给相同对象的数量 $r$相同的垃圾箱。对于分布的数量，有几种相对简单的情况。这些在将来会很有用，因为递归将用于寻找更复杂问题的解决方案。

案例1: $n < r$

每个箱子里没有足够的东西。因此，分布的数量为 $0$．

案例2: $n = r$

有完全 $1$对象为每个容器。因此，只有 $1$分布。

案例3: $n = r + 1$

有完全 $1$对象，并 $1$更多的物体有待放置。它被放入哪个箱子并不重要，所以有确切的 $1$分布。

案例4: $r = 1$

只有一个容器可以存放对象，所以只有 $1$分布。

例5: $r = 2$

如果 $n$是奇数，那么分布的数目是 $\ dfrac {n} {2}$．如果 $n$是偶数，那么分布的数目是多少 $\ dfrac {n} {2}$．

你想把987美元存入两个相同的储蓄账户。把钱分成两组有多少种方法?

---

假设货币是按美元总额分配的。可以将其建模为 $n = 987$相同的物体分布在 $r = 2$相同的垃圾箱。

的基本情况 $r = 2$可以使用。 $987$是奇数，那么分布的数目是 $\ dfrac {n} {2} = \ dfrac {986} {2} = 493$．

因此,有 $\盒装{493}$把钱分成两组的方法。

当 $n$和 $r$变得足够大，找到分布的数量的问题 $n$相同的对象 $r$相同的容器可能令人生畏。幸运的是，有一种方法可以利用递归把问题分解成更简单的部分。下面的定理将是解决这些问题的关键。

$p (n, r) = \ \ limits_总和{k = 1} ^ {r} {p (n-r k)}$

当部分排序从大到小，每个分区计数 $p (n, r)$总是以整数开始 $r$．分区中的其余整数本身就是的分区 $n-r$．这些分区的 $n-r$之间的最大整数是多少 $1$和 $r$、包容。因此, $p (n, r)$等于所有的总和吗 $p (n-r k)$,在那里 $k$是介于 $1$和 $r$、包容。

解决“将相同的对象放入相同的箱子”的策略是使用上述定理，以及本页上的所有其他定理和基本情况，以尽可能高效地得到一个解决方案。用几个步骤来解决问题并不总是可能的，但递归将使把一个复杂的问题分解成更简单的问题成为可能。

把12个相同的立方体分成3组有几种方法?每个组必须至少有一个立方体，组的顺序无关紧要。

---

这个问题可以被认为是发现 $3 p(12日)$．利用上述定理，

$3 p(12日)= p (9,1) + p(9日2)+ p (9, 3)$

根据基本情况4， $p (9,1) = 1$．

根据基本情况5， $2 p(9日)= 4$．

现在我们可以用上面的定理来求 $3 p(9日)$：

$3 p(9日)= p (6,1) + (6 2) + p (6 3)$

根据基本情况4， $p (6,1) = 1$．

根据基本情况5， $p (2) = 3$．

为 $p (6,3)$， $n \ le 2 r$．根据之前的定理， $p (6,3) = p (3) = 3$．

所以, $3 p(9日)= 1 + 3 + 3 = 7$

$3 p(12日)= p (9,1) + p(9日2)+ p (9, 3) = 1 + 4 + 7 = 12$

因此,有 $\盒装{12}$将12个相同的立方体分成3组。

的值作为参考 $p (n, r)$为 $r \ n, le 7$下面列出。

$开始\{数组}{c | c c c c c c c} _n”\反斜杠^ r & 1 & 2 & 3 & 4 & 5 & 6 & 7 \ \ \线1 & 1 \ \ 2 & 1 & 1 \ \ 3 & 1 & 1 & 1 \ \ 4 & 1 & 2 & 1 & 1 \ \ 5 & 1 & 2 & 2 & 1 & 1 \ \ 6 & 1 & 3 & & 2 & 1 & 1 \ \ 7 & 1 & 3 & 4 & 3 & 2 & 1 & 1 \ \ \{数组}结束$