十二重计数法
有 \(n\) 个球，\(m\) 个盒子，将每个球装进盒子，并满足下面的条件，有多少种方案？
1. 球不同，盒不同
相当于每个球选择一个盒子放
答案为 \(m^n\)
2. 球不同，盒不同，每个盒子至多装一个
分两种情况讨论
- \(n \le m\) ，对于每个球，找一个没有放过球的盒子放，答案为 \(m^{\underline{n}}\)
- \(n > m\) ，这种情况无解，答案为 \(0\)
3. 球不同，盒不同，每个盒子至少放一个
还是分两种情况
-
\(n < m\) 无解
-
\(n \ge m\)
至少放一个的条件不太好做，所以我们可以用 1 的答案减去不合法的方案数，这里用容斥即可
\[\sum_{i = 0}^m (-1)^i \binom m i (m - i)^n \]
4. 球不同，盒同
考虑第二类斯特林数：\(S_{n,m}\) 表示 \(n\) 个不同的元素组成 \(m\) 个非空集合的方案数，枚举有多少个盒子装了球，答案为
\[\sum_{i = 1}^m S_{n, i}
\]
5. 球不同，盒同，每个盒子至多放一个
答案为：\([n \le m]\)
6. 球不同，盒同，每个盒子至少放一个
- \(n < m\) 无解
- \(n \ge m\) 这个和第 3 个的区别在于盒子相同，于是可以用第 3 个的答案除去 \(m!\) 即可
\[\frac {\sum_{i = 0}^m (-1)^i \binom m i (m - i)^n} {m!}
\]
关于第 4 个问题为什么不能用第一个问题的答案除去 \(m!\) 得到
第 6 个问题可以由第 3 个问题转化过来的主要原因是：6 & 3 中的盒子都有球，并且因为 6 中的盒子装了不同的球，所以 6 中的装球盒子也都是本质不同的。回过头来看 4 ，因为盒子可以为空，所以空盒子本质相同，因此无法通过 1 转化
后面这三个就是我们平时见得比较多的插板法了
7. 球相同，盒不同
\[\binom {n + m - 1} {m - 1}
\]
8. 球相同，盒不同，每个盒子至多放一个
- \(n > m\) 无解
- \(n \le m\) ， \(\binom m n\)
9. 球相同，盒不同，每个盒子至少放一个
- \(n < m\) 无解
- \(n \ge m\) ，\(\binom {n - 1} {m - 1}\)
10. 球相同，盒相同
设 \(p_{n,m}\) 表示“划分数”——即将 \(n\) 划分成 \(m\) 个自然数的可重集的方案数，那么我们的答案就是 \(p_{n,m}\)
经典 \(O(n^2)\) 的 \(dp\) ：
\[p_{i,j} = p_{i - j,j} + p_{i, j - 1}
\]
11. 球相同，盒相同，每个盒子至多放一个
这个就和前面的那个是一样的 \([n \le m]\) ，因为盒子相同的话，放哪个盒子都是一样的，不论球是否相同
12. 球相同，盒相同，每个盒子至少放一个
-
\(n < m\) 无解
-
\(n \ge m\)
考虑将上面划分数中的自然数变成正整数，先强制每个盒子放一个球，答案即为 \(p_{n - m,m}\)