组合数学中将物体放入盒子中的四种情况

组合数学中将物体放入盒子中的四种情况"/>

组合数学中将物体放入盒子中的四种情况

在实现生活中， 如何将物体分配到盒子里面是一个非常普通且常见的一个问题。
要解决这个问题需要考虑几种清空。
首先我们把这个问题分成四个类别的的问题。

1. 将不同的物体分配到不同的盒子中

2. 将相同的物体分配到不同的盒子中

3. 将不同的物体分配到相同的盒子中

4. 将相同的物体分配到相同的盒子中

将不同的物体分配到不同的盒子中

• 举例：如果将52张扑克开（一套扑克牌）分配给4个玩家， 每人5张牌。
  有多少种分配方法？

• 解答：这个问题就是典型的将不同的物体分配到不同的盒子中的问题。
  要解决这个问题其实很简单， 只需要采用乘法原理即可。采用五个步骤，
  第一步分配给第一个玩家， 第二步分配给第二个玩家， 并以此类推。

  ( 52 5 ) ( 47 5 ) ( 42 5 ) ( 37 5 ) = 52 ! 5 ! 5 ! 5 ! 5 ! 32 ! \binom{52}{5}\binom{47}{5}\binom{42}{5}\binom{37}{5}=\frac{52!}{5!5!5!5!32!} (552​)(547​)(542​)(537​)=5!5!5!5!32!52!​

• 总结：将n个不同的物体分配给k个不同盒子，
  并且每一个盒子分配得到的数量是 n i , i = 1 , 2 , ⋯ , k n_i, i=1,2,\cdots, k ni​,i=1,2,⋯,k.
  分配方案的个数是 n ! n 1 ! n 2 ! ⋯ n k ! \frac{n!}{n_1!n_2! \cdots n_k!} n1​!n2​!⋯nk​!n!​

将相同的物体分配到不同的盒子中

• 举例：对于算式 a + b + c + d = 10 , a , b , c , d ∈ N a+b+c+d = 10, a,b,c,d\in \mathbb{N} a+b+c+d=10,a,b,c,d∈N. 请问 a , b , c , d a,b,c,d a,b,c,d
  有多少种不同的取值？

• 解答: 这个问题相当于用隔板去把10个1， 分割来开。
  隔板的数量是3就可以了。 注意这里不能用插入， 插入会造成重复。
  而是选择隔板的位置。 从10+3个位置中选择3个位置的隔板。

  ( 13 3 ) = ( 10 + 4 − 1 4 − 1 ) \binom{13}{3}=\binom{10+4-1}{4-1} (313​)=(4−110+4−1​)

• 总结：将n个相同的物体分配到r个不同的盒子中，总的分配方案是

  ( n + r − 1 r − 1 ) \binom{n+r-1}{r-1} (r−1n+r−1​)

将不同的物体分配到相同的盒子中

虽然看起来这个问题比较简单， 但是这个问题比前面两个问题都要复杂得多。
这个问题没有一个统一的公式。 因为包含很多种情况。 比如只放在一个盒子里，
只放在两个盒子里面， 等等。这其中， 每个盒子不为空的情况有统一公式，
这个公式在机器学习中的应用就是聚类。 把n个不同的物体聚成4类，
这四个类别其实就是4个相同的盒子。但是这个问题有一个要求及时每个盒子不能为空，
否则不能聚为一个类别。这个问题的答案其实就是第二类的Stirling数。

n个不同的对象分到k个相同的盒子里面, 要求每个盒子至少有一个对象.
有多少种分法. 这是在k均值聚类里面的一个组合数学问题.
在k均值聚类里面有n个对象各不相同,
要把这个n个对象分到k个类别里面并要求每个类别必须至少含有一个对象.
总共的分法有多少中? 这道题的答案是第二类的stirling number.
我们来看看如何来求解.我们把原问题定义为 P ( n , k ) P(n,k) P(n,k)

初探

如果将n个不同的对象放到k个不同的盒子里面总共有多少种方法?
这个问题不再限制每个盒子必须含有一个对象. 我们定义这个事件为 S S S,答案是
∣ S ∣ = k n |S|=k^n ∣S∣=kn

接下来,
我们再来定义特殊的几个事件.我们先假设盒子各不相同并且有 k k k个盒子.
设 A i A_i Ai​表示第 i , ( 1 ⩽ i ⩽ k ) i, (1\leqslant i\leqslant k) i,(1⩽i⩽k)个盒子是空的事件.
那么,我们定义下面一个事件

S n , k = A ‾ 1 ∩ A ‾ 2 ∩ ⋯ ∩ A ‾ k S_{n,k}=\overline{A}_1\cap \overline{A}_2 \cap \cdots \cap \overline{A}_k Sn,k​=A1​∩A2​∩⋯∩Ak​

事件 S n , k S_{n,k} Sn,k​表示, k k k个盒子都非空.

∣ S n , k ∣ = ∣ S ∣ − ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A k ∣ |S_{n,k}|=|S|-|A_1\cup A_2\cup \cdots \cup A_k| ∣Sn,k​∣=∣S∣−∣A1​∪A2​∪⋯∪Ak​∣

如果我们能够计算出 ∣ S n , k ∣ |S_{n,k}| ∣Sn,k​∣那么 P ( n , k ) = 1 k ! ∣ S n , k ∣ P(n,k)=\frac{1}{k!}|S_{n,k}| P(n,k)=k!1​∣Sn,k​∣

容斥原理

