不同的对象放入相同的箱子

不同的物品放入相同的箱子是一个问题组合它的目标是计算有多少对象可能分布到垃圾箱中，这样每个对象进入哪个垃圾箱并不重要，但哪些对象被分组在一起却很重要。这个问题通常比相关的放置问题更棘手不同的对象放入不同的箱子．

假设有4朵不同的玫瑰将被放入2个相同的花瓶中。玫瑰有多少种排列方式?

如果一个乘积法则当我们尝试这种方法时，问题就变成了:“第一朵、第二朵、第三朵或第四朵花去了哪里?”然而，这并不能说明花瓶是完全相同的，因为这些花是全部进入了第一个花瓶还是全部进入了第二个花瓶并不重要。无论哪种情况，最终结果都是一样的。

既然没有明确的想法如何进行，就简单地列出所有的方法。请注意，在总共8种方法中，有7种都涉及到花瓶:

在本维基中，我们的目标是了解如何以合理的方式处理一般情况。列出病例非常繁琐，很可能导致重复计算或遗漏病例。不像将不同的对象计数到不同的容器中，其中有一个简单的双射参数，这个过程稍微复杂一些，并将引导您沿着路径递归．

考虑以下两种情况:

1. 不同的对象放入相同的箱子中，没有空箱子-第二类斯特林数
2. 不同的对象进入任何数量相同的箱子-贝尔号码

一个第二类斯特林数，表示为 $年代(n, r)$或 $\左\{n \顶r\右\}$，是一组方法的个数 $n$元素可以被划分 $r$非空集。

同样地，第二类斯特林数可以确定在相同的非空箱子中有多少种不同的物体可以分布。本节将探讨第二类斯特林数的基本情况，以便更好地理解如何解决“不同的对象放入相同的箱子”问题。

让 $n$是要分布的不同对象的数量 $r$相同的垃圾箱。

考虑这些情况，在这些情况下，箱子的数量接近对象的数量:

1.>对象数量:
显然，由于每个箱子至少需要1个对象，所以没有足够的对象来分配。因此，这样做的方法的数量是 $0$．

2.bin数量=对象数量:
显然，每个bin必须只有一个对象。由于箱子是相同的，每个箱子都包含一个对象，箱子的顺序无关紧要。因此，只有 $1$道路

3.bin数量=对象数量- 1:
其中一个容器包含2个对象，其余的容器每个容器将包含1个对象。因此，找到选择两个对象并将其放入一个容器的方法的数量就足够了，而其余的将放入相同的容器。因此，有 $\ binom {n} {2}$这样做的方法。

4.bin数量=对象数量- 2:
有2个“额外的”对象要放置。有两种可能的情况:

• 一个箱子里有3个物体:有 $\ binom {n} {3}$选择3个对象进入这个箱子的方法。
• 一个箱子里有两个对象，出现了两次:首先，有 $\ binom {n} {4}$选择4个对象的方法，还有 $\ binom {4} {2} \ div2 = 3$把它们放在两个箱子里的方法。因此，有 $\binom{n}{4} \乘以3$的方式。

因此，有 $\binom{n}{3} + 3 \binom{n}{4}$的方式。

这个过程可以继续，但很快就会因为需要研究的案例数量而变得复杂。

将7个不同的物体放入5个相同的非空箱子有多少种方法?

---

这些物体要么在一个分布中 $1 | 1 | 1 | 1 | 3$或 $1 | 1 | 1 | 2 | 2。$注意，对象的顺序并不重要，重要的是哪些对象被分组在一起。对于第一种情况，有 $\ binom {7} {3}$选择3个对象分组的方法。然后，在第二种情况下，有 $\ binom {7} {4}$从7个对象中选择4个对象的方法，还有 $\ binom {4} {2} \ div 2 = 3$将这4个物体分成2组的方法。排列对象的方法总数是

$\binom{7}{3}+3\binom{7}{4} = 140。\ _ \广场$

注意，这也可以用上面的公式计算。

现在考虑箱子数量很小的情况。

• 箱数= 1:
  显然，如果箱子的数量是1，那么所有的对象都必须在这个箱子里。因此，只有 $1$做得好。

• 箱数= 2:
  考虑一个稍微不同的场景，那里有 $n$球在两个箱子里。如果箱子是不一样的，那么就有 $2 ^ n$球的分布，因为每个球可以进入任意一个箱子。然而，其中两种分布涉及将所有球放入一个箱子中。因此，有 $2 n ^ 2$这些球可以被放入 $2$不相同的箱子，没有空的箱子。

