排列组合问题里什么时候会用到隔板法?请举例说明

来源:百度知道 编辑:UC知道 时间:2024/06/05 20:02:36
如题。。。

PS. 比如说20个相同的小球放在号码为1,2,3的三个盒子里,使每个盒子里的小球数不小于盒子上的数字,有多少种可能?

隔板法要求是把没有区别的几个“球”分成有序的几堆。
由于“球”没区别,所以各堆之间只能体现数目,无法体现是哪个球。其方法有二。
1、不允许有空堆。
例:x+y+z=10的正整数解。
9个空中放两个板成为三份。
2、允许有空堆。
例:x+y+z=10的非负整数解。
10个“球”和两个板占的12个位置中找两个 位置放板即可。
你的问题中,先去掉1+2+3=6个球,就是说,先在三个盒子里各放上要求的最少球数,所以另外要放的球的数为x,y,z,则x+y+z=14,求它的非负整数解的个数,用第2类方法。

120种 先在第2 3盒子里分别放1和2个球
剩下17个球 隔板法就是在剩下的17个球中插入2块挡板 使其分成3堆
所以是16个空中放两块挡板 16C2=120 种

实际上隔板法就是解X1+X2+...+Xn=M 的正整数解的组数的一种方法

应用隔板法必须满足三个条件:
(1) 这n个元素必须互不相异
(2) 所分成的每一组至少分得一个元素
(3) 分成的组别彼此相异
组合不排列的情况可以用隔板法