小球入盒问题是所有组合问题的基础，它计算的是形如 “$n$ 个球放进 $m$ 个盒子的方案数” 的一类问题，在这类问题中一般存在三种限制 ：
- 小球是否有编号。
- 盒子是否有编号。
- 盒子中球的数量是无限制，至少一个还是至多一个。
记有编号为 $L\rm (labelled)$，无编号为 $U\rm (unlabelled)$，盒子中球的数量限制分别为 $A,B,C$，这样我们就可以将一个问题用三个字母简记，如 $\rm LUB$ 表示将 $n$ 个有标号小球放进 $m$ 个无标号盒子里，每个盒子中至少有一个球的方案数。
可以发现问题共有 $12$ 类，现在我们来一个个分析。
Part1 LLA
将 $n$ 个有标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量没有限制的方案数。
可以看作每次从 $m$ 个盒子里任选一个，一共要放 $n$ 次，没有其他限制，故方案数为 ：
$$\boxed{m^n}
$$
Part2 ULA
将 $n$ 个无标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量没有限制的方案数。
在这个问题中我们只关心对每个盒子里面球的数量，所以这个问题的方案数等于方程 $x_1+x_2+\cdots +x_m=n$ 非负整数解的数量，用隔板法可以求得其为 ：
$$\boxed{\dbinom{n+m-1}{m-1}}
$$
Part3 ULB
将 $n$ 个无标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至少为 $1$ 的方案数。
这个问题与上个问题相似，方案数等于方程 $x_1+x_2+\cdots +x_m=n$ 正整数解的数量，用隔板法可以求得其为 ：
$$\boxed{\dbinom{n-1}{m-1}}
$$
Part4 LLC
将 $n$ 个有标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。
我们发现这个问题等价于依次为每个球选择一个盒子，故答案为 ：
$$\boxed{m^{\underline{n}}}
$$
Part5 ULC
将 $n$ 个无标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。
相当于是为每一个盒子选择数量，等价于从 $m$ 个盒子中选出 $n$ 个，让它的数量为 $1$，故方案数为 ：
$$\boxed{\dbinom{m}{n}}
$$
Part6 LUC
将 $n$ 个有标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。
盒子顺序可以任意交换，所以任意一种方案都等价，发现当球数超过盒子数时无解，故方案数为 ：
$$\boxed{[n\leqslant m]}
$$
Part7 UUC
将 $n$ 个无标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量至多为 $1$ 的方案数。
理由同上，方案数为 ：
$$\boxed{[n\leqslant m]}
$$
Part8 LLB
将 $n$ 个有标号的球放进 $m$ 个有标号的盒子里，每个盒子中球的数量至少为 $1$ 的方案数。
考虑使用容斥原理，枚举有多少个盒子为空，剩下的盒子随便填，故方案数为 ：
$$\boxed{\sum_{i=0}^m(-1)^i\dbinom{m}{i}(m-i)^n}
$$
利用 $\rm Part9$ 中讲到的第二类斯特林数也可以 $\rm LLB$ 问题的方案数表示为 ：
$$\boxed{\begin{Bmatrix}n\\m\end{Bmatrix}m!}
$$
Part9 LUB
将 $n$ 个有标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量至少为 $1$ 的方案数。
只需要将 $m$ 个盒子排序产生的方案去除即可，故方案数为 :
$$\boxed{\sum_{i=0}^m\frac{(-1)^i(m-i)^n}{i!(m-i)!}}
$$
$\rm LUB$ 问题的答案被定义为 “第二类斯特林数”，递推式如下 ：
$$\boxed{\begin{Bmatrix}n\\m\end{Bmatrix}=m\begin{Bmatrix}n-1\\m\end{Bmatrix}+\begin{Bmatrix}n-1\\m-1\end{Bmatrix}}
$$
其含义为考虑新加入一个有标号小球，可以将其加入之前的任意一个盒子，也可以为它单独开一个盒子，方案数相加。
Part10 LUA
将 $n$ 个有标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量无限制的方案数。
记 $\rm LUA$ 问题的方案数为 $B_n$，读作贝尔数。因为若某个盒子为空可以看作没有这个盒子，故 $B_n$ 表示将 $n$ 个数划分成任意个集合的方案数，有 ：
$$\boxed{B_n=\sum_{i=1}^n\begin{Bmatrix}n\\i\end{Bmatrix}}
$$
同时，我们发现它也可以递推，有递推式 ：
$$\boxed{B_{n+1}=\sum_{i=0}^n\dbinom{n}{i}B_i}
$$
其含义为第 $n+1$ 个数若和之前的 $i$ 个数放在一起，方案数为 $\tbinom{n}{i}B_{n-i}$。
Part11 UUA
将 $n$ 个无标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量无限制的方案数。
我们发现其实这就是划分数，求法如下 ：
记 $f_{i,j}$ 表示将 $i$ 划分成不超过 $j$ 的数的方案数，当计算 $f_{i,j}$ 时，其方案数可以从 $f_{i-j,j}$ 继承，表示分出去一个大小为 $j$ 的数，其方案数也可以从 $f_{i,j-1}$ 继承，表示不选大小为 $j$ 的数。故有转移方程 ：
$$f_{i,j}=f_{i-j,j}+f_{i,j-1}
$$
我们发现 $f$ 的转移就是一个完全背包，所以考虑将其改写为一维形式，即 ：
$$f_j=\sum_{i=1}^nf_{j-i}
$$
记 $g_{i,j}$ 表示将 $i$ 划分成 $j$ 个数的方案，当计算 $g_{i,j}$ 时，其方案数可以从 $g_{i-j,j}$ 继承，表示将所有数 $+1$，其方案数也可以从 $g_{i-1,j-1}$ 继承，表示新增一个大小为 $1$ 的数。我们发现后增加的数一定比前增加的数小，所以不重，这样一定能遍历到所有合法的划分，所以不漏，故有转移方程 ：
$$g_{i,j}=g_{i-j,j}+g_{i-1,j-1}
$$
这两种方式都可以做到 $\Theta(n^2)$。
我们分析两种方式的优劣，发现第一种算法主要依赖于划分成的数大小的上界，第二种算法主要依赖于划分成数的数量，于是考虑根号分治。将问题看成一个完全背包，物品按照占用空间小于等于 $\sqrt{n}$ 和大于 $\sqrt{n}$ 分类即可。
同时，由于 $g$ 计算的只有物品占用空间大于 $\sqrt{n}$ 的情况，所以转移方程要改写成 :
$$g_{i,j}=g_{i-j,j}+g_{i-\sqrt{n},j-1}
$$
每次加入一个 $\sqrt{n}$ 就可以保证所有数都大于 $\sqrt{n}$ 了。
最后统计答案的时候直接枚举 $i$，然后将 $f_i$ 和 $g_{n-i,k}$ 乘起来即可。
时间复杂度 $\Theta(n\sqrt{n})$。
Part12 UUB
将 $n$ 个无标号的球放进 $m$ 个无标号的盒子里，每个盒子中球的数量 至少为 $1$ 的方案数。
我们发现只需要先在每个盒子中放 $1$ 个球就可以了，等价于 $\rm UUA$ 问题中 $n-m$ 个球，$m$ 个盒子的情况。