您好,欢迎光临赵帅的博客,如果有什么不足或者错误之处,感谢您留言指出!

【笔记】球盒问题(关于n个球和m个盒子的问题)

个人分享 赵 帅 290浏览 0评论

球盒问题

一、球相同,盒子相同,且盒子不能为空

例1. 8个相同的球放入3个相同的盒子中,每个盒子中至少有一个,问有多少种不同的方法?

解析:

球入盒子问题,可以看成分两步完成,首先是将8个球分成三堆,每堆至少一个。由于这里球和盒子都相同。由于这里球和盒子都相同,每三堆放入3个盒子中只有一种情况,所以只要将8个球分成三堆. 即1-1-6、1-2-5、1-3-4、2-2-4、2-3-3五种,故将8个相同的球放入3个相同的盒子中,每个盒子至少有一个, 有五种不同的放法。

结论:

n个相同的球放入m个相同的盒子(n>=m),不能有空盒时的放法种数等于n分解成m个数的和的种数。

二、球相同,盒子相同,且盒子可以空

例2.8个相同的球放入3个相同的盒子中. 问有多少种不同的放法?
解析:

与上题不同的是分成的三堆中,上题中的每一堆至少有一个球,而这个题中的三堆可以有球数为零的堆,即除了分成上面的五堆外,还可分为1-7、2-6、3-5、4-4和只一堆共五种情况,故8个相同的球放入3个相同的盒子中.,有十种不同的放法

结论:

n个相同的球放入m个相同的盒子(n>=m),不能有空盒时的放法种数等于n分解成m个数,m-1个数,m-2个数,……,2个,1个数的所有种数之和。、

三、球相同,盒子不同,且盒子不能为空

例3,8个相同的球放入1,2,3的三个盒子中,每个盒子中至少有一个,问有多少种不同的放法?(隔板法)

解析:

这是个相同球放入不同的盒子中,与前面不同的是,这里盒子不同,所以不能再用前面的解法。将8个球排成一排,形成7个空隙,在7个空隙中,任取两个插入两块隔板,有 C(2,7) = (7*6)/2 种,这样将8个球分成三堆,第一堆放到1号盒子内,第二堆放到2号盒子内,第三堆放到3号盒子内. 故将8个相同的球放入标号为1、2、3的三个盒子中,每个盒子中至少有一个,有21种不同的放法.

结论:

n个相同球放入m个不同的盒子中(n>=m),不能有空盒的方法数 C(m-1,n-1)

四、球相同,盒子不同,且盒子可以空

例4,8个相同的球放入标号为1、2、3的三个盒子中去,问有多少种不同的放法?

解析:

(1)与上一题不同的是,这里可以有盒子没放一个,还是利用 隔板原理 将8个球分为三堆,只不过有的堆的球数为零,即在8个球之间插入两块隔板.  首先将8个球排成一排,就有9个空,
任取一个空插入一块隔板,有C(1,9)种;然后再将第二块隔板插入前面8个球和第一块隔板形成的10个空中,有C(1,10)种,但这两种放法中有重复的,要除以2;最后将第一块隔板左边的球放入1号盒子中,两块隔板之间的球放入2号盒子中,第二块隔板右边的球放入3号盒子中。故一共有 1/2  * C(1,9) * C(1,10)  = C(2,10) = 10*9 / 2 = 45 种。

(2)将8个球分成三堆(包括没有0数堆和有0数堆),也就是在8个球的9个空隙中取两个插入隔板或取一个插入两块隔板,即 C(1,9) + C(2,9) = 9 + 36 = 45

(3)上面的 例3。8个相同的球放入标号为1,2,3的三个盒子中,每个盒子中至少有一个,先放一个在每一个盒子里面,只有一种情况。然后将剩下的5个球排成一排,插入两块隔板,

有 1/2 * C(1,6) * C(2,7) = 7 * 6 / 2 =  21种。

结论:

n个相同的球放入m个不同的盒子中(n>=m),可以有空盒的方法数 C(m-1, n+m-1) 

五、球不同,盒子相同,且盒子不能空

例5,8个不同球放入三个相同的盒子中,每个盒子中至少有一个。问有多少种情况?

解析:

由于盒子相同,所以只要对 8个不同的球分成三堆就行了,因为放入盒子只有一种情况。而8个球分成三堆,各堆球数一次为 1-1-6、1-2-5、1-3-4、2-2-4、2-3-3五种.

对情况1-1-6有 C(1,8) * C(1,7) * C(6,6) /2 种分法,对情况1-2-5有 C(1,8) * C(2,7) * C(5,5) /2 种分法,对情况1-3-4有 C(1,8) * C(3,7) * C(4,4) 种分法,对情况2-2-4有2442628CCC种分法,对情况2-3-3有23
3628CCC(注意,分组有几组个数相同即几组均分就要除以几的阶乘).所以加起来一共 966 种。

结论:

n个不同的球放入m个相同的盒子中(n>=m),不能有空盒的方法种数等于n个不同的球分成m堆的种数。

六、球不同,盒子相同,且盒子可以空

例6,8个不同的球放入3个相同的盒子里,问有多少种不同的做法?

解析:

只是比上一题多了两种情况,一是一堆为0的,即分为两堆,1-7,2-6,3-5,4-4四种情况,有 C(1,8)*C(7,7) + C(2,8) * C(6,6) + C(3,8)*C(5,5) + 1/2 * C(4,8) = 127;二是有两堆为0的,即只分为一堆,一种情况。所以一共有 966 + 127 + 1 = 1094种

结论:

n个不同的球放入m个相同的盒子中(n≥m),可以有空盒的放法种数等于将n个不同的球分成m堆、(m-1)堆、(m-2)堆、…、2堆、1堆的所有种数之和.

七、球不同,盒子不同,且盒子不能空

例7,8个不同的球放入标号为1,2,3的三个盒子中,每个盒子至少有一个。问有多少种不同的放法?

解析:

这个问题就等价于“8本不同的书分给3个同学,每人至少有一本,有多少种分法?”

就是在例5先分堆的基础上,再加一步,分到三个不同的盒子中. 即 966 * A(3,3) =5796

结论:

n个不同的球放入m个不同的盒子中,(n>=m),不能有空盒的放法种数等于n个不同的球分成m堆的种数乘以m!

八、球不同,盒子不同,且盒子可以空

例8,8个不同的球放入标号为1,2,3的三个盒子中,问有多少种不同的放法?

解析:

包括分三堆的 5796 种,还有分两堆得 127*A(3,3) = 762,还有只分一堆的 3种情况,所以一共是  5796 + 762 + 3 = 6561 种。

结论 

n个不同的球放入m个不同的盒子中(n≥m),可以有空盒的放法种数等于m^n种.

转载请注明:碎念 » 【笔记】球盒问题(关于n个球和m个盒子的问题)

喜欢 (3)or分享 (0)