8类放球问题

放球问题简介

放球问题是一类很有意思的排列组合问题。通俗来说，就是把n个小球放到m个盒子里，问有几种放法。根据小球是否相同，盒子是否相同，是否允许有空盒，又可以把问题细分为8个具体的问题。其中有一些问题是非常简单的，有一些问题经常出现在一些经典的排列组合问题当中，有一些问题则比较有难度，难以通过一个表达式直接写出答案。

放球问题的解法

我们分8种情况具体讨论这个问题。假设有n个小球，m个盒子，且默认n$\ge$m。我们就从易到难，慢慢来分析。

1.球不同，盒不同，允许有空盒

这是最简单的一种情况。对于每个小球，有m种放法，一共有n个小球，于是一共有$m^n$种放法。

2.球相同，盒不同，不允许有空盒

由于球相同，我们可以把每个球看成一个0，n个球组成了一个长度为n的全0序列。放小球的过程可以看成把这个序列分为m段，且每段长度大于0。于是我们就可以用隔板法解决了。问题相当于在这个长度为n的序列中插入m-1个隔板，从而就把序列分成了m段。这个序列有n-1个间隙，为了保证每段长度大于0，则只需要两块隔板不放在同一个间隙中。于是问题就变成了，在n-1个间隙中，挑选m-1个位置放隔板，即$C_{n-1}^{m-1}$种放法。

3.球相同，盒不同，允许有空盒

这个有两种做法。第一种做法是这样的。跟上面那种情况类似，也是看成一个序列，但是两个隔板是可以相邻的。n个球，m-1个隔板，一共长度为n+m-1。我们只需要在这个n+m-1个位置中选m-1个位置作为隔板即可，于是有$C_{n+m-1}^{m-1}$种放法。
第二种做法是，可以认为我们一开始有n+m个小球，先在每个盒中放上一个小球。于是问题就转化为了n+m个球放在m个盒子里，不允许有空盒的情况。套用上面的公式，得有$C_{n+m-1}^{m-1}$种放法。

4.球不同，盒不相同，不允许有空盒

到这里，问题开始变得难起来了。正难则反，我们反过来，考虑必定存在空盒的情况。这里我们采用容斥原理的方法做。由于盒子不同，给每个盒子从1-m编个号。令$A_i$表示第i个盒子是空的情况，|A|表示在A情况下的方案数。比如$|A_i|$表示第i个盒子一定是空盒的方案数，那么$|A_i|=(m-1{)}^n$。
$|A_i\cap A_j|$表示第i个盒子和第j个盒子同时是空盒的情况数，即$(m-2{)}^n$种。我们要求有空盒的方案数，即$|A_1\cup A_2\cup \cdots \cup A_m|$。
根据容斥原理的公式，
$|A_1\cup A_2\cup \cdots \cup A_m|={\sum }_{1\le i\le m}|A_i|-{\sum }_{1\le i<j\le m}|A_i\cap A_j|+{\sum }_{1\le i<j<k\le 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{)}^n+C_m^3(m-3{)}^n-\cdots +(-1{)}^{m-1}{C}_m^m(m-m{)}^n={\sum }_{k=1}^m(-1{)}^{k-1}{C}_m^k(m-k{)}^n$
必定存在空盒的方案数有${\sum }_{k=1}^m(-1{)}^{k-1}{C}_m^k(m-k{)}^n$种，那么不存在空盒的方案数有$m^n-{\sum }_{k=1}^m(-1{)}^{k-1}{C}_m^k(m-k{)}^n={\sum }_{k=0}^m(-1{)}^k{C}_m^k(m-k{)}^n$
总的来说，求解的思路是通过容斥原理，把较难的不允许有空盒的情况转化为较为容易的允许有空盒的情况。

5.球不同，盒相同，不允许有空盒

这个问题跟上一个问题相比，仅仅是盒不同改成了盒相同，那么由于球不同，所以这个问题的放法是上面问题放法的$\frac{1}{m!}$，即$\frac{1}{m!}{\sum }_{k=0}^m(-1{)}^k{C}_m^k(m-k{)}^n$
由于该问题求解起来较为复杂，所以人们为这个问题专门定义了一个术语——第二类斯特林数。第二类斯特林数$S(n,m)$表示将n个不同的小球放在m个相同的盒子中，不允许有空盒的方案数。
那么，根据我们的推导，$S(n,m)=\frac{1}{m!}{\sum }_{k=0}^m(-1{)}^k{C}_m^k(m-k{)}^n$。
同时，这也是$S(n,m)$的通项公式。

6.球不同，盒相同，允许有空盒

相比于上面的问题，这个问题允许有空盒了。那么我们只需要枚举非空盒的个数，就能转化为上面的问题了。有i个非空盒时，方案数为$S(n,i)$。于是总方案数为${\sum }_{i=1}^{m}S(n,i)$

7.球相同，盒相同，允许有空盒

这个问题可以用母函数的方法做，但是由于本人才疏学浅，没有学过母函数的方法，于是在这里提供一种递推的解法。
设方案数为$f(n,m)$。
先给出边界情况，当小球数为0或盒子数为1，肯定就只有1种方案了。
再分类讨论，给出递推关系式。
若小球数比盒子数少，则多出来的盒子只能空着，于是有$f(n,m)=f(n,n)，n<m$
若小球数不比盒子数少，那么我们就要放小球了。整体思路是，把盒子排成一排，后面的盒子放的小球数不能超过前面盒子的小球数。这样枚举的话，才能不重不漏。我们考虑当前的最后一个盒子，有放小球和不放小球两种情况。如果空着，方案数为$f(n,m-1)$。如果要放小球，由于这个盒子的小球必须是最少的，所以前面所有盒子都要放一个小球，这样的方案数为$f(n-m,m)$。
合起来，可以得到$f(n,m)$的递推表达式
$$f(n,m)=\{\begin{array}{ll}1& n=0||m=1\\ f(n,n)& n<m\\ f(n-m,m)+f(n,m-1)& n\ge m\end{array}$$

8.球相同，盒相同，不允许有空盒

既然球跟盒都相同，那不妨拿出m个球，先在每个盒子里放上一个球。这样问题就转化为，将n-m个相同的小球放到m个盒子里，允许有空盒的问题了。方案数即为$f(n-m,m)$

代码

下面是我写的python代码

import math
def f(n,m):if n==0 or m==1:return 1if n<m: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(m+1))/math.factorial(m)
def fangqiu(n,m,qiu,he,kong): #n表示球数，m表示盒数，qiu表示小球是否相同，he表示盒子是否相同，kong表示是否允许有空盒if qiu==0 and he==0 and kong==1:return m**nif qiu==1 and he==0 and kong==0:return math.comb(n-1,m-1)if qiu==1 and he==0 and kong==1:return math.comb(n+m-1,m-1)if qiu==0 and he==0 and kong==0:return S(n, m)*math.factorial(m)if qiu==0 and he==1 and kong==0:return S(n, m)if qiu==0 and he==1 and kong==1:return sum(S(n,i) for i in range(1,m+1))if qiu==1 and he==1 and kong==1:return f(n,m)if qiu==1 and he==1 and kong==0:return f(n-m,m)
n,m=map(int,input().split())
print(int(fangqiu(n,m,0,0,1)))

总结

虽然我们按一定的标准，划分出了8个问题，但其实这8个问题又有很多变种。比如，我们只关注了$n\ge m$的情况，我们得出的结论一部分对$n\le m$适用，一部分却不适用了。掌握解决这一类问题的方法比记住结论更加重要。