排列组合之分堆问题
煎饼侠主题曲-竞争管理
排列组合之分堆问题(教师)
引例
将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本.
分析:①分书过程中要分清:是均匀的还是非均匀的;是有序的还是无序的.
②特别是均匀的分法中要注意算法中的重复问题.
3
解:⑴是指定人应得数量的非均匀问题:①学生甲从6本中取3 本有
C
6
种取法,②学生
1
乙从余下的3本中取2本有
C
3
2
种取法,③学生丙从余下的1本中取1本有
C
1
种取法. 所以方法数
32
1
为
C
6
C
3
C
1
=60;
3
⑵是没有指定人应得数量的非均匀问题:①从6本中取3 本作为一堆有
C
6
种取法,②从
1
余下的3本中取2本作为一堆有
C
3
2<
br>种取法,③从余下的1本中取1本作为一堆有
C
1
种取法,④将
33213
三堆依次分给甲乙丙三人有
P
3
种分法. 所以方法数为
C
6
C
3
C
1
P
3
=360; 2
⑶是指定人应得数量的均匀问题:①学生甲从6本中取2本有
C
6
种取
法,②学生乙从余下
22
的4本中取2本有
C
4
种取法,③学生丙从
余下的2本中取2本有
C
2
种取法. 所以方法数为
222
C
6
C
4
C
2
=90;
3
⑷是分堆的非均匀问题:①从6本中取3 本作为一堆有
C
6
种取
法,②从余下的3本中取2
1
本作为一堆有
C
3
2
种取法,
③从余下的1本中取1本作为一堆有
C
1
种取法. 所以方法数为
321C
6
C
3
C
1
=60;
2
⑸是分堆
的均匀问题:相当于①学生甲从6本中取2本有
C
6
种取法,②学生乙从余下的422222
本中取2本有
C
4
种取法,③学生丙从余下的2本中取2本有
C
2
种取法.方法数为
C
6
C
4
C
2
=90.然
2223
后再取消甲乙丙的分配顺序,故方法数为
C
6
=15;
C
4
C
2
A
3
411
C
6
C
2
C
1
P
3
3
⑹是部分均匀地分给人的问题:方法数为=90;
2
A
2
11<
br>C
6
4
C
2
C
1
⑺是部分均匀地分堆的问题:方法数为=15.
2
A
2
以上问题归纳为:
非均匀
均匀
部分均匀
分给人(有序)
321C
6
C
3
C
1
P
3
3
222
C
6
C
4
C
2
411<
br>C
6
C
2
C
1
P
3
3
分
成堆(无序)
321
C
6
C
3
C
1
<
br>222
C
6
C
4
C
2
P
3
3
411
C
6
C
2
C
1
P<
br>2
2
P
2
2
分组(堆)问题有六个模型
:①有序不等分;②有序等分;③有序局部等分;④无序
不等分;⑤无序等分;⑥无序局部等分.是排列
、组合及其应用基本问题.在历年的各地高考
试题中都有体现.
例1 (
2006年重庆卷理8)
将5名实习教师分配到高一年级的3个班实习,每班至少1
名,最多2名,则不同的分配方案有(
)
(A)30种 (B)90种 (C)180种
(D)270种
分析:这是一个有序局部等分问题. 根据题意应先将5名实习教师按(2~2~1)
分为三
组,然后再将这三组依次安排到高一年级的3个班实习.
解:将5名实习教师分配到高
一年级的3个班实习,每班至少1名,最多2名,则将5
122
C
5
C4
C
2
名教师分成三组,一组1人,另两组都是2人,有
15
种方法,再将3组依次分到
2
A
2
3
3个班有
A
3
6
种分法.
根据分步计数原理,共有
15690
种不同的分配方案,故选B.
点评:没有明
确安排各班学校的教师分配数量时,要先将教师分成堆(组)再将各堆依
次分配到班学校,简称为“先分
组,后到位”;对于局部均匀的分堆(组),先依次选取出来
再去掉均匀堆(组)选出的顺序,即除以均
匀堆(组)数的全排列.
例2(2007陕西理科第16题)安排3名支教老师去6所学校任教,每
校至多2人,则
不同的分配方案共有
210
种.(用数字作答) 分析:根据题意应先将3名支教老师按(1~1~1)分为三组或按(2~1)分为两组,然
后再将
这组依次安排到学校.
111
C
3
C
2
C
1
解:①将3名支教老师按(1~1~1)分为三组有
1
种分法,再将三组
依次分到
3
A
3
3
学校有
A
6
120<
br>种中分法,根据分步计数原理,共有1×120=120种不同的分配方案;
1
②将3
名支教老师按(2~1)分为两组有
C
3
2
C
1
3
种分法,再将两组依次分到学校有
2
A
6
30
中分法,根据分步
计数原理,共有3×30=90种不同的分配方案.
再由分类计数原理,共有120+90=210种不同的分配方案. 故填210.
点评:分类讨论问题是考试的热点.
本题是将分类与分组问题巧妙的融合在了一起,同
时达到考察分类计数原理和分步计数原理的目的.
例3 (2007宁夏理科第16题)某校安排5个班到4个工厂进行社会实践,每个班去
一个
工厂,每个工厂至少安排一个班,不同的安排方法共有 种.(用数字作答)
分析:5个班到4个工
厂进行社会实践,每个班去一个工厂,每个工厂至少安排一个班,
说明必有某一个工厂安排了两个班,其
余的3个工厂各有一个班,由于到一个工厂的两个班
的“地位”是等同的(无序),不能出现谁先进入谁
后进入的局面,也就是说这两个班要同时
进入(无序)到这个工厂才可以. 因此应该先分组后到班.
111
C
5
2
C
3
C
2
C
1
解:由题意,先将5个班分为四组(2~1~1~1)有
10
种分法;再将这四
3
A
3
4
组依次分配到4个工厂有
A
4
24
种分配方法.
根据分步计数原理,共有10×24=240种不同
的进行社会实践分配方案. 故填240.
一般地,对于分组(堆)的问题模型,其解题思路及步骤为:①明确每个人的分配数量
时,依次选取即
可;没有明确安排位置的分配数量时,要先分堆(组)再将各堆依次安排到
对应位置,简称为“先分组,
后到位”;②非均匀的分堆(组),依次选取出来即可;③均匀
的分堆(组),先依次选取出来再去掉选
出的顺序,即除以堆(组)数的全排列;④局部均匀
的分堆(组),先依次选取出来再去掉均匀堆(组)
选出的顺序,即除以均匀堆(组)数的全
排列.
排列组合之分堆问题
引例 将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本.
分组(堆)问题有六个模型:①有序不等分;②有序等
分;③有序局部等分;④无序不
等分;⑤无序等分;⑥无序局部等分.是排列、组合及其应用基本问题.
在历年的各地高考试
题中都有体现.
例1(2006年重庆卷理8)
将5名实习教师分配到高一年级的3个班实习,每班至少1
名,最多2名,则不同的分配方案有(
)
(A)30种 (B)90种 (C)180种
(D)270种
例2(2007陕西理科第16题)安排3名支教老师去6所学校任教,每校至多2人
,则不
同的分配方案共有
210
种.(用数字作答)
例3
(2007宁夏理科第16题)某校安排5个班到4个工厂进行社会实践,每个班去一
个工厂,每个工厂
至少安排一个班,不同的安排方法共有 种.(用数字作答)
一般地,对于分组(堆)的问题模型,
其解题思路及步骤为:①明确每个人的分配数量
时,依次选取即可;没有明确安排位置的分配数量时,要
先分堆(组)再将各堆依次安排到
对应位置,简称为“先分组,后到位”;②非均匀的分堆(组),依次
选取出来即可;③均匀
的分堆(组),先依次选取出来再去掉选出的顺序,即除以堆(组)数的全排列;
④局部均匀
的分堆(组),先依次选取出来再去掉均匀堆(组)选出的顺序,即除以均匀堆(组)数的全
排列。