这两天复习组合数学,仔细品了品八种放球问题,感觉还是挺有意思的。
放球问题的基本表述是:将$n$个球放入$m$个盒子中(每个球都必须放到某个盒子里),有多少种方案?
由于有$3$个方面的条件,所以总共有$2^3=8$种,按熟悉程度分别介绍吧。

1. 将$n$个无区别的球放入$m$个有区别的盒子中,不允许空盒

使用经典的插空法,把$m-1$个板插入$n-1$个空中,自然划分出$m$个区,对应$m$个有区别的盒子,如图所示。
插空法示意图
方案数$=C_{n-1}^{m-1}$。
该问题等价于求$\sum_{i=1}^{m}{x_{i}}=n$的正整数解的个数。

2. 将$n$个无区别的球放入$m$个有区别的盒子中,允许有空盒

使用经典的隔板法,把$m-1$个板与$n$个球放在一起。“允许有空盒”意味着板和板可以紧邻地放在一起,这时候就要换一种思维方式,也就是从位置的角度来考虑,在$n+m-1$个位置中选$m-1$个放隔板,剩下的$n$个放球。
隔板法示意图
方案数$=C_{n+m-1}^{m-1}$。
该问题等价于求$\sum_{i=1}^{m}{x_{i}}=n$的非负整数解的个数,通过换元法可以转化为问题1。

3. 将$n$个有区别的球放入$m$个有区别的盒子中,允许有空盒

第1个球有$m$种选择,第2个球也有$m$种选择,第3个……。
方案数$=m \times m \times \cdots \times m = m^{n}$。

4. 将$n$个有区别的球放入$m$个无区别的盒子中,不允许空盒

这是第二类斯特林数的定义。
方案数$=S(n,m)$,递推式为$S(n,m)= S(n-1,m-1) + S(n-1,m) \times m$,包含了两种情况,

  1. 第$n$个球单独放一个盒子,也就是之前的$n-1$个球放入了$m-1$个盒子;
  2. 第$n$个球放入已经存在的盒子,由于不能有空盒,此时$m$个盒子内部的情况肯定是不一样的,所以可以直接乘以$m$。

5. 将$n$个有区别的球放入$m$个无区别的盒子中,允许有空盒

由于盒子是无区别的,可以直接枚举空盒的数量而不考虑具体是哪些盒子。
方案数$=S(n,m)+S(n,m-1)+\cdots + S(n,1)=\sum_{i=1}^{m}{S(n,i)}$。

6. 将$n$个有区别的球放入$m$个有区别的盒子中,不允许空盒

考虑问题4中的任意一种方案,将$m$个盒子分别标号$1$到$m$,将任意两个盒子中的球做整体的对换,就产生了本问题的一种新方案。不断地进行两两对换,不重复的方案显然组成了全排列。
方案数$=S(n,m) \times m!$。

7. 将$n$个无区别的球放入$m$个无区别的盒子中,允许有空盒

等价于整数拆分问题,即,将整数$n$无序拆分为不超过$m$个正整数的方案数。由Ferrers图像的对称性,该方案数等于将整数$n$无序拆分为最大数不超过$m$的方案数。
显然有母函数
$$G(x)=(1+x+x^{2}+ \cdots )(1+x^{2}+x^{4}+ \cdots ) \cdots (1+x^{m}+x^{2m}+ \cdots )=\frac{1}{(1-x)(1-x^{2}) \cdots (1-x^{m})}$$
方案数为,$G(x)$中$x^{n}$的系数。

8. 将$n$个无区别的球放入$m$个无区别的盒子中,不允许空盒

等价于整数拆分问题,即,将整数$n$无序拆分为$m$个正整数的方案数。由Ferrers图像的对称性,该方案数等于将整数$n$无序拆分为最大数等于$m$的方案数。
显然有母函数
$$G(x)=(1+x+x^{2}+ \cdots )(1+x^{2}+x^{4}+ \cdots ) \cdots (x^{m}+x^{2m}+ \cdots )=\frac{x^{m}}{(1-x)(1-x^{2}) \cdots (1-x^{m})}$$
方案数为,$G(x)$中$x^{n}$的系数。

ps. 其实问题678的想法感觉不是很自然,不知道有没有其他更好的推理方法。