准备
组合数
$$
\binom{n}{m} = C(n,m) =
\left\lbrace \begin{aligned}
&\frac{n!}{m!~(n-m)!}, &n \geqslant m \
&0, &n < m
\end{aligned} \right.
$$
第二类斯特林数
\begin{aligned}
S(n,m) &=mS(n-1,m)+S(n-1,m-1) \
&=\frac{1}{m!} \sum_{k=0}^m (-1)^k\binom{m}{k} (m-k)^n \
&\
&\text{其中， $n > 1, m \geqslant 1$。}
\end{aligned}
小球放盒模型
有 $n$ 个小球放入 $m$ 个盒子中，求方案数。
000 小球无区别 盒子无区别 不允许空盒
初始时，先给每一个盒子放一个小球。问题转化成 $n-m$ 个 无区别小球 放入 $m$ 个 无区别盒子 且 允许有空盒。
方案数：$G(x)=\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}$ 的 $x^n$ 项系数。
001 小球无区别 盒子无区别 允许有空盒
设某一方案中，有 $i$ 个小球的盒子有 $ a_i $ 个。
显然，$\displaystyle \left(\sum_{i=0}^n a_i\right) =m, ~ 0 \leqslant a_i \leqslant m $。
对于每一个方案，我们仅用 $a_i \neq 0$ 的项组成的形如 $\big\lbrace (r,a_r),(p,a_p),\cdots,(q,a_q) \big\rbrace$ 的序偶序列表示足矣。
问题等价于用 $\lbrace 1,2,\cdots,m \rbrace$ 拆分 $n$ 的拆分数。
利用母函数，容易得到：
$$
\begin{aligned}
G(x)&=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(1+x^m+x^{2m}+\cdots) \
&=\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}
\end{aligned}
$$
方案数：$G(x)=\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}$ 的 $x^n$ 项系数。
010 小球无区别 盒子有区别 不允许空盒
相当于在 $n$ 个小球中放置 $m-1$ 块挡板将小球分成不为空的 $m$ 部分。
这个问题等价于在 $n-1$ 个位置中选择 $m-1$ 个位置。
方案数：$C(n-1,m-1)$。
011 小球无区别 盒子有区别 允许有空盒
由于允许空盒，根据前面的分析，挡板可以相邻。
所以问题等价于，在 $n+m-1$ 个位置中放置 $m-1$ 块挡板。
方案数：$C(n+m-1,m-1)$。
100 小球有区别 盒子无区别 不允许空盒
设方案数 $f(n,m)$。
讨论任一小球 $ball(1)$ 的摆放情况，所有的方案分为两类：
- $ball(1)$ 独占一个盒子；相当于其它 $n-1$ 个不同球需要放入 $m-1$ 个相同盒子且不允许空盒；
方案数：$f(n-1,m-1)$。 - $ball(1)$ 不独占一个盒子; 相当于先把 $n-1$ 个不同球放入 $m$ 个相同盒子且不允许空盒，再将 $ball(1)$ 放入任一盒子中；
得到递推式：$\quad f(n,m) = m \times f(n-1,m)+f(n-1,m-1). $
比较第二类斯特林数，不难发现：$\quad f(n,m)=S(n,m) $。
101 小球有区别 盒子无区别 允许有空盒
仅需在 不允许空盒 的基础上枚举空盒个数就好了。
方案数：$\displaystyle \sum_{i=1}^{\min(n,m)} S(n,i)$
110 小球有区别 盒子有区别 不允许空盒
因为无空盒，且每个小球必然只能放到一个盒子中，故方案数等于 盒子无区别 时的方案数乘上 $m!$。
方案数：$m! \times S(n,m)$。
111 小球有区别 盒子有区别 允许有空盒
显然每个球有 $m$ 个选择，且互不影响。
方案数：$m^n$。
小结
| $n$ 个球 | $m$ 个盒子 | 是否允许空盒 | 方案数 |
|---|---|---|---|
| 无区别 | 无区别 | 无空盒 | $G(x)=\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^n)}$ 的 $x^n$ 项的系数 |
| 无区别 | 无区别 | 有空盒 | $G(x)=\frac{1}{(1-x)(1-x^2)\cdots(1-x^n)}$ 的 $x^n$ 项的系数 |
| 无区别 | 有区别 | 无空盒 | $C(n-1,m-1)$ |
| 无区别 | 有区别 | 有空盒 | $C(n+m-1,n)$ |
| 有区别 | 无区别 | 无空盒 | $S(n,m)$ |
| 有区别 | 无区别 | 有空盒 | \begin{align} &S(n,1)+S(n,2)+\cdots+S(n,m), &n\geqslant m \\ &S(n,1)+S(n,2)+\cdots+S(n,n), &n\leqslant m \end{align} |
| 有区别 | 有区别 | 无空盒 | $m!~S(n,m)$ |
| 有区别 | 有区别 | 有空盒 | $m^n$ |
Hint
Markdown 下 \\\ 才是换行。
参考资料：《组合数学》（第 4 版》 —by 卢开澄、卢华明
