01 小球装箱问题与组合证明

小球装箱问题

小球装箱问题：有$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\end{array}\right)\right)$。等价于从$n$个元素里选$k$次，每次选的可以是重复的，选完的结果是不考虑顺序的。

第六种：球不同，箱子相同，每个箱子至少一个球。

箱子相同，所以装箱等价于分组。把$k$个不同元素分成$n$组的方案数，我们把这个数记为$\left\{\begin{array}{l} k \\ n \end{array}\right\}$，称为第二类斯特林数(the second type of Stirling number)。我们将在下一节证明求解第二类斯特林数的递推公式，在“容斥原理”一文中证明第二类斯特林数的通项公式。

第七种：球不同，箱子不同，每个箱子至少一个球。

在第二类斯特林数$\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)$。

第十一种：球不同，箱子相同，每个箱子至多一个球。

如果球的个数比箱子少，那么每个球自成一组，只有这一种方案。如果球的个数比箱子多，那么一定不可能有解。答案是$\mathbb{1}[k \leq n]$。

第十二种：球相同，箱子相同，每个箱子至多一个球。

同上，答案是$\mathbb{1}[k \leq n]$。

用组合意义证明恒等式

在组合数学中有一种称为double counting的证明恒等式的方法：如果数同一个东西有两种不同的数法，那么两种数法的表达式对应的结果必然相等。

恒等式1

杨辉三角：

$$\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}$$

证明：等式左边表示从$n$个不同的元素里选$k$个。也可以这么讨论：讨论第$n$个元素有没有被选。如果被选了，那么对应的方案数等价于从前$n-1$个里选剩下的$k-1$个；如果没有被选，那么对应的方案数等价于从$n-1$个里面选$k$个。所以等式两边只是同一个问题的两种不同看法而已。

恒等式2

$$\left(\left(\begin{array}{l}n \\k\end{array}\right)\right)=\left(\left(\begin{array}{c}n \\ k-1\end{array}\right)\right)+\left(\left(\begin{array}{c}n-1 \\ k\end{array}\right)\right)$$

等式左边表示从$n$个不同的元素里可重复地选$k$个，选的结果是忽略顺序的。也可以这么讨论：讨论第$n$个元素有没有被选。如果被选了，那么它可以继承所有从$n$个里选$k-1$次的结果；如果没有被选，那么只能继承所有从$n-1$个元素里面选$k$次的方案了。

恒等式3

范德蒙德卷积(Vandermonde convolution)：

$$\sum_{j=0}^{k}\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{c} n \\ k-j \end{array}\right)=\left(\begin{array}{c} m+n \\ k \end{array}\right)$$

这个式子说明，从$m+n$个元素里选$k$个，可以分类讨论从前$m$个里选$j$个，从后$n$个里选$k-j$个。

恒等式4

$$\left\{\begin{array}{l} n \\ k \end{array}\right\}=\left\{\begin{array}{c} n-1 \\ k-1 \end{array}\right\}+k \cdot\left\{\begin{array}{c} n-1 \\ k \end{array}\right\}$$

把$n$个元素分成$k$组。如果第$n$个元素自成一组，那么继承$n-1$个元素分$k-1$组的方案；如果第$n$个元素没有自成一组，那么它所在的组至少有两个元素。那么前$n-1$个元素必须已经分成了$k$组，第$n$个元素必须加入其中一组。注意这样是不会重复的，因为加入这个元素后发生重复说明加入前就已经重复了，与“不同的方案数”矛盾。

用这个递推式可以$O(nk)$求出斯特林数。

恒等式5

$$\left\{\begin{array}{l} n \\ k \end{array}\right\}=\sum_{j=0}^{n-1}\left(\begin{array}{c} n-1 \\ j \end{array}\right) \cdot\left\{\begin{array}{c} n-j-1 \\ k-1 \end{array}\right\}$$

把$n$个元素分成$k$组，考虑最后一个元素和哪些元素在同一个组。假如同组的还有$j$个其它元素，那么这$j$个元素的选择就是组合数。剩下的元素分$k-1$组。

恒等式6

$$P(n, k)=P(n-1, k-1)+P(n-k, k)$$

把$n$拆成$k$个元素的和，考虑拆出来的数字里有没有1。如果有1，那么剩下的$n-1$拆成$k-1$个数字；如果没有1，说明拆除来的每个数都大于1，那么可以给每个数都削掉一个1，变成$n-k$拆成$k$个数字，之后可以随便拆分。

用这个递推式可以$O(nk)$求出划分数。

恒等式7

$$P(n,k)=\sum\limits_{j=0}^{k}P(n-k,j)$$

把$n$拆成$k$个元素的和，考虑拆出来的数字里有多少个1。如果有$k-j$个1，那么剩下的$j$个数都大于1。除去所有的1，后面总共有$n-k+j$个数，全都削掉1，转化成$n-k$拆成$j$个数。

恒等式8

$$\sum\limits_{j=0}^{n}(-1)^j\dbinom{n}{j}\dbinom{2n+k-2j}{n}=2^n$$

从$(0,0)$出发，每次只能向右或向上走，先走到$(n,n)$，再一路往右走到$(n+k,n)$。在从$(0,0)$走到$(n,n)$的过程中，总共走$2n$步。规定$\forall i \in [n]$，第$2i-1$步和第$2i$步不能都向右走。

两步为一组看这个问题，每组只有右上和上右两种情况，最后的$k$步一定全部向右，因此总的方案数就是$2^n$。

用容斥原理来计算（见下一篇文章）。假设对于$i \in [n]$，如果第$2i-1$步和第$2i$步都向右走了，就称这次走路在坏集合$A_i$内。设$J=\{A_{i_1},\cdots,A_{i_t}\}$，那么$N_\geq(J)$应当这样计算，总共走$2n+k$步，现在已经确定了有$2t$步，剩下的$2n+k-2t$步里必须有$n$步是向上走的，因此$N_\geq(J)=\dbinom{2n+k-2t}{n}$。根据容斥，总方案数应当是$N_=(\varnothing)=\sum\limits_{j=0}^{n}(-1)^j\sum\limits_{J \in \binom{\mathscr{A}}{j}}N_\geq(J)=\sum\limits_{j=0}^{n}(-1)^j\dbinom{n}{j}\dbinom{2n+k-2j}{n}$。

参考资料

[1] Chihao Zhang, Combinatorics in Computer Science (Spring 2023)