现在我们剩下的唯一目的就是计算 ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A k ∣ |A_1\cup A_2\cup \cdots \cup A_k| ∣A1​∪A2​∪⋯∪Ak​∣.
而这个集合可以使用容斥原理来计算

∣ A 1 ∪ A 2 ∪ ⋯ ∪ A k ∣ = ∑ i = 1 k ∣ A i ∣ − ∑ i ≠ j k ∣ A i ∩ A j ∣ + ∑ i ≠ j ≠ h k ∣ A i ∩ A j ∩ A h ∣ + ⋯ + ( − 1 ) k ∣ A 1 ∩ A 2 ∩ ⋯ ∩ A k ∣ |A_1\cup A_2\cup \cdots \cup A_k| = \sum_{i=1}^{k}|A_i|-\sum_{i\neq j}^k|A_i\cap A_j|+\sum_{i\neq j \neq h}^{k}|A_i\cap A_j\cap A_h|+\cdots+ (-1)^k|A_1\cap A_2\cap \cdots \cap A_k| ∣A1​∪A2​∪⋯∪Ak​∣=i=1∑k​∣Ai​∣−i​=j∑k​∣Ai​∩Aj​∣+i​=j​=h∑k​∣Ai​∩Aj​∩Ah​∣+⋯+(−1)k∣A1​∩A2​∩⋯∩Ak​∣

∣ A 1 ∪ A 2 ∪ ⋯ ∪ A k ∣ = ( k 1 ) ( k − 1 ) n − ( k 2 ) ( k − 2 ) n + ( k 3 ) ( k − 3 ) n + ⋯ + ( − 1 ) k − 1 ( k k ) ( k − k ) n |A_1\cup A_2\cup \cdots \cup A_k|=\binom{k}{1}(k-1)^n-\binom{k}{2}(k-2)^n+\binom{k}{3}(k-3)^n+\cdots + (-1)^{k-1}\binom{k}{k}(k-k)^n ∣A1​∪A2​∪⋯∪Ak​∣=(1k​)(k−1)n−(2k​)(k−2)n+(3k​)(k−3)n+⋯+(−1)k−1(kk​)(k−k)n

最后可得

∣ S n , k ∣ = ∣ S ∣ − ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A k ∣ = ( k 0 ) ( k − 0 ) n − ( k 1 ) ( k − 1 ) n + ( k 2 ) ( k − 2 ) n + ( k 3 ) ( k − 3 ) n + ⋯ + ( − 1 ) k ( k k ) ( k − k ) n = ∑ i = 0 k ( k i ) ( − 1 ) i ( k − i ) n \left. \begin{aligned} |S_{n,k}|&=|S|-|A_1\cup A_2\cup \cdots \cup A_k|\\ &=\binom{k}{0}(k-0)^n-\binom{k}{1}(k-1)^n+\binom{k}{2}(k-2)^n+\binom{k}{3}(k-3)^n+\cdots + (-1)^{k}\binom{k}{k}(k-k)^n\\ &=\sum_{i=0}^{k}\binom{k}{i}(-1)^i(k-i)^n \end{aligned} \right. ∣Sn,k​∣​=∣S∣−∣A1​∪A2​∪⋯∪Ak​∣=(0k​)(k−0)n−(1k​)(k−1)n+(2k​)(k−2)n+(3k​)(k−3)n+⋯+(−1)k(kk​)(k−k)n=i=0∑k​(ik​)(−1)i(k−i)n​

最后得到第二类stirling number为

P ( n , k ) = 1 k ! ∣ S n , k ∣ = 1 k ! ∑ i = 0 k ( k i ) ( − 1 ) i ( k − i ) n P(n,k)=\frac{1}{k!}|S_{n,k}|=\frac{1}{k!}\sum_{i=0}^{k}\binom{k}{i}(-1)^i(k-i)^n P(n,k)=k!1​∣Sn,k​∣=k!1​i=0∑k​(ik​)(−1)i(k−i)n

总结

至此， 我们可以最终得到我们原问题的答案

∑ r = 1 k P ( n , r ) \sum_{r=1}^{k}P(n,r) r=1∑k​P(n,r)

即分成好几种情况进行处理， 每一种是一个Stirling Number。

将相同的物体分配到相同的盒子中

这个问题其实也没有一个简单的统一公式，我们把这个问题的解设为 H ( n , k ) H(n,k) H(n,k),
即把n个相同的物体分配给k个相同的盒子. 这个问题也是要分情况考虑的，
比如所有的对象放到一个，两个， 三个， 等等，
并且每一个盒子非空。我们用 W ( n , k ) W(n, k) W(n,k)来表示将n个相同的物体放倒k相同的盒子中，
并且每个盒子非空。那么原问题就等于

H ( n , k ) = ∑ r = 1 k W ( n , r ) H(n,k)=\sum_{r=1}^{k}W(n,r) H(n,k)=r=1∑k​W(n,r)

那么， 这个问题转为话求 W ( n , r ) W(n,r) W(n,r).

W ( n , r ) = ∑ j = 1 r W ( n − r , j ) = H ( n − r , r ) W(n,r)=\sum_{j=1}^{r}W(n-r,j)=H(n-r, r) W(n,r)=j=1∑r​W(n−r,j)=H(n−r,r)

这是因为，
每一个盒子分走一个之后剩下的就只有 n − r n-r n−r个物体。然后剩下这 n − r n-r n−r个物体再考虑以下情况，
非空的放入 1 1 1个盒子， 2 2 2个盒子， ⋯ \cdots ⋯, r r r个盒子。
:::