这两天复习组合数学，仔细品了品八种放球问题，感觉还是挺有意思的。
放球问题的基本表述是：将$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$，包含了两种情况，
- 第$n$个球单独放一个盒子，也就是之前的$n-1$个球放入了$m-1$个盒子；
- 第$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的想法感觉不是很自然，不知道有没有其他更好的推理方法。
