n 个球放入 m 个箱子问题

n个球放入m个箱子$(m\geq1,n\geq1)$，问有多少种放法。

可以根据球是否相同、箱子是否相同、是否允许空箱分成如下几类（对于不允许空箱的情况，应满足$m\leq n$）：

1. 球相同，箱子相同，允许空箱

设$dp[i][j]$表示将i个球放入j个箱子在允许空箱的情况下的全部放法。则

1. $i \ge j$的情况下，可以分为没有空箱和有空箱两种情况，前者是$dp[i-j][j]$，后者是$dp[i][j-1]$。
2. $i>j$的情况下，新来的箱子没用，所以是$dp[i][j-1]$。

$$dp[i][j]= \begin{cases} dp[i-j][j]+dp[i][j-1]&i\geq j\\ dp[i][j-1]&i<j \end{cases}\\ initial\;conditions:\\ dp[k][1]=dp[1][l]=dp[0][l]=1,k\in[0,n],l\in[1,m]$$

$dp[i-j][j]$表示j个箱子不存在空箱的情况下的放法，$dp[i][j-1]$表示箱子存在空箱情况下的放法。

2. 球相同，箱子相同，不允许空箱

可以考虑这样一种放法：先从n个球中选取m个分别放入m个箱子中，再将余下个n-m球放入这m个箱子中。这种放法相当于1的条件下只有n-m个球的情况，因此答案即为$dp[n-m][m]$。

3. 球相同，箱子不同，不允许空箱

应用“插板法”。n个球之间有n-1个空隙，从中选取m-1个位置插入隔板。答案为

$$C_{n-1}^{m-1}$$

4. 球相同，箱子不同，允许空箱

可以考虑这样一种放法：先在m个箱子中每个放入一个球，再将n个球放入这m个箱子中，最后再将每个箱子中的球减少一个即可。这种放法相当于将m+n个球在不允许空箱的情况下放入了m个箱子中，因此答案即为

$$C_{m+n-1}^{m-1}$$

5. 球不同，箱子不同，允许空箱

每个球选择箱子，一个球有m种选择，n个球有$m^n$种选择

6. 球不同，箱子相同，不允许空箱

此即第二类斯特林数，$S_2(n,m)$。

$S_2(n,m)$有如下两种推导方法：

（a）动态规划

考虑计算$S_2(i,j)$。

$i=j或j=1$时，$S_2(i,j)=1$是显然的。

$i>j$时，$S_2(i,j)$可以分为两种情况，一种情况是第i个球单独一组，剩下i-1球分到j-1个箱子，一共$S_2(i-1,j-1)$种情况；另一种情况是i-1个球已经分到了j个箱子中，此时第i个球选择任意一个箱子放入都行，一共$jS_2(i-1,j)$种情况。

所以$S_2(i,j)=S_2(i-1,j-1)+jS_2(i-1,j)$。

（b）数学

第二类斯特林数的展开式_百度百科 (baidu.com)

7. 球不同，箱子相同，允许空箱

分为m种情况讨论：分别将n个球放入1、2、3…m个箱子且不允许空箱，将这m中情况对应的放法相加即可。

$$\Sigma_{k=1}^m S_2(n,k)$$

8. 球不同，箱子不同，不允许空箱

只需要在箱子相同的答案基础上乘以$m!$即可，即$S_2(n,m)\times m!$