十二重计数法

本文距离上次更新已过去 0 天，部分内容可能已经过时，请注意甄别。

---

复赛完了再写这篇文章是不是太迟了？

闲话：我只是为了初赛练练组合数学而做的，没有多少 OI 内容（可能复赛时会考虑添加？ 复赛寄的太彻底，不加了）。

我们教练说：初赛时排列组合的题目不会做就大力递推。虽然 CSP 初赛中数学题目越来越简单了，但这并不妨碍我仍然害怕着排练组合的题目。于是他让我来做这道题，并不是码，而是把递推式列出来。这方法确实很有用——于是我就写了这篇文章。

这篇文章是为我自己而写，也是为不会组合数学的人写的。所以很多理所当然的过程都写了上去，请多包含。

另附一些符号约定：

符号	意义
	集合 的并集，
	集合 的交集，
	即
	下降阶乘幂，

---

P5824 十二重计数法

有 个球和 个盒子，要全部装进盒子里。
还有一些限制条件，那么有多少种方法放球？（与放的先后顺序无关）

限制条件分别如下：

：球之间互不相同，盒子之间互不相同。
：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。

：球之间互不相同，盒子全部相同。
：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
：球之间互不相同，盒子全部相同，每个盒子至少装一个球。

：球全部相同，盒子之间互不相同。
：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
：球全部相同，盒子之间互不相同，每个盒子至少装一个球。

：球全部相同，盒子全部相同。
：球全部相同，盒子全部相同，每个盒子至多装一个球。
：球全部相同，盒子全部相同，每个盒子至少装一个球。

---

想法

---

每个球都有 种方案数。答案即为

依次取球放进盒子，每次放球后方案数都会少一种，乘起来答案为

可以考虑先参考 。
那么考虑盒子的排列，一种很显然的答案就是

当然了，我们也可以考虑容斥：枚举空着的盒子的个数，不限制放置个数的方案总数 减去 有 个盒子空着时方案的总数 即为我们求的答案。
设全集 是所有放球的方法构成的集合（容易注意到 ）， 为能满足 个盒子为空的放法构成的集合。即求 。
容斥得

前面的系数 可以归纳证明。 表示选 个作为空盒子， 的情景和 相同。

所以答案就是

这个时候我们可以再次回看 。

先参考 。
与 不同的是没有了个数的限制。枚举非空盒子个数，所以是

最简单的一集！由于盒子相同且最多放一个球，无论怎么装，都可以交换盒子顺序额得到同一种方案，所以答案为：

顺带去看看 。

我会递推！
设 为 个球， 个盒子的方案数。
考虑新加进来一个球：
- 可以再拿一个盒子，盒子数目也就从 个变成了 个。那就从 转移过来；
- 可以放在之前任意一个盒子里，有 个盒子可选，即从 转移。
所以递推式为：

实际上，这就是 第二类斯特林数 。
解决 后，我们发现 。而 ，于是最后理所应当地得到了

非常神奇呢。

我会递推！
设 为 个球， 个盒子的方案数。
考虑这一个球 不放而让新开的盒子空着 还是 在之前的盒子里放多个：
- 可以不放这个球而让盒子空着，小球数目仍然为 个。拿过来了一个新的盒子，即从 转移。
- 在之前的盒子里放多个，盒子数目仍然为 个。即从 转移。

所以递推式为：

也可以从插板的角度考虑：
> 先往每个盒子里塞一个球，最后把这个球拿走就行了。换言之，先求「将 个相同小球，放入到 个不同盒子，盒子至少装一球」的方案数，对于每个这个问题的划分方案，将每个盒子抽掉一个球，就是 的方案。因此该问答案即为
>
>
>
> 引用自 囧仙

我会递推！
设 为 个球， 个盒子的方案数。
考虑这一个球 再开一个盒子放一个 还是 不放而让新开的盒子空着：
- 再开一个盒子放一个，盒子数目也就从 个变成了 个。那就从 转移过来；
- 可以不放这个球而让盒子空着，小球数目仍然为 个。拿过来了一个新的盒子，即从 转移。

所以递推式为：

实际上，这就是 组合数 。
也可以直接考虑选 个盒子装球，那答案也是一样的。

我会递推！
设 为 个球， 个盒子的方案数。
考虑这一个球 再开一个盒子放一个 还是 在之前的盒子里放多个：
- 再开一个盒子放一个，盒子数目也就从 个变成了 个。那就从 转移过来；
- 在之前的盒子里放多个，盒子数目仍然为 个。即从 转移。

所以递推式为：

也可以从插板的角度考虑，是最平凡的插板法。答案为

我会递推！
设 为 个球， 个盒子的方案数。可以发现，在所谓「第一个盒子里装一个球、第三个盒子里装三个球」是和「第一个盒子里装三个球、第三个盒子里装一个球」无异的。一种比较讨巧的做法是这样的：将盒子按照球的数量从小到大排序。这样的话，两种方案相同，仅当两种方案排序后的序列相同。所以可以：
- 在这个序列 开头加一个空盒子，盒子数目也就从 个变成了 个。那就从 转移过来；
- 让所有盒子里都加一个球，也就从 转移过来；

可以证明以上的转移方案是正确的。所以递推式为：

这个东西其实就是 划分数。

最简单的一集！

与 的唯一差别是每个盒子里都至少要一个球——那就先往盒子里都放一个球就好了。答案就是