• 现在考虑如何修改这个场景，以反映两个箱子是相同的。要有球 $\ mathfrak {B} _1$在第一个箱子和球里 $\ mathfrak {B} _2$在第二个箱子里。有球的分布是等价的 $\ mathfrak {B} _2$在第一个箱子和球里 $\ mathfrak {B} _1$在第二个箱子里。有 $2$将不同的对象分布到不同的容器中 $1$将不同的物品分配到相同的箱子中。因此，分配到相同的箱子两倍计算，则总数为:

$\frac{2^n - 2} {2} = 2^{n-1} -1。$

现在已经考虑了几个基本的情况，策略转向如何使用这些基本的情况来开发递归关系 $年代(n, r)$对于任何 $n$对象数量和 $r$箱子的数量。

这是一个总结使用斯特林符号计算上一节的结果:

让它存在吧 $n$要分配给不同的对象 $r$相同的垃圾箱。然后

1. $\quad r > n\表示S(n, r) = 0$．
2. $\quad r = n\表示S(n,n) = 1$．
3. $\quad r = n-1 \表示S(n, n-1) = {n \ select 2}$．
4. $\quad r = n-2 \表示S(n, n-2) = {n \choose 3} + 3 {n \choose 4}$．
5. $\quad r = 1\表示S(n,1) = 1$．
6. $\quad r = 2\表示S(n,2) = 2^{n-1} -1。$
   

从这些基本情况，任何值 $年代(n, r)$可以通过计算递归关系：

$S(n,r) = r S(n-1, r) + S(n-1, r-1)$

证明

要建立这种关系，请考虑固定一个对象，然后考虑其余对象的位置。有两种情况:

• 案例1:固定对象在自己的bin中。
  有 $n - 1$要分布到的剩余对象 $R - 1$箱子，它给出 $S(n-1, r -1)$这种情况下的分布。
• 案例2:固定对象与其他对象同在一个bin中。
  剩下的 $n - 1$对象被分布到 $r$箱子，它给出 $年代(n - 1右)$分布。对于每个分布，都有 $r$将固定对象与其他对象分组的方法。因此，有 $rS (n-1, r)$这种情况下的分布。

把这两种情况加起来就得到了结果

$S(n,r) = r S(n-1, r) + S(n-1, r-1)。\ _ \广场$

递归关系允许人们从基本情况计算第二类斯特林数。

有多少种方法可以将5朵花放入3个相同的盒子里(不存在空盒子)?

---

我们的目标是找到 $S(5,3)$．根据递归关系，

$S(5,3)= 3s (4,3)+ S(4,2)。$

的价值 $(4,3)$而且 $S(4,2)$从基本案例可以得出: $S(4,3) = {4 \ select 2} = 6$而且 $S(4,2) = 2^{4-1} -1 = 7$．因此,

$S(5,3) = 3 \ * 6 + 7 = 25。\ _ \广场$

现在考虑一个多次使用递归关系的例子:

将7朵花放入4个箱子有多少种方法?

---

我们的目标是找到 $4 S(7日)$．根据递归关系，

$S(7 4) = 4(6, 4) +年代(6 3)。$

这些值不能从基本情况中得出，但可以再次使用递归关系分别计算它们。

从递归关系、基本情况和前面的例子中，

$年代(4)= 4(4)+年代(5,3)= 4 \ * 10 + 25 = 65。$

同样从递归关系，基本情况，和之前的例子，

$(6,3) = 3 S (5,3) + S(2) = 3 \ * 25 + 15 = 90。$

把这些放在一起，

$S(7,4) = 4 \乘以S(6,4) + S(6,3) = 4 \乘以65 + 90 = 350。\ _ \广场$

这些例子显示了递归关系的力量，它允许计算的任何值 $年代(n, r)$从其他价值 $年代(n, r)$．为供参考，这里有一份清单 $年代(n, r)$为 $N \leq 7:$

$\开始{数组}{c | c c c c c c} _n”\反斜杠^ r & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \ \ \线0 & 1 \ \ 1 & 0 & 1 \ \ 2 & 0 1 \ \ 3 & 4 0 &1&3&1 \ \ & 0 &1&7&6&1 \ \ 5 & 6 0 &1&15&25&10&1 \ \ & 0 & 1 & 31日& 90 & 65 & 15 & 1 \ \ 7 & 0 & 1 & 63 & 301 & 350 & 140 & & 1 \ \ \{数组}结束$

$7$身高不同的人想要拍照。它们完全形成 $3.$垂直排列，这样每一行都按高度顺序排列。有多少种方法?

---

