球盒问题

将小球放在盒子中的问题，一共有八种情况。
我们假定一共有$n$个球，$m$个盒子。

一、球可区分，盒可区分，盒子可以为空

这个是最简单的情况，每个球有$m$种不同的选择方式，所以方案数是：
$$m^n$$

二、球可区分，盒可区分，盒子不可以为空

我们可以用生成函数来解决这个问题。
这个问题等价于，我们有$m$种不同的气球，每种气球有无限个，然后选择n个气球出来排列，每个气球至少选一个。
所以指数生成函数是：
$$G(z)=(\sum_{i=1}^{\infty}\frac{z^i}{i!})^m=(e^z-1)^m$$
二项式展开后：
$$G(z)=\sum_{i=0}^m\binom{m}{i}e^{z(m-i)}(-1)^{i}$$
那么$\frac{x^n}{n!}$的系数就是：
$$\sum_{i=0}^m\binom{m}{i}(m-i)^n(-1)^i$$

三、球可区分，盒不可区分，盒子不可以为空

这个问题就是问题二中，将盒子的情况给除掉就好，即：
$$\frac{1}{m!}\sum_{i=0}^m\binom{m}{i}(m-i)^n(-1)^i$$
上式又称第二类斯特林数，记为$S(n,m)$，或者$\begin{Bmatrix}n\\ m\end{Bmatrix}$
为了寻找一个递推的形式，我们尝试用动态规划的思想来解决
首先我们将$n-1$个球放好，有两种情况：
第一种就是$n-1$个球占了$m-1$个盒子，这时候第$n$个球只用占最后一个盒子就好。
第二种就是$n-1$个球占了$m$个盒子，这时候第$n$个球就随便放哪了。
所以得到递推关系式：
$$S(n,m)=S(n-1,m-1)+mS(n-1,m)$$
有了斯特林数，问题二也可以解决了。

四、球可区分，盒不可区分，盒子可以为空

这时候我们只需要枚举总共用了几个盒子就好，所以答案是：
$$\sum_{i=1}^mS(n,i)$$

五、球不可区分，盒可区分，盒子可以为空

这时候我们依然可以用生成函数的方法解决：
$$G(z)=(\sum_{i=0}^{\infty}(z^i))^m=\frac{1}{(1-z)^m}$$
使用广义二项式定理，我们有：
$$G(z)=(1-z)^{-m}=\sum_{i=0}^{\infty}\binom{-m}{i}z^i(-1)^i$$
$$G(z)=\sum_{i=0}^{\infty}\frac{\prod_{j=0}^{i-1}(m+j)}{i!}z^i$$
其中$z^n$的系数便是：
$$\binom{m+n-1}{n}$$

六、球不可区分，盒可区分，盒子不可以为空

这个问题相当于我们先在每个盒子中放一个球，之后便是问题五。
所以总的方案数是将$n-m$个球放到$m$个盒子中，盒子可以为空，盒子可区分，球不可区分：
$$\binom{n-1}{n-m}$$

七、球不可区分，盒不可区分，盒子不可以为空

我们用$dp[i][j]$表示将$i$个不可区分的球放到$j$个不可区分的盒子中，盒子不可以为空的方案数。
考虑将$i$个盒子排序，我们考虑最少的那个盒子。

如果这个盒子中的球只有一个，那么就是子问题$dp[i-1][j-1]$
如果这个盒子中的球大于一个，说明所有盒子都比这个盒子的球多，从每个盒子中拿掉一个球，那么子问题就是$dp[i-j][j]$

所以总的转移就是：
$$dp[i][j]=dp[i-1][j-1]+dp[i-j][j]$$
$$dp[i][1]=1,dp[i][i]=1$$
$$dp[i][j]=0,i<j$$

八、球不可区分，盒不可区分，盒子可以为空

我们从别的地方借$m$个球放在问题七的$m$个盒子中，每个盒子放一个，那么就和问题七一样了。
答案既是问题七中的$dp[n+m][m]$