组合数只会求还不行！组合数指南之盒子与球问题
-1. 一些闲话
关于 动机
其实我只是觉得这玩意难上加难才写这篇博客的。
才怪写这篇博客其实是因为我担心 NOIP CSP 会考.....
关于 食用人群
真正的老少皆宜
但说实话最适合信竞，其次是数竞电竞
关于 难度
其实很难但经过我讲解就很简单了（不要脸）
比较适中，自己理解（没有我讲）可能会难上加难
文章较短，但所含知识较烧脑，理解起来还需花一番功夫。
0. 前置知识
I.组合数
1.定义：用表示
个物品选
个（不排序）的方案数。
2.性质：
1>
2>
3>（证明：利用性质2）
>
（性质3的扩展）
4>
3.求法：略
II.第二类斯特林（Stirling II）数
1.定义：把 个物品分成
个集合的方案数叫第二类斯特林数，用
表示。其中
个物品互不相同，
个集合相同。亦写作S2{n,k}。
2.递推式：略
.分析：第
个人可以一个人一个集合，也可以加入前面
个集合中任意一个。
For more information ：
更多知识，请访问 [戳](https://www.luogu.org/blog/setfire/binom-learning)
1. 基本模型
就是：有 n 个球放进 k 个盒子，请问有多少种不同的放法？
当然了，会有一些奇怪的限制，造成答案的极其不同。
2. 盒子不同的盒子与球问题
1> 盒子不同，球相同，盒子不可为空
解释：我们取 个球如下:
在其中插入 块个板, 不能插在边上。
可见，球被分成了 份，恰好对应
个盒子且不可能为空（因为两块板不能插在一起啊），所以结果就是在
个 空中插 入
块板所对应的的方案数。（预计思考：
）
2> 盒子不同，球相同，盒子可以为空
解释：其实就是 2> 的升级版，只不过可以为空了。
那么我们可以先加入 个球，在分完组后再从每个集合拿走一个球，这样既保证了球总数为
，也使得有一部分集合可以为空（就是最开始分完后只包含一个球的那些集合，它们拿走一个球后就为空）（预计思考：
）
3> 盒子不同，球不同，盒子可以为空
解释：因为对于每个球都有放入1号盒子，2号盒子，...，k号盒子的选择，故答案为 个
连乘。
4> 盒子不同，球不同，盒子不可为空
（奇怪的 语法）
解释：将 个球分为
个集合（
显然不能为空），但因为集合是不同的，所以集合内部还可以排序，即乘上 种排列方法。
3. 盒子相同的盒子与球问题
1> 盒子相同，球相同，盒子不可为空
解释：定义一个叫化分数的东西 ，表示将
分成
个数（不排序）有多少方案。
这个东西的递推式：
$\therefore$ 显然这个的答案就是化分数。
2> 盒子相同，球相同，盒子可以为空
解释：因为盒子是相同的，所以盒子为空相当于去掉那一个盒子（预计思考：）
那么我们可以将 为
至
时的化分数加起来，即代表了
个，
个，...，
个盒子为空时所对应的方案数。（正确性预计思考：
）
3> 盒子相同，球不同，盒子不可为空
解释：其实就是 *2. 3> * 中去掉给盒子排序那一步。
4> 盒子相同，球不同，盒子可以为空
解释：因为盒子是相同的，所以盒子为空相当于去掉那一个盒子（同前）
那么我们可以将 为
至
时的第二类斯特林数加起来，即代表了
个，
个，...，
个盒子为空时所对应的方案数。（正确性预计思考：
，和前面有点不同）
4. 一些题
这个是给信竞生看的（笑）
仅给两题，都是比较基础的模板：
Luogu 数的划分
提示：3. 1>
Openjudge 鸣人的影分身
提示：3. 2>
5. Summarize
在遇到盒子与球问题时，一定不要慌张或放弃，先思考是否为上面所叙述的八类（万一是抽屉原理呢），再思考具体是哪一类，最后根据情况写出相应的码。
以上就是盒子与球的所有内容，看完一定记得勤总结这类问题哦~
怎么样，有收获吗？那就施舍一个赞吧~有什么建议，也欢迎提出哦！
查看10道真题和解析
