基本计数法

小球装箱问题

小球装箱问题：有\(k\)个球，装进\(n\)个箱子里，问有几种方案？分别讨论球是否相同，箱子是否相同，每个箱子至少一个、至多一个、没有限制，共12种不同情况。

第一种：球不同，箱子不同，没有限制。我们对球讨论，每个球都独立地有\(n\)种选择。只要有一个球的选择不一样，结果就不一样。因此共有\(n^k\)种方案。

第二种：球不同，箱子不同，每个箱子至多一个球。这首先要求箱子要比球多。那么先选出哪些箱子里有球，有\(\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}\)种选法。球可以全排列，有\(k!\)种排法。因此共有\(\dfrac{n!}{(n-k)!}\)。这正好是\(n\)的\(k\)阶下降阶乘幂，记作\((n)_k\)。

第三种：球相同，箱子不同，每个箱子至多一个球。箱子比球多。只需要选出\(k\)个有球的箱子就好了，答案是\(\dbinom{n}{k}\)。

第四种：球相同，箱子不同，每个箱子至少一个球。插入\(n-1\)块隔板，隔板的位置有\(k-1\)个可选，答案是\(\dbinom{k-1}{n-1}\)。

第五种：球相同，箱子不同，没有限制。要插\(n-1\)块隔板，但箱子可以为空。我们选择在\(k+n-1\)个元素中挑出\(n-1\)个变成隔板，所以答案是\(\dbinom{k+n-1}{n-1}\)。这是从箱子的角度来考虑的。如果从球的角度考虑，那么每个球选择了一个箱子，但球是没有区别的，所以所有\(k\)个球的选择构成的是一个元素可以重复集合（与顺序无关），称为“可重集”。所以我们知道了，总共\(k\)个元素且每个元素的范围在\(1\)到\(n\)的可重集个数为\(\dbinom{k+n-1}{n-1}\)，记为\(\left(\left(\begin{array}{c}n \\k-n\end{array}\right)\right)\)。

第六种：球不同，箱子相同，每个箱子至少一个球。箱子相同，所以装箱等价于分组。把\(k\)个不同元素分成\(n\)组的方案数，我们把这个数记为\(\left\{\begin{array}{l} k \\ n \end{array}\right\}\)，称为第二类斯特林数。

第七种：球不同，箱子不同，每个箱子至少一个球。在第二类斯特林数\(\left\{\begin{array}{l} k \\ n \end{array}\right\}\)的基础上，现在箱子不同了，原来的每种分组方案都可以对应箱子的全排列。所以答案是\(\left\{\begin{array}{l} k \\ n \end{array}\right\} \cdot n!\)。

第八种：球不同，箱子相同，没有限制。没有限制说明分的组数可以大到\(n\)组，小到\(1\)组。答案是\(\sum\limits_{i=1}^{n}\left\{\begin{array}{l} k \\ i \end{array}\right\}\)。

第九组：球相同，箱子相同，每个箱子至少一个球。相当于要把一个数字\(k\)分解成\(n\)个数字的和。这个答案称为划分数，记为\(P(k,n)\)。

第十组：球相同，箱子相同，没有限制。划分的个数可以从\(1\)到\(n\)，答案为\(\sum\limits_{i=1}^{n}P(k,i)\)。

第十一组：球不同，箱子相同，每个箱子至多一个球。如果球的个数比箱子少，那么每个球自成一组，只有这一种方案。如果球的个数比箱子多，那么一定不可能有解。答案是\(1[k \leq n]\)。

第十一组：球相同，箱子相同，每个箱子至多一个球。同上，答案是\(1[k \leq n]\)。