十二重计数法
十二重计数法
Zera / 捷攎复赛完了再写这篇文章是不是太迟了？
闲话：我只是为了初赛练练组合数学而做的，没有多少 OI 内容（可能复赛时会考虑添加？ 复赛寄的太彻底，不加了）。
我们教练说：初赛时排列组合的题目不会做就大力递推。虽然 CSP 初赛中数学题目越来越简单了，但这并不妨碍我仍然害怕着排练组合的题目。于是他让我来做这道题，并不是码，而是把递推式列出来。这方法确实很有用——于是我就写了这篇文章。
这篇文章是为我自己而写，也是为不会组合数学的人写的。所以很多理所当然的过程都写了上去，请多包含。
另附一些符号约定：
| 符号 | 意义 |
|---|---|
| 集合 |
|
| 集合 |
|
| 即 |
|
| 下降阶乘幂， |
|
P5824 十二重计数法
有
还有一些限制条件，那么有多少种方法放球？（与放的先后顺序无关）
限制条件分别如下：
想法
I
每个球都有
II
依次取球放进盒子，每次放球后方案数都会少一种，乘起来答案为
III
可以考虑先参考
那么考虑盒子的排列，一种很显然的答案就是
当然了，我们也可以考虑容斥：枚举空着的盒子的个数，不限制放置个数的方案总数 减去 有
设全集
容斥得
前面的系数
所以答案就是
这个时候我们可以再次回看
IV
先参考
与
V
最简单的一集！由于盒子相同且最多放一个球，无论怎么装，都可以交换盒子顺序额得到同一种方案，所以答案为：
顺带去看看
VI
我会递推！
设
考虑新加进来一个球：
- 可以再拿一个盒子，盒子数目也就从
个变成了 个。那就从 转移过来； - 可以放在之前任意一个盒子里，有
个盒子可选，即从 转移。
所以递推式为：
实际上，这就是 第二类斯特林数 。
解决后，我们发现 。而 ，于是最后理所应当地得到了
非常神奇呢。
VII
我会递推！
设
考虑这一个球 不放而让新开的盒子空着 还是 在之前的盒子里放多个：
- 可以不放这个球而让盒子空着，小球数目仍然为
个。拿过来了一个新的盒子，即从 转移。 - 在之前的盒子里放多个，盒子数目仍然为
个。即从 转移。
所以递推式为：
也可以从插板的角度考虑：
先往每个盒子里塞一个球，最后把这个球拿走就行了。换言之，先求「将
个相同小球，放入到 个不同盒子，盒子至少装一球」的方案数，对于每个这个问题的划分方案，将每个盒子抽掉一个球，就是 的方案。因此该问答案即为
引用自 囧仙
VIII
我会递推！
设
考虑这一个球 再开一个盒子放一个 还是 不放而让新开的盒子空着：
- 再开一个盒子放一个，盒子数目也就从
个变成了 个。那就从 转移过来； - 可以不放这个球而让盒子空着，小球数目仍然为
个。拿过来了一个新的盒子，即从 转移。
所以递推式为：
实际上，这就是 组合数
也可以直接考虑选
IX
我会递推！
设
考虑这一个球 再开一个盒子放一个 还是 在之前的盒子里放多个：
- 再开一个盒子放一个，盒子数目也就从
个变成了 个。那就从 转移过来； - 在之前的盒子里放多个，盒子数目仍然为
个。即从 转移。
所以递推式为：
也可以从插板的角度考虑，是最平凡的插板法。答案为
X
我会递推！
设
- 在这个序列
开头加一个空盒子，盒子数目也就从 个变成了 个。那就从 转移过来； - 让所有盒子里都加一个球，也就从
转移过来；
可以证明以上的转移方案是正确的。所以递推式为：
这个东西其实就是 划分数。
XI
最简单的一集！
XII
与
