组合数学（苹果盘子问题）
苹果盘子问题
初赛题目中往往会出现将多少东西（相同或者不同），分到一些容器（相同或者不同）中，允许或者不允许空的问题，这里我们就统一总结一下。
本篇博客中，物品统一称为苹果，容器统一称为盘子，因而得名为苹果盘子问题。
写在开头
本类题目会大量地与排列组合结合，因而先放出排列组合的公式，如果读者对排列组合不了解，可以先去查询一下排列组合的相关性质以及表示方式等等。
-
组合：
C_n^m=\frac{n!}{m!(n-m)!} （在本文中，也用\binom{n}{m} 表示组合数C_n^m ） -
排列：
A_n^m=\frac{n!}{(n-m)!}
目录
1.苹果相同，盘子不同，不允许空
2.苹果相同，盘子不同，允许空
3.苹果相同，盘子相同，不允许空
4.苹果相同，盘子相同，允许空
5.苹果不同，盘子相同，不允许空
6.苹果不同，盘子相同，允许空
7.苹果不同，盘子不同，不允许空
8.苹果不同，盘子不同，允许空
1.苹果相同，盘子不同，不允许空
如果有
思路分析
既然苹果是相同的，盘子是不同的，那么实际上我们的问题就是，将
此时，问题就可以转化为排列组合中的插空问题（如下图）。
类似于，在
3.苹果相同，盘子相同，不允许空
如果有
思路分析
-
由于我们要把
n 个相同的苹果放到m 个相同的盘子中，因而我们可以理解为把n 个相同的苹果分成m 堆。于是，这个问题就与整数划分问题相同了。 -
我们使用
f_{i,j} 表示将i 个苹果放进j 个盘子里的方案数。那么对于每一个f_{i,j} ，都有如下方案：-
如果我们将
1 个苹果放在一个盘子里，那么f_{i,j}=f_{i-1,j-1} 。（在这个盘子中至少需要放一个） -
如果我们在每一个盘子里都放一个苹果，那么
f_{i,j}=f_{i-j,j} 。
-
-
综上，我们可以得到，
f_{i,j}=f_{i-1,j-1}+f_{i-j,j} 。 -
最终答案
ans=f_{n,m} 。
4.苹果相同，盘子相同，允许空
这个问题同样地，我们向不允许空的问题上转化。我们可以发现，同样地枚举允许几个盘子为空即可。所以最终答案实际上就等于
其中
5.苹果不同，盘子相同，不允许空
本题目可以类似于：将
-
首先，我们考虑将
n 拆分成m 份。我们就可以得到1-1-6,1-2-5,1-3-4,2-2-4,2-3-3 这五种不同的拆分方案。 -
然后，对于每一种拆分方案，我们可以求解其内部分方案数。
-
1-1-6$ 这一方案，可以分为先选 $1$ 个，再选 $1$ 个，最后剩下 $6$ 个。其中，选一个的情况有重复出现，于是还需要去重。最终结果 $ans=C_8^1C_7^1C_6^6/A_2^2 -
-
1-3-4$ 的最终结果 $ans=C_8^1C_7^3C_4^4 -
2-2-4$ 的最终结果 $ans=C_8^2C_6^2C_4^4/A_2^2 -
2-3-3$ 的最终结果 $ans=C_8^2C_6^3C_3^3/A_2^2
-
-
而最终的结果就是上面五种情况的和。
-
注意：如果出现了例如
2-2-3-3 这样的情况，最终除的应该是A_2^2*A_2^2 ，原因是2 出现一次重复，3 出现一次重复之后，根据乘法原理，一共重复的应该是乘积次。
6.苹果不同，盘子相同，允许空
这个问题同样的，我们考虑向问题
由于现在是允许空，也就可以分为
7.苹果不同，盘子不同，不允许空
我们通过对题目反复思考之后可以发现，这个问题实际上就是第五个问题的延伸。
既然这个问题，只是第五个问题中的 盘子相同 改变为 盘子不同，所以我们只需要对这个问题进行第五个问题的求解，然后乘上盘子的全排列（即同样的放置方案，放在不同盘子里的情况）即可。
注意：本处将问题拆分为递进的两步，先求苹果的方法，再求盘子的方法，最终结果也就是这两种方案总数的乘积（乘法原理）了。
8.苹果不同，盘子不同，允许空
这个问题是整体上最简单的一个题目。由于苹果不同，盘子不同，也允许为空，所以我们的每一个苹果都可以放到任意一个盘子中去。
因而，我们枚举每个苹果，并将其放在