组合数学(苹果盘子问题)

发布时间 2023-11-23 15:40:24作者: 陆留生信奥艺术

初赛题目中往往会出现将多少东西(相同或者不同),分到一些容器(相同或者不同)中,允许或者不允许空的问题,这里我们就统一总结一下。

本篇博客中,物品统一称为苹果,容器统一称为盘子,因而得名为苹果盘子问题。

1.苹果相同,盘子不同,不允许空

思路:既然苹果是相同的,盘子是不同的,那么实际上我们的问题就是,将 nn 个苹果分成 mm 堆,有多少种不同的分法。此时,问题就可以转化为排列组合中的插空问题

2.苹果相同,盘子不同,允许空

思路:既然我们解决了上面的问题1,那么允许空的问题,我们同样可以尽力往问题1上面靠。

考虑到,我们现在可以分为为空的某一堆,那么我们要向问题1转化,最大的问题就在于如果使得问题转化为不允许空。我们发现,如果提前在 m 个盘子上放一个苹果,最后再拿走,最终的结果是不变的,因而我们可以将问题转化为,有 n+m个苹果,m 个盘子,不允许空的情况。

3.苹果相同,盘子相同,不允许空

思路:由于我们要把 n 个相同的苹果放到 m 个相同的盘子中,因而我们可以理解为把 n 个相同的苹果分成 m 堆。于是,这个问题就与整数划分问题相同了。

4.苹果相同,盘子相同,允许空

思路:这个问题同样地,我们向不允许空的问题上转化。我们可以发现,同样地枚举允许几个盘子为空即可。

5.苹果不同,盘子相同,不允许空

思路:本题目可以类似于:将 n个不同的元素分成 m个集合的方案总数。

6.苹果不同,盘子相同,允许空

思路:这个问题同样的,我们考虑向问题 5转化。由于现在是允许空,也就可以分为 nn 个苹果,放到 m,m−1,m−2,…,1个盘子里面,不允许空的方案数总和,这个问题也随之解决。(或者可以理解为,枚举有几个盘子为空,然后其他的都不为空,然后求解总和即可)

7.苹果不同,盘子不同,不允许空

思路:我们通过对题目反复思考之后可以发现,这个问题实际上就是第五个问题的延伸。既然这个问题,只是第五个问题中的 盘子相同 改变为 盘子不同,所以我们只需要对这个问题进行第五个问题的求解,然后乘上盘子的全排列(即同样的放置方案,放在不同盘子里的情况)即可。

注意:本处将问题拆分为递进的两步,先求苹果的方法,再求盘子的方法,最终结果也就是这两种方案总数的乘积(乘法原理)了。

8.苹果不同,盘子不同,允许空

思路:这个问题是整体上最简单的一个题目。由于苹果不同,盘子不同,也允许为空,所以我们的每一个苹果都可以放到任意一个盘子中去。