带你搞定数学的 MBA大师上海中心
分堆问题
如果做个小调查,问问大家,在备考数学的过程中,最头疼的是哪一块,不用说,排列组合肯定榜上有名。今天,我们准备专攻排列组合中常考的一种题。这类题常常以各种形式出现,n个不同的球放入m个相同的盒子,有几种放法?n本不同的书,分给m个人,有多少种分法?(条件:n>=m)
还有很多种变体,m本不同的书分给n个同学,每个人至少分得一本书,有多少种分法?
相信很多同学,被这个类型的题目,搞得晕头转向的。今天我们就用一篇专题来着重解决这个问题。
这类问题一共有8种情况
1、n个相同的球,放入m个相同的盒子,无空盒。
2、n个相同的球,放入m个相同的盒子,可以有空盒。
3、n个相同的球,放入m个不同的盒子,无空盒。
4、n个相同的球,放入m个不同的盒子,可以有空盒。
5、n个不同的球,放入m个相同的盒子,无空盒。
6、n个不同的球,放入m个相同的盒子,可以有空盒。
7、n个不同的球,放入m个不同的盒子,无空盒。
8、n个不同的球,放入m个不同的盒子,可以有空盒。
为方便分析, 设n=8,m=3
01
球相同,盒子相同,无空盒
解析 :球入盒问题,可以看成分两步完成,首先是将8个球分成三堆,每堆至少一个. 由于这里球和盒子都相同,每三堆放入3个盒子中只有一种情况,所以只要将8个球分成三堆. 即1-1-6、1-2-5、1-3-4、2-2-4、2-3-3五种,故将8个相同的球放入3个相同的盒子中,每个盒子至少有一个, 有五种不同的放法.
But,考试不会考这么简单的题。
结论:n个相同的球放入m个相同的盒子(n≥m),不能有空盒时的放法种数等于n分解为m个数的和的种数.
02
球相同,盒子相同,可以有空盒
解析:与上题不同的是分成的三堆中,上题中的每一堆至少有一个球,而这个题中的三堆可以有球数为零的堆,即除了分成上面的五堆外,还可分为1-7、2-6、3-5、4-4和只一堆共五种情况,故8个相同的球放入3个相同的盒子中.,有十种不同的放法.
结论:n个相同的球放入m个相同的盒子(n≥m),可以有空盒时的放法种数等于将n分解为m个、(m-1)个、(m-2)个、…、2个、1个数的和的所有种数之和.
03
球相同,盒子不同,无空盒
解析:这是个相同的球放入不同的盒子中,与前面不同的是,这里盒子不同,所以不能再用前面的解法. 将8个球排成一排,形成7个空隙,在7个空隙中任取两个插入两块隔板,有C2 7 = 21种,这样将8个球分成三堆,第一堆放到1号盒子内,第二堆放到2号盒子内,第三堆放到3号盒子内. 故将8个相同的球放入标号为1、2、3的三个盒子中,每个盒子中至少有一个,有21种不同的放法.
结论:n个相同的球放入m个不同的盒子中(n≥m),不能有空盒的放法数
.
04
球相同,盒子不同,可以有空盒
解析:还是利用隔板原理将8个球分为三堆,只不过有的堆的球数为零,即在8个球之间插入两块隔板. 首先将8个球排成一排,就有9个空,任取一个空插入一块隔板,有
种;然后再将第二块隔板插入前面8个球和第一块隔板形成的10个空中,有
种,但这两种放法中有重复的,要除以2;最后将第一块隔板左边的球放入1号盒子中,两块隔板之间的球放入2号盒子中,第二块隔板右边的球放入3号盒子中. 故一共有