箱球模型学习笔记

· · 算法·理论

我是蒟蒻，可能有错，还请指出。

箱球模型有很多种，基本都是按照小球是否不同，箱子是否不同和是否允许空箱分类的。

我们设箱子数为 k，球数为 n。

\color{green}{1.\text{球不同，箱不同，允许空箱}}

很简单。对于每一个球，我们可以把它放进 k 个箱子中的任意一个，易得答案为 k^n。

\color{green}{2.\text{球同，箱不同，不允许空箱}}

也是很简单。注意到球是相同的，所以我们可以把球排成一列，名字都叫没有差别小球球，都是一家人，顺序不重要，只要是一列就好。然后我们可以把 k 个箱子转化为 k-1 个隔板，隔板只可以插到在两个小球之间的地方（边缘就不能插），也不可以和其他的隔板抢位置，这样就不会隔出空的箱子。同时隔板是有顺序的，不然就会有一堆重复计数。所以是 C，不是 A。答案：C_{n-1}^{k+1}。

\color{green}{3.\text{球同，箱不同，允许空箱}}

和2很像，但是箱子能空箱。空箱实在是太难办了，于是我们考虑惩罚箱子。我们可以硬送给箱子一个小球，但是那样我们就会WA，所以让我们把题目改成：有 n+k 个小球， k 个箱子，球同，箱不同，不允许空箱。如果箱子想在原来的题目里空箱的话只需要在新题里只留一个我们送箱子的小球就行，不会WA了，AC快乐。答案： C_{n+k-1}^{k-1}

新手期已过

箱子相同都是难的（哭）

\color{orange}{4.\text{球不同，箱同，不允许空箱}}

该引入第二类斯特林数(Stirling Number，OI界也有人简称为SN(?))了。

先上答案：

n\\k \end{Bmatrix}=S2(n,k)

再详细点，就是：

\frac{1}{k!}\sum_{i=0}^{k}(-1)^iC_k^i(k-i)^n

对于我这种蒟蒻&小奥人这个公式简直是太吓人了，这和小学奥数的组合数学完全不一样啊

不过幸好的是第二类斯特林数的递推公式很简单。

n\\k \end{Bmatrix}= \begin{Bmatrix} n-1\\k-1 \end{Bmatrix}+k\begin{Bmatrix} n-1\\k \end{Bmatrix}

这个东西以我的水平还是可以解释解释的。在 k 个一样的箱子里面放 n 个不同的小球的方案可以拆成两种：

1.让一个箱子在 n-1 个球的时候仍然保持空箱，并且把第 n 个球放在这个空箱里。所以对于我们这种情况，我们只要求出 n-1 个球， k-1 个箱子的方案数，即

n-1\\k-1 \end{Bmatrix}

即可。

2.我们把小球随便放入一个箱子，因为没有对箱子做出新的任何限制，我们只要算出

n-1\\k \end{Bmatrix}

即可。注意因为随便选一个箱子都行，所以要多乘一个 k。

\color{orange}{5.\text{球不同，箱不同，不允许空箱}}

我们发现它与4的区别仅在箱子不同了。我们只要在4的基础上乘上一个 k! 就行了。或者把第二类斯特林数的通项公式里那个用来去重的 \frac{1}{k!} 删掉就行了。答案：

n\\k \end{Bmatrix}=\sum_{i=0}^{k}(-1)^iC_k^i(k-i)^n

\color{orange}{6.\text{球不同，箱同，允许空箱}}

我们发现它与4的区别仅在允许空箱。于是我们考虑枚举有多少个箱子是非空的。最后用一个sigma求和就行。答案：

n\\i \end{Bmatrix}

\color{red}{7\&8.\text{球同，箱同，允许（第七问）/不允许（第八问）空箱}}

这不是拆数问题吗

我们只需要求出递推公式，对于答案的具体求值，我们可以使用DP（动态规划）。不过由于这个DP太简单了，说是递推也可以:P

先给第七题答案：

1 & n=0\vee k=1 \\ 0 & k=0\wedge n\ne 0 \\ B1(n,n) & n<k \\ B1(n-k,k)+B1(n,k-1) & \text{otherwise} \end{cases}

第一项的意思是说“如果一个小球都没有的话，那就只有一种方法：不放；如果只有一个箱子的话也只有一个方法：把所有小球都放进去”，第二项的意思是说“如果一个箱子都没有，还要放球进去的话，那肯定是不可能的”，第三项的意思就是“如果球比箱子还少，那就把一定没用的箱子丢了，反正箱子都一样”，而第四项的意思就是“我们可以把盒子放满，如果不想放满也是可以的”。

接下来是第八题的答案：

1 & n=0\wedge k=0\\ 0 & (k=0\oplus n=0) \vee n<k\\ B1(n-k,k) & \text{otherwise} \end{cases}

第一项的意思就是说“如果没有箱子也没有小球，那唯一一种方法就是啥也不干”，第二项的意思是说“如果没箱子或者没小球而且还不是箱子小球一起没有的话。那压根不可能。如果小球比箱子还少，那就一定有空箱，也是不符合要求的。”，第三项说的是“我们可以考虑先给每个箱子配一个小球，接下来问题就变成了第七问的问题。”