排列组合之分堆问题.doc

关于分组(堆)问题的六个模型及求法
(833200)新疆奎屯市第一高级中学王新敞
引例将6本不同的书按下列分法,各有多少种不同的分法?
⑴分给学生甲3 本,学生乙2本,学生丙1本;
⑵分给甲、乙、丙3人,其中1人得3本、1人得2 本、1 人得1 本;
⑶分给甲、乙、丙3人,每人2本;
⑷分成3堆,一堆3 本,一堆2 本,一堆1 本;
⑸分成3堆,每堆2 本;
⑹分给分给甲、乙、丙3人,其中一人4本,另两人每人1本;
⑺分成3堆,其中一堆4本,另两堆每堆1本.
分析:①分书过程中要分清:是均匀的还是非均匀的;是有序的还是无序的.
②特别是均匀的分法中要注意算法中的重复问题.
解:⑴是指定人应得数量的非均匀问题:①学生甲从6本中取3 本有种取法,②学生乙从余下的3本中取2本有种取法,③学生丙从余下的1本中取1本有种取法. 所以方法数为=60;
⑵是没有指定人应得数量的非均匀问题:①从6本中取3 本作为一堆有种取法,②从余下的3本中取2本作为一堆有种取法,③从余下的1本中取1本作为一堆有种取法,④将三堆依次分给甲乙丙三人有种分法. 所以方法数为=360;
⑶是指定人应得数量的均匀问题:①学生甲从6本中取2本有种取法,②学生乙从余下的4本中取2本有种取法,③学生丙从余下的2本中取2本有种取法. 所以方法数为=90;
⑷是分堆的非均匀问题:①从6本中取3 本作为一堆有种取法,②从余下的3本中取2本作为一堆有种取法,③从余下的1本中取1本作为一堆有种取法. 所以方法数为=60;
⑸是分堆的均匀问题:相当于①学生甲从6本中取2本有种取法,②学生乙从余下的4本中取
2本有种取法,③=,故方法数为=15;
⑹是部分均匀地分给人的问题:方法数为=90;
⑺是部分均匀地分堆的问题:方法数为=15.
以上问题归纳为:
分给人(有序)
分成堆(无序)
非均匀
均匀
部分均匀
分组(堆)问题有六个模型:①有序不等分;②有序等分;③有序局部等分;④无序不等分;⑤无序等分;⑥、.
例1 ( 2006年重庆卷理(8)) 将5名实****教师分配到高一年级的3个班实****每班至少1名,最多2名,则不同的分配方案有( )
(A)30种(B)90种(C)180种(D)270种
分析:这是一个有序局部等分问题. 根据题意应先将5名实****教师按(2~2~1)分为三组,然后再将这三组依次安排到高一年级的3个班实****br/>解:将5名实****教师分配到高一年级的3个班实****每班至少1名,最多2名,则将5名教师分成三组,一组1人,另两组都是2人,有种方法,再将3组依次分到3个班有种分法. 根据分步计数原理,共有种不同的分配方案,故选B.
点评:没有明确安排各学校的教师分配数量时,要先将教师分成堆(组)再将各堆依次分配到学校,简称为“先分组,后到位”;对于局部均匀的分堆(组),先依次选取出来再去掉均匀堆(组)选出的顺序,即除以均匀堆(组)数的全排列.
例2(2007陕西理科第16题)安排3名支教老师去6所学校任教,每校至多2人,则不同的分配方案共有种.(用数字作答)
分析:根据题意应先将3名