太奇MBA数学助教
一.分组(分堆)与分配问题
李瑞玲
将n个不同元素按照某些条件分配给k个不同的对象,称为分配问题,又分为定向分配和不定向分配两种问题。
将n个不同元素按照某些条件分成k组,称为分组问题。分组问题有不平均分组,平均分组,部分平均分组三情况。
分组问题和分配问题是有区别的,前者组与组之间只要元素个数相同是不区分的,而后者即使两组的元素个数相同,但因所要分配的对象不同,仍然是可区分的。对于后者必须先分组后排列。一.基本的分组问题
例1.六本不同的书,分为三组,求在下列条件下各有多少种不同的分配方法?
(1)每组两本(均分三组)(2)一组一本,一组两本,一组三本(3)一组四本,另外两组各一本
(平均分组问题)(不平均分组问题)(部分平均分组问题)
分析:(1)分组和顺序无关,是组合问题。分组数为C62C42C22=90,而这90种分组方法实际上重复了6次。现把六本不同的书标上
1,2,3,4,5,6六个号码,先看一下这种情况:
(1,2)(3,4)(5,6)(3,4)(1,2)(5,6)(5,6)(1,2)(3,4)
(1,2)(5,6)(3,4)(3,4)(5,6)(1,2)(5,6)(3,4)(1,2)
由于书是均匀分组的,三组的本数都一样,又与顺序无关,所以这种
情况下这六种分法是同一种分法,于是可知重复了6次。以上的分组实际上加入了组的顺序,同理其他情况也是如此,因此还应取消分组
2
C62C42C290
的顺序,即除以P,于是最后知分法为==15.
P336
3
3
123
(2)先分组,分组方法是C6C5C3=60,那么还要不要除以P33???(很
关键的问题)
由于每组的书的本数是不一样的,因此不会出现相同的分法,即
123共有C6C5C3=60。
11(3)先分组,分组方法是C64C2C1=30,这其中有没有重复的分法???(需
要好好考虑)
现还把六本不同的书标上1,2,3,4,5,6六个号码,先看以下情况1)先取四本分一组,剩下的两本,一本一组,情况如下(1,2,3,4)5
6
(1,2,3,4)6
5
2)先取一本分一组,再取四本分一组,剩余的一本为一组,情况如下
5
(1,2,3,4)6
6(1,2,3,4)5
3)先取一本分一组,再取一本为一组,剩下的四本为一组,情况如下
5
6(1,2,3,4)
6
5(1,2,3,4)
由此可知每一种分法重复了2次,原因是其中两组的的书的本数都是一本,这两组有了顺序,需要把分组的顺序取消掉,而四本的那一组,由于书的本数不一样,不可重复,故最后的结果为
11
C64C2C130
==15.2
P22
通过以上三个小题的分析,可以得出分组问题的一般结论如下:一般地,将n个不同的元素分成p组,各组内元素个数分别为
m1,m2,⋯,mp,其中k组内元素个数相等,那么分组方法数为
Cnm1Cnm−2m1⋯Cnm−i(m1+m2+⋯+mi−1)⋯Cmpp
Pkk
的总组数的全排列!
m
,即选完元素后要除以元素相同
三.基本的分配问题1.定向分配问题
例2六本不同的书,分给甲乙丙三人,求在下列条件下各有多少种不同的分法?
(1)甲两本,乙两本,丙两本(2)甲一本,乙两本,丙三本(3)甲四本,乙一本,丙一本
分析:由于分配给三人,每人分几本是一定的,属于分配问题中的定向分配问题。由分步计数原理得(1)C62C42C22=902.不定向分配问题
例3.六本不同的书,分给甲乙丙三人,求在下列条件下各有多少种不同的分法?(1)每人两本
123
(2)C6C5C3=60
11
(3)C64C2C1=30
(2)一人一本,一人两本,一人三本(3)一人四本,一人一本,一人一本
分析:此题属于分配中的不定向分配问题。由于分配给三人,同一本书给不同的人是不同的分法,所以是排列问题。实际上可看作是“六本不同的书分为三组,再将这三组分给甲乙丙三人”,因此只要将元素的分组的方法数再乘以所分配对象的全排列即可!
2
C62C42C2
所以有(1)×P33=903
P3
123
(2)C6C5C3×P33=36011
C64C2C1
(3)×P33=902
P2
结论:一般地,如果把n个不同的元素分配给k个不同的对象,并且每个不同的对象可接受的元素个数没有限制,那么实际上是先分组后排列的问题,结果为分组方案数乘以不同对象数的全排列。解不定向分配题的一般原则是:先分组后排列!
数学讲义上第95页排列组合本章作业
第4题属于不定向分配问题(需要先分组,再分配,其中分组为不
123平均分组)结果为C6C5C3×P33=360,故选B。
123第5题属于定向分配问题,所以为C6C5C3=60,故选D。
第6题属于不定向分配问题(需要先分组,再分配,其中分组为平均
2
C62C42C23
分组)结果为×P3=90,故选C。3
P3
第28题也属于不定向分配问题,同第6题,结果为
44C12C84C43444
×P=CC3128C4,故选A。3
P3
元素种类
(1)元素相同(2)元素不同
1)分配对象相同2)分配对象不同1)分配对象相同2)分配对象不同分组(分堆)问题隔板法解决分组(分堆)问题可重复和不可重复此时要依据每组的数量来区别
要依据每组的数量和元素特征来区别可重复:投信,人进房间问题不可重复:组合,排列问题
例:现有6个球,4个盒子,每个盒子至少一个球,在下列各种情况下各有多少种放法?
(1)球不同,盒子不同(2)球不同,盒子相同(3)球相同,盒子不同(4)球相同,盒子相同解:(1)属于组合,排列问题,需要先分组,再分配给不同的对象。
分组有两种分法:1)2211
2)3111
[1**********]11
⎛C62C4C62C42C2C1C6C3C2C1C2C1C6C3C2C1⎞4⎜⎟则有+,最后结果为+23⎜⎟×P4.P22P33PP23⎝⎠
(2)由于分配对象相同,没有区别,所以实质上为分组问题。分组有两种分法:1)2
2)3
21
1111
113111
C62C42C2C1C6C3C2C1
则有+,即为最后结果。
P22P33
(3)球相同,即元素相同,但分配对象不同,又要求每个盒子至少一个球,故
3
为隔板问题,需用隔板法来解决,即C5=10种。
(4)球相同,盒子相同,就有两种方法,即22种方法。
11和3111这两