关于论文网站开发参考文献,关于做摄影的网站,国际网站建设标准,linux做网站1G内存够不放球问题简介
放球问题是一类很有意思的排列组合问题。通俗来说#xff0c;就是把n个小球放到m个盒子里#xff0c;问有几种放法。根据小球是否相同#xff0c;盒子是否相同#xff0c;是否允许有空盒#xff0c;又可以把问题细分为8个具体的问题。其中有一些问题是非常简…放球问题简介
放球问题是一类很有意思的排列组合问题。通俗来说就是把n个小球放到m个盒子里问有几种放法。根据小球是否相同盒子是否相同是否允许有空盒又可以把问题细分为8个具体的问题。其中有一些问题是非常简单的有一些问题经常出现在一些经典的排列组合问题当中有一些问题则比较有难度难以通过一个表达式直接写出答案。
放球问题的解法
我们分8种情况具体讨论这个问题。假设有n个小球m个盒子且默认n ≥ \geq ≥m。我们就从易到难慢慢来分析。
1.球不同盒不同允许有空盒
这是最简单的一种情况。对于每个小球有m种放法一共有n个小球于是一共有 m n m^n mn种放法。
2.球相同盒不同不允许有空盒
由于球相同我们可以把每个球看成一个0n个球组成了一个长度为n的全0序列。放小球的过程可以看成把这个序列分为m段且每段长度大于0。于是我们就可以用隔板法解决了。问题相当于在这个长度为n的序列中插入m-1个隔板从而就把序列分成了m段。这个序列有n-1个间隙为了保证每段长度大于0则只需要两块隔板不放在同一个间隙中。于是问题就变成了在n-1个间隙中挑选m-1个位置放隔板即 C n − 1 m − 1 C_{n-1}^{m-1} Cn−1m−1种放法。
3.球相同盒不同允许有空盒
这个有两种做法。第一种做法是这样的。跟上面那种情况类似也是看成一个序列但是两个隔板是可以相邻的。n个球m-1个隔板一共长度为nm-1。我们只需要在这个nm-1个位置中选m-1个位置作为隔板即可于是有 C n m − 1 m − 1 C_{nm-1}^{m-1} Cnm−1m−1种放法。 第二种做法是可以认为我们一开始有nm个小球先在每个盒中放上一个小球。于是问题就转化为了nm个球放在m个盒子里不允许有空盒的情况。套用上面的公式得有 C n m − 1 m − 1 C_{nm-1}^{m-1} Cnm−1m−1种放法。
4.球不同盒不相同不允许有空盒
到这里问题开始变得难起来了。正难则反我们反过来考虑必定存在空盒的情况。这里我们采用容斥原理的方法做。由于盒子不同给每个盒子从1-m编个号。令 A i A_i Ai表示第i个盒子是空的情况|A|表示在A情况下的方案数。比如 ∣ A i ∣ |A_i| ∣Ai∣表示第i个盒子一定是空盒的方案数那么 ∣ A i ∣ ( m − 1 ) n |A_i|(m-1)^n ∣Ai∣(m−1)n。 ∣ A i ∩ A j ∣ |A_i \cap A_j| ∣Ai∩Aj∣表示第i个盒子和第j个盒子同时是空盒的情况数即 ( m − 2 ) n (m-2)^n (m−2)n种。我们要求有空盒的方案数即 ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A m ∣ |A_1\cup A_2\cup \cdots \cup A_m| ∣A1∪A2∪⋯∪Am∣。 根据容斥原理的公式 ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A m ∣ ∑ 1 ≤ i ≤ m ∣ A i ∣ − ∑ 1 ≤ i j ≤ m ∣ A i ∩ A j ∣ ∑ 1 ≤ i j k ≤ m ∣ A i ∩ A j ∩ A k ∣ − ⋯ ( − 1 ) m − 1 ∣ A 1 ∩ A 2 ∩ ⋯ ∩ A m ∣ C m 1 ( m − 1 ) n − C m 2 ( m − 2 ) n C m 3 ( m − 3 ) n − ⋯ ( − 1 ) m − 1 C m m ( m − m ) n ∑ k 1 m ( − 1 ) k − 1 C m k ( m − k ) n |A_1\cup A_2\cup \cdots \cup A_m|\sum_{1\leq i \leq m}{|A_i|}-\sum_{1\leq ij \leq m}{|A_i \cap A_j|}\sum_{1 \leq ijk \leq m}{|A_i \cap A_j \cap A_k|}-\cdots(-1)^{m-1}|A_1 \cap A_2 \cap \cdots \cap A_m|C_m^1(m-1)^n-C_m^2(m-2)^nC_m^3(m-3)^n-\cdots (-1)^{m-1}C_m^m(m-m)^n\sum_{k1}^m{(-1)^{k-1}C_m^k(m-k)^n} ∣A1∪A2∪⋯∪Am∣∑1≤i≤m∣Ai∣−∑1≤ij≤m∣Ai∩Aj∣∑1≤ijk≤m∣Ai∩Aj∩Ak∣−⋯(−1)m−1∣A1∩A2∩⋯∩Am∣Cm1(m−1)n−Cm2(m−2)nCm3(m−3)n−⋯(−1)m−1Cmm(m−m)n∑k1m(−1)k−1Cmk(m−k)n 必定存在空盒的方案数有 ∑ k 1 m ( − 1 ) k − 1 C m k ( m − k ) n \sum_{k1}^m{(-1)^{k-1}C_m^k(m-k)^n} ∑k1m(−1)k−1Cmk(m−k)n种那么不存在空盒的方案数有 m n − ∑ k 1 m ( − 1 ) k − 1 C m k ( m − k ) n ∑ k 0 m ( − 1 ) k C m k ( m − k ) n m^n-\sum_{k1}^m{(-1)^{k-1}C_m^k(m-k)^n}\sum_{k0}^m{(-1)^kC_m^k(m-k)^n} mn−∑k1m(−1)k−1Cmk(m−k)n∑k0m(−1)kCmk(m−k)n 总的来说求解的思路是通过容斥原理把较难的不允许有空盒的情况转化为较为容易的允许有空盒的情况。
5.球不同盒相同不允许有空盒
这个问题跟上一个问题相比仅仅是盒不同改成了盒相同那么由于球不同所以这个问题的放法是上面问题放法的 1 m ! \frac{1}{m!} m!1即 1 m ! ∑ k 0 m ( − 1 ) k C m k ( m − k ) n \frac{1}{m!}\sum_{k0}^m{(-1)^kC_m^k(m-k)^n} m!1∑k0m(−1)kCmk(m−k)n 由于该问题求解起来较为复杂所以人们为这个问题专门定义了一个术语——第二类斯特林数。第二类斯特林数 S ( n , m ) S(n,m) S(n,m)表示将n个不同的小球放在m个相同的盒子中不允许有空盒的方案数。 那么根据我们的推导 S ( n , m ) 1 m ! ∑ k 0 m ( − 1 ) k C m k ( m − k ) n S(n,m)\frac{1}{m!}\sum_{k0}^m{(-1)^kC_m^k(m-k)^n} S(n,m)m!1∑k0m(−1)kCmk(m−k)n。 同时这也是 S ( n , m ) S(n,m) S(n,m)的通项公式。
6.球不同盒相同允许有空盒
相比于上面的问题这个问题允许有空盒了。那么我们只需要枚举非空盒的个数就能转化为上面的问题了。有i个非空盒时方案数为 S ( n , i ) S(n,i) S(n,i)。于是总方案数为 ∑ i 1 m S ( n , i ) \sum_{i1}^m{S(n,i)} ∑i1mS(n,i)
7.球相同盒相同允许有空盒
这个问题可以用母函数的方法做但是由于本人才疏学浅没有学过母函数的方法于是在这里提供一种递推的解法。 设方案数为 f ( n , m ) f(n,m) f(n,m)。 先给出边界情况当小球数为0或盒子数为1肯定就只有1种方案了。 再分类讨论给出递推关系式。 若小球数比盒子数少则多出来的盒子只能空着于是有 f ( n , m ) f ( n , n ) n m f(n,m)f(n,n)nm f(n,m)f(n,n)nm 若小球数不比盒子数少那么我们就要放小球了。整体思路是把盒子排成一排后面的盒子放的小球数不能超过前面盒子的小球数。这样枚举的话才能不重不漏。我们考虑当前的最后一个盒子有放小球和不放小球两种情况。如果空着方案数为 f ( n , m − 1 ) f(n,m-1) f(n,m−1)。如果要放小球由于这个盒子的小球必须是最少的所以前面所有盒子都要放一个小球这样的方案数为 f ( n − m , m ) f(n-m,m) f(n−m,m)。 合起来可以得到 f ( n , m ) f(n,m) f(n,m)的递推表达式 f ( n , m ) { 1 n 0 ∣ ∣ m 1 f ( n , n ) n m f ( n − m , m ) f ( n , m − 1 ) n ≥ m f(n,m)\begin{cases} 1 n0 || m1 \\ f(n,n) nm \\ f(n-m,m)f(n,m-1) n\geq m \end{cases} f(n,m)⎩ ⎨ ⎧1f(n,n)f(n−m,m)f(n,m−1)n0∣∣m1nmn≥m
8.球相同盒相同不允许有空盒
既然球跟盒都相同那不妨拿出m个球先在每个盒子里放上一个球。这样问题就转化为将n-m个相同的小球放到m个盒子里允许有空盒的问题了。方案数即为 f ( n − m , m ) f(n-m,m) f(n−m,m)
代码
下面是我写的python代码
import math
def f(n,m):if n0 or m1:return 1if nm:return f(n,n)return f(n-m,m)f(n,m-1)
def S(n,m):return sum((-1)**k * math.comb(m, k) * math.pow(m-k, n) for k in range(m1))/math.factorial(m)
def fangqiu(n,m,qiu,he,kong): #n表示球数m表示盒数qiu表示小球是否相同he表示盒子是否相同kong表示是否允许有空盒if qiu0 and he0 and kong1:return m**nif qiu1 and he0 and kong0:return math.comb(n-1,m-1)if qiu1 and he0 and kong1:return math.comb(nm-1,m-1)if qiu0 and he0 and kong0:return S(n, m)*math.factorial(m)if qiu0 and he1 and kong0:return S(n, m)if qiu0 and he1 and kong1:return sum(S(n,i) for i in range(1,m1))if qiu1 and he1 and kong1:return f(n,m)if qiu1 and he1 and kong0:return f(n-m,m)
n,mmap(int,input().split())
print(int(fangqiu(n,m,0,0,1)))总结
虽然我们按一定的标准划分出了8个问题但其实这8个问题又有很多变种。比如我们只关注了 n ≥ m n\geq m n≥m的情况我们得出的结论一部分对 n ≤ m n\leq m n≤m适用一部分却不适用了。掌握解决这一类问题的方法比记住结论更加重要。