这开始看起来像安排了 $7$人们进入 $3.$行。验证问题可以用第二类斯特林数解决:

• $7$不同的物体:是的，这些人都有不同的高度。
• $3.$相同的盒子:是的，行顺序无关紧要。
• 放进盒子:是的，物品的顺序并不重要，因为只有 $1$按高度递增顺序排列的方法。

因此，它等于 $S(7,3) = 301$(由上表得出)。 $_ \广场$

证明了感应那 $S(n,3) = \frac{3^{n-1} + 1} {2} - 2 ^{n-1}$．

---

基本情况: $N = 3$， $S(3,3) = 1$． $3 ^ \压裂{{n} + 1} {2} - 2 ^ {n} = \压裂{3 ^ 2 + 1}{2}- 2 ^ 2 = 5 - 4 = 1$．因此，基本情况得到验证。

归纳假说:假设它对某些人是正确的 $N = k$．由递归关系式:

$\{对齐}年代开始(k + 1, 3) & = 3 S (k, 3) + S (k, 2 ) \\ & = 3 \离开(\压裂{3 ^ {k - 1} + 1} {2} - 2 ^ {k - 1} \右)+左(\ \ vphantom{\压裂{3 ^ {k}} {2}} 2 ^ {k - 1} - 1 \ ) \\ & = \ 压裂{3 ^ k + 1} {2} - 2 ^ {k}。结束\{对齐}$

因此，通过数学归纳法，这个陈述是正确的。 $\ _ \广场$

前面的例子要求对象被放置在特定数量的非空箱子中。还有一个相关的问题，物体可以放置在任意数量的非空箱子中。想想这个例子:

有 $4$不同的花。一模一样的花瓶有几种栽法?

---

这些花可以放在里面 $1$， $2$， $3.$,或 $4$花瓶。因此，花瓶中鲜花的分布数量将是第二类斯特林数的和:

$(4,1) +年代(4,2)+(3)+年代(4,4)= 1 + 7 + 6 + 1 = 15。\ _ \广场$

的贝尔的数字数一数方法的数量 $n$不同的对象最多可以分布到 $n$相同的非空箱子。在集合的语言中，贝尔数计数一个集合的分区 $n$对象划分为非空不相交子集，这些子集的并集就是整个集合。 $_ \广场$

斯特林数表示排列方式的数量 $n$将对象区分为 $k$相同的盒子,
贝尔数表示排列方式的数量 $n$截然不同的对象进入到 $n$相同的对象。
因此，贝尔数被计算为斯特林数的和:

$B_n = \sum_{k=1}^n S(n,k)。$

从斯特林数表中，下列贝尔数被计算为每个贝尔数的和 $n ^ \文本{th}$行:

$c \开始{数组}{}&B_0 = 1, &B_1 = 1, &B_2 = 2, &B_3 = 5, &B_4 = 15, &B_5 = 52, &B_6 = 203, &B_7 = 877, & \ ldots。\{数组}$

贝尔数有自己的递归关系:

$B_{n+1} = \sum_{k=0}^n {n \ select k} B_k$

证明

这将用组合学来证明。考虑一下 $文本(n + 1) ^ \ {th}$元素被分区。假设有 $k$这些元素不在它的盒子里 ${n \ select k}$挑选方法 $k$元素，之后还有 $b_ k$如何安排这些 $k$元素放进相同的盒子里。因此，有 ${n \ select k} B_k$这样的安排。所得到的贝尔数是所有这些排列对的所有可能值的和 $k$． $_ \广场$

有趣的是注意到指数生成函数是贝尔数的倒数

$B(x) = \sum_{n=0} ^ \infty \frac{B_n} {n !} x^n = e^{e^x -1}。$

证明这一点最简单的方法是证明前面的递归关系解释了原因 $B'(x) = e^x B(x)$，通过求解微分方程并在 $X = 0$．

假设 $N$是 $n$不同的素数。一共有多少种写法 $N$作为正整数的乘积 $(> 1)$，在这里，术语的顺序无关紧要?

---

考虑如何放置 $n$相同方框中的不同质数提供了一种写法 $N$作为正整数的乘积。首先，找到乘积的每一项的质因数分解，并将每一项的因数放入一个方框中。然后,自 $N$是不同质因数的乘积，每个质因数出现在一个唯一的方框中。因为这些项的乘积是 $N$，每个质因数必须在一个方框中。
相反，给定这些的任意排列 $n$将质数区分为 $r$相同的方框，将方框中的质数相乘得到一项，这些项的乘积得到 $N$．这就建立了双射。因此，方法的数量是 $B_n。\ _ \广场$