Balls and Boxes

经典组合数学

小球与盒子

前置知识

组合数 ：

$$C_n^m = \frac{n!}{m!(n-m)!}$$

插板法 ：用于解决不相邻组合与追加排列的问题，就是在$n$个物品之间插上$m$个板，将其分为$m+1$组。

捆绑法：将一些物品作为整体计算。

容斥原理：将重复计算的数目去除，比如：

$$A\cup B = A+B- A\cap B$$

1. 球相同，盒子不同，不能有空盒

其实这个问题的实质就是把$n$个小球分为$m$组（不能空），就转化为了一个组合数问题，答案其实就是

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

其实就是插板法，在小球的$n-1$个空隙中插入$m-1$个板子，使其分为$m$组。

2. 球相同，盒子不同，可以有空盒

其实和上个问题差不多，我们一开始可以就向每个盒子中添加一个小球，这样就不会有空盒，答案为

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

3. 球不同，盒子不同，可以有空盒

对于每一个球，都可以放在$m$个位置中的任意一个位置，由于球与球之间是相互独立的，答案就是

$$m^n$$

4.球不同，盒子相同，不能有空盒

这个其实就是第二类斯特林数，将$n$个物体划分为$k$个非空的没有区别的集合的方案数，其递推公式为：

$$f_{i,j} = f_{i-1,j}\times j + f_{i-1,j-1}$$

其实通俗的理解就是对于第$i$个球，可以放在以前的$j$个盒子中有$j \times f_{i-1,j}$种方案,或者放入一个新的盒子有$f_{i-1,j-1}$种方案。

不过这是一个$n^2$的公式，但是其它还有一个更通用的公式：

$$f(n,m) = \frac{1}{m!} \times \sum_{k = 0}^m (-1)^k \dbinom{m}{k} \times (m-k)^n$$

5. 球不同，盒子也不同，不能有空盒

其实这个和上一种情况不同的就是，这个情况需要有序性，答案其实就是对应的斯特林数，

$$f(n,m) \times m!$$

就可以了。

6. 球不同， 盒子相同，可以有空盒

因为可以有空盒，其实就可以枚举每次用了几个盒子，然后将对应的斯特林数相加即可,答案就是

$$\sum_{i =1}^m f(n,i)$$

其实这种数还有另一种名称叫贝尔数，它表示集合${1,2,3,\cdots,n}$的划分方案数，其实就表示了第二类斯特林数之和。

7.球相同，盒子相同，可以有空盒

首先分情况，如果一个盒子没有小球，方案数显然为1，同时如果小球比盒子要少，盒子肯定时是放不满的，所以$f_{i,j} = f_{i,i}$，如果小球比盒子要多，就将盒子分为放满和没放满两种情况，所以$f_{i,j} = f_{i-j,j} + f_{i,j-1}$。

8. 球相同，盒子相同，不能有空盒

只需要假设每个盒子里都已经放上了一个球，答案就是，

$$f(n-m,m)$$