组合数学中将物体放入盒子中的四种情况"/>
组合数学中将物体放入盒子中的四种情况
在实现生活中, 如何将物体分配到盒子里面是一个非常普通且常见的一个问题。
要解决这个问题需要考虑几种清空。
首先我们把这个问题分成四个类别的的问题。
-
将不同的物体分配到不同的盒子中
-
将相同的物体分配到不同的盒子中
-
将不同的物体分配到相同的盒子中
-
将相同的物体分配到相同的盒子中
将不同的物体分配到不同的盒子中
-
举例:如果将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个盒子。
:::
更多推荐
组合数学中将物体放入盒子中的四种情况
发布评论