在实现生活中， 如何将物体分配到盒子里面是一个非常普通且常见的一个问题。
要解决这个问题需要考虑几种清空。
首先我们把这个问题分成四个类别的的问题。
-
将不同的物体分配到不同的盒子中
-
将相同的物体分配到不同的盒子中
-
将不同的物体分配到相同的盒子中
-
将相同的物体分配到相同的盒子中
将不同的物体分配到不同的盒子中
-
举例：如果将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!1i=0∑k(ik)(−1)i(k−i)n
总结
至此， 我们可以最终得到我们原问题的答案
∑ r = 1 k P ( n , r ) \sum_{r=1}^{k}P(n,r) r=1∑kP(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∑kW(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∑rW(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个盒子。
:::
