小球入盒问题是所有组合问题的基础，它计算的是形如 “\(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\) 个盒子的情况。
