文档库

最新最全的文档下载
当前位置:文档库 > 分组与隔板法

分组与隔板法

组合问题中分组问题和分配问题.

(1)非均匀不编号分组:将n 个不同元素分成不编号的m 组,每组元素数目均不相同,且不考虑各组间顺序,不管是否分尽,其分法种数为

1m n

C

A =2

1m m -n C …k m )m ...m (m -n 1-k 21C +++

例1:10人分成三组,每组人数分别为2、3、5,其分法种数为2520

5

538210=C C C 若从

10人中选出6人分成三组,各组人数分别为1、2、3,其分法种数为

12600

3

729110=C C C .

(2)均匀不编号分组:将n 个不同元素分成不编号的m 组,假定其中r

组元素个数相等,不管是否分尽,其分法种数为r

r A A /(其中

A 为非均匀不

编号分组中分法数).如果再有K 组均匀分组应再除以k

k A .

例2:10人分成三组,各组元素个数为2、4、4,其分法种数为

1575

/224

448210=A C C C .

若分成六组,各组人数分别为1、1、2、2、2、2,其分法种数为4

4

222224262819110/A A C C C C C C ?

(3)非均匀编号分组: n 个不同元素分组,各组元素数目均不相等,且

考虑各组间的顺序,其分法种数为m m

A A ?

例3:10人分成三组,各组人数分别为2、3、5,去参加不同的劳动,其安排方法为:3

3

5538210A C C C ???种.

若从10人中选9人分成三组,人数分别为2、3、4,参加不同的劳动,

则安排方法有

33

4538210A C C C ?种

(4)均匀编号分组:n 个不同元素分成m 组,其中r 组元素个数相同且

考虑各组间的顺序,其分法种数为

)(r

r

A A A /m

m ?.

例4:10人分成三组,人数分别为2、4、4,参加三种不同劳动,分法种数为

3

3

22

4448210A A C C C ?

练习题:

1 将13个球队分成3组,一组5个队,其它两组4个队, 有多少分法?(544213842

/C C C A )

2.10名学生分成3组,其中一组4人, 另两组3人但正副班长不能分在同一组,有多少种不同的分组方法 (1260)

3.某校高二年级共有六个班级,现从外地转入4名学生,要安排到该年级的两个班级且每班安排2名,则不同的安排方案种数为______(2222

4262/90

C C A A )

作业1:

(1) 今有10件不同奖品,从中选6件分给三份,一份一件,一份二件和一份三件,有多少种分法?

(2)今有10件不同奖品,从中选6件分给甲一件,乙二件和丙三件,有多少种分法?

(3) 今有10件不同奖品, 从中选6件分给三人,其中1人一件1人二件1人三件, 有多少种分法?

(4) 今有10件不同奖品, 从中选6件分成三份,每份2件, 有多少种分法?

(5) 今有10件不同奖品, 从中选6件分成三份,一份4件,另外2份各一件, 有多少种分法?

(6)今有10件不同奖品, 从中选6件分成三个人,一个人4件,另外2个人各一件, 有多少种分法?

(7)今有10件不同奖品, 从中选6件分成三个人,每人2件, 有多少种分法? 作业2:(1)10个相同的球装5个盒中,每盒至少一个有多少装法? (2) 25x y z w +++=求这个方程组的自然数解的组数

隔板法

隔板法又叫隔墙法,插板法,n 件相同物品(n 个名额)分给m

个人,名额分配,相同物品分配常用此法。

若每个人至少1件物品(1个名额),则n 件物品(n 名额)排成1排,中间有n-1个空挡,在这个n-1空档选m-1个空挡放入隔板,隔板1种插法对应1

种分法,所以有1

1--m n C 种分法。

若允许有人分不到物品 ,则先把n 件物品和m-1块隔板排成一排,

有n+m-1个位置,从这个位置中选m-1个位置放隔板,有1

1

--+m m n C

种方法,

再将n 件物品放入余下的位置,只有1种方法,m-1块隔板将物品分成m 块,从左到右可看成每个人分到的物品数,每1种隔板的放法对应一种分法,所以共有11

--+m m n C

种分法。

例4 9个 颜色大小相同的分别放入编号分别为1,2,3,4,5,

6的6个盒中,要求每个盒中至少放1个小球,有多少种方法?

解:(法1)将9个小球排成一排,9个小球之间有8个空挡,在

这8个空挡选5个空挡放5个隔板,将9个小球分成6份,每份至少1个球,将这6份放到6个盒中,有5

C=56种方法。

8

(法2)先给每个盒中放1个球,然后将余下的3个小球和5块

隔板排成一排,排列位置有8个,先从8个位置中选5个放隔板,有5

C=56

8

种方法,再余下位置放小球只有1种方法,5块隔板将小球分成6块,

从左到右看成6个盒所得球数,每一种隔板放法对应1种分法,故有5

C=56

8

种方法。

例6.有10个运动员名额,分给7个班,每班至少一个,有多少种分配方案?

解:因为10个名额没有差别,把它们排成一排。相邻名额之间形成9个空隙。在9个空档中选6个位置插个隔板,可把名额分成7份,

对应地分给7个班级,每一种插板方法对应一种分法共有6

C种分

9法。

分组与隔板法

分组与隔板法

分组与隔板法

分组与隔板法

分组与隔板法

分组与隔板法

分组与隔板法

分组与隔板法

分组与隔板法

二班三班四

七班

变式1:某校准备参加今年高中数学联赛,把16个选手名额分配到高三年级的1-4 个教学班,每班至少一个名额,则不同的分配方案共有___种. 变式2:某校准备参加今年高中数学联赛,把16个选手名额分配到高三年级的1-4 个教学班,每班的名额不少于该班的序号数,则不同的分配方案共有___种.: 练习题:

1 100x y z w +++=求这个方程组的正整数解的组数

2 100x y z w +++=求这个方程组的自然数解的组数 3103

C

顺序固定用“除法”:

对于某几个元素按一定的顺序排列问题,可先把这几个元素与其他元素一同进行全排列,然后用总的排列数除于这几个元素的全排列数。

例4、6个人排队,甲、乙、丙三人按“甲---乙---丙”顺序排的排队方法有多少种?

分析:不考虑附加条件,排队方法有A66种,而其中甲、乙、丙的A33种排法中只有一种符合条件。故符合条件的排法有A66 ÷A33 =120种。(或A63种)

例5、4个男生和3个女生,高矮不相等,现在将他们排成一行,要求从左到右女生从矮到高排列,有多少种排法。

解:先在7个位置中任取4个给男生,有A74种排法,余下的3个位置给女生,只有一种排法,故有A74 种排法。(也可以是A77 ÷A33种)