复赛完了再写这篇文章是不是太迟了？
闲话：我只是为了初赛练练组合数学而做的，没有多少 OI 内容（可能复赛时会考虑添加？ 复赛寄的太彻底，不加了）。
我们教练说：初赛时排列组合的题目不会做就大力递推。虽然 CSP 初赛中数学题目越来越简单了，但这并不妨碍我仍然害怕着排练组合的题目。于是他让我来做这道题，并不是码，而是把递推式列出来。这方法确实很有用——于是我就写了这篇文章。
这篇文章是为我自己而写，也是为不会组合数学的人写的。所以很多理所当然的过程都写了上去，请多包含。
另附一些符号约定：
| 符号 |
意义 |
| \displaystyle \bigcup\limits_{i=1}^n A_i |
集合 A_1, A_2, \dots, A_n 的并集，\displaystyle \bigcup\limits_{i=1}^n A_i=A_1\cup A_2\cup \dots \cup A_n |
| \displaystyle \bigcap\limits_{i=1}^n A_i |
集合 A_1, A_2, \dots, A_n 的交集，\displaystyle \bigcap\limits_{i=1}^n A_i=A_1\cap A_2\cap \dots \cap A_n |
| \dbinom{n}{k} |
即 \mathrm C^k_n |
| n^{\underline {k}} |
下降阶乘幂，n^{\underline{k}}=\dfrac{n!}{(n-k)!} =\mathrm A^k_n |
| \Z^{n}_{>0} |
\left \{ x \in \Z ~\vert~ 0 < x \leq n \right \} |
P5824 十二重计数法
有 n 个球和 m 个盒子，要全部装进盒子里。
还有一些限制条件，那么有多少种方法放球？（与放的先后顺序无关）
限制条件分别如下：
$\text{II}$：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
$\text{III}$：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。
$\text{IV}$：球之间互不相同，盒子全部相同。
$\text{V}$：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
$\text{VI}$：球之间互不相同，盒子全部相同，每个盒子至少装一个球。
$\text{VII}$：球全部相同，盒子之间互不相同。
$\text{VIII}$：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
$\text{IX}$：球全部相同，盒子之间互不相同，每个盒子至少装一个球。
$\text{X}$：球全部相同，盒子全部相同。
$\text{XI}$：球全部相同，盒子全部相同，每个盒子至多装一个球。
$\text{XII}$：球全部相同，盒子全部相同，每个盒子至少装一个球。
-----
想法
-----
# $\text{I}
每个球都有 m 种方案数。答案即为
m^n
\text{II}
依次取球放进盒子，每次放球后方案数都会少一种，乘起来答案为
m^{\underline {n}}
\text{III}
可以考虑先参考 \text{VI}。
那么考虑盒子的排列，一种很显然的答案就是
m!\begin{Bmatrix} n \\ m \end{Bmatrix}
当然了，我们也可以考虑容斥：枚举空着的盒子的个数，不限制放置个数的方案总数 减去 有 i 个盒子空着时方案的总数 即为我们求的答案。
设全集 U 是所有放球的方法构成的集合（容易注意到 |U| = m^n），A_i 为能满足 i 个盒子为空的放法构成的集合。即求 |U| - \left|\bigcup_{i=1}^{m}A_i\right|。
容斥得
\left|\bigcup_{i=1}^{m}A_i\right| &= \sum_{K \subseteq \Z^{n}_{>0}}(-1)^{|K|-1}\left|\bigcap_{k \in K} A_k\right| \\
&= \sum_{i=1}^m (-1)^{i-1}\dbinom{m}{i}(m-i)^n
\end{aligned}
前面的系数 (-1)^{i-1} 可以归纳证明。\dbinom{m}{i} 表示选 i 个作为空盒子，(m-i)^n 的情景和 \text I 相同。
所以答案就是
\begin{aligned}
|U| - \left|\bigcup_{i=1}^{m}A_i\right| &= m^n - \sum_{i=1}^m (-1)^{i-1}\dbinom{m}{i}(m-i)^n \\ &= m^n + \sum_{i=1}^m (-1)^{i}\dbinom{m}{i}(m-i)^n\\
&= \sum_{i=0}^m (-1)^{i}\dbinom{m}{i}(m-i)^n
\end{aligned}
这个时候我们可以再次回看 \text{VI}。
\text{IV}
先参考 \text{VI}。
与 \text{VI} 不同的是没有了个数的限制。枚举非空盒子个数，所以是
\sum_{i = 1}^{m} \begin{Bmatrix} n \\ i \end{Bmatrix}
\text{V}
最简单的一集！由于盒子相同且最多放一个球，无论怎么装，都可以交换盒子顺序额得到同一种方案，所以答案为：
[n \le m]
顺带去看看 \text{XI}。
\text{VI}
我会递推！
设 f_{\text {VI}}(n, m) 为 n 个球，m 个盒子的方案数。
考虑新加进来一个球：
\begin{Bmatrix} n \\ m \end{Bmatrix} = \frac{1}{m!}\sum_{i=0}^m (-1)^{i}\binom{m}{i}(m-i)^n
非常神奇呢。
\text{VII}
我会递推！
设 f_{\text {VII}}(n, m) 为 n 个球，m 个盒子的方案数。
考虑这一个球 不放而让新开的盒子空着 还是 在之前的盒子里放多个：
- 可以不放这个球而让盒子空着，小球数目仍然为 n 个。拿过来了一个新的盒子，即从 f_{\text {VII}}(n, m - 1) 转移。
- 在之前的盒子里放多个，盒子数目仍然为 m 个。即从 f_{\text {VII}}(n - 1, m) 转移。
所以递推式为：
f_{\text {VII}}(n, m) = f_{\text {VII}}(n - 1, m) + f_{\text {VII}}(n, m - 1)
也可以从插板的角度考虑：
先往每个盒子里塞一个球，最后把这个球拿走就行了。换言之，先求「将 n+m 个相同小球，放入到 m 个不同盒子，盒子至少装一球」的方案数，对于每个这个问题的划分方案，将每个盒子抽掉一个球，就是 \mathrm{VII} 的方案。因此该问答案即为
\dbinom{n+m-1}{m-1}
引用自 囧仙
\text{VIII}
我会递推！
设 f_{\text {VIII}}(n, m) 为 n 个球，m 个盒子的方案数。
考虑这一个球 再开一个盒子放一个 还是 不放而让新开的盒子空着：
- 再开一个盒子放一个，盒子数目也就从 m - 1 个变成了 m 个。那就从 f_{\text {VIII}}(n - 1, m - 1) 转移过来；
- 可以不放这个球而让盒子空着，小球数目仍然为 n 个。拿过来了一个新的盒子，即从 f_{\text {VIII}}(n, m - 1) 转移。
所以递推式为：
f_{\text {VIII}}(n, m) = f_{\text {VIII}}(n - 1, m - 1) + f_{\text {VIII}}(n, m - 1)
实际上，这就是 组合数 \dbinom{n}{m} 。
也可以直接考虑选 m 个盒子装球，那答案也是一样的。
\text{IX}
我会递推！
设 f_{\text {IX}}(n, m) 为 n 个球，m 个盒子的方案数。
考虑这一个球 再开一个盒子放一个 还是 在之前的盒子里放多个：
- 再开一个盒子放一个，盒子数目也就从 m - 1 个变成了 m 个。那就从 f_{\text {IX}}(n - 1, m - 1) 转移过来；
- 在之前的盒子里放多个，盒子数目仍然为 m 个。即从 f_{\text {IX}}(n - 1, m) 转移。
所以递推式为：
f_{\text {IX}}(n, m) = f_{\text {IX}}(n - 1, m - 1) + f_{\text {IX}}(n - 1, m)
也可以从插板的角度考虑，是最平凡的插板法。答案为
\dbinom{n - 1}{m - 1}
\text{X}
我会递推！
设 f_{\text {X}}(n, m) 为 n 个球，m 个盒子的方案数。可以发现，在所谓「第一个盒子里装一个球、第三个盒子里装三个球」是和「第一个盒子里装三个球、第三个盒子里装一个球」无异的。一种比较讨巧的做法是这样的：将盒子按照球的数量从小到大排序。这样的话，两种方案相同，仅当两种方案排序后的序列相同。所以可以：
- 在这个序列 X 开头加一个空盒子，盒子数目也就从 m - 1 个变成了 m 个。那就从 f_{\text {X}}(n, m - 1) 转移过来；
- 让所有盒子里都加一个球，也就从 f_{\text {X}}(n - m, m) 转移过来；
可以证明以上的转移方案是正确的。所以递推式为：
f_{\text{X}}(n, m) = f_{\text {X}}(n, m - 1) + f_{\text {X}}(n - m, m)
这个东西其实就是 划分数。
\text{XI}
最简单的一集！
[n \le m]
\text{XII}
与 \text{X} 的唯一差别是每个盒子里都至少要一个球——那就先往盒子里都放一个球就好了。答案就是
f_{\text {X}}(n - m, m)