排列组合中分组(分堆)与分配问题

排列组合中分组(分堆)与分配问题

ID:40162195

大小:92.55 KB

页数:5页

时间:2019-07-24

排列组合中分组(分堆)与分配问题_第1页
排列组合中分组(分堆)与分配问题_第2页
排列组合中分组(分堆)与分配问题_第3页
排列组合中分组(分堆)与分配问题_第4页
排列组合中分组(分堆)与分配问题_第5页
资源描述:

《排列组合中分组(分堆)与分配问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、太奇MBA数学助教李瑞玲一.分组(分堆)与分配问题将n个不同元素按照某些条件分配给k个不同的对象,称为分配问题,又分为定向分配和不定向分配两种问题。将n个不同元素按照某些条件分成k组,称为分组问题。分组问题有不平均分组,平均分组,部分平均分组三情况。分组问题和分配问题是有区别的,前者组与组之间只要元素个数相同是不区分的,而后者即使两组的元素个数相同,但因所要分配的对象不同,仍然是可区分的。对于后者必须先分组后排列。一.基本的分组问题例1.六本不同的书,分为三组,求在下列条件下各有多少种不同的分配方法?(1)每组两本(均分三组)(平均分组问题)(2)一组一本,一组

2、两本,一组三本(不平均分组问题)(3)一组四本,另外两组各一本(部分平均分组问题)分析:(1)分组和顺序无关,是组合问题。分组数为222CCC=90,642而这90种分组方法实际上重复了6次。现把六本不同的书标上1,2,3,4,5,6六个号码,先看一下这种情况:(1,2)(3,4)(5,6)(1,2)(5,6)(3,4)(3,4)(1,2)(5,6)(3,4)(5,6)(1,2)(5,6)(1,2)(3,4)(5,6)(3,4)(1,2)由于书是均匀分组的,三组的本数都一样,又与顺序无关,所以这种情况下这六种分法是同一种分法,于是可知重复了6次。以上的分组实际上

3、加入了组的顺序,同理其他情况也是如此,因此还应取消分组222的顺序,即除以3C6C4C290P,于是最后知分法为==15.33P63(2)先分组,分组方法是1233CCC=60,那么还要不要除以P???(很6533关键的问题)由于每组的书的本数是不一样的,因此不会出现相同的分法,即共有123CCC=60。653(3)先分组,分组方法是411CCC=30,这其中有没有重复的分法???(需621要好好考虑)现还把六本不同的书标上1,2,3,4,5,6六个号码,先看以下情况1)先取四本分一组,剩下的两本,一本一组,情况如下(1,2,3,4)56(1,2,3,4)652

4、)先取一本分一组,再取四本分一组,剩余的一本为一组,情况如下5(1,2,3,4)66(1,2,3,4)53)先取一本分一组,再取一本为一组,剩下的四本为一组,情况如下56(1,2,3,4)65(1,2,3,4)由此可知每一种分法重复了2次,原因是其中两组的的书的本数都是一本,这两组有了顺序,需要把分组的顺序取消掉,而四本的那一组,由于书的本数不一样,不可重复,故最后的结果为411CCC30621==15.2P22通过以上三个小题的分析,可以得出分组问题的一般结论如下:一般地,将n个不同的元素分成p组,各组内元素个数分别为m,m,⋯,m,其中k组内元素个数相等,那

5、么分组方法数为12pCm1Cm2⋯Cmi⋯Cmpnn−m1n−(m1+m2+⋯+mi−1)mpk,即选完元素后要除以元素相同Pk的总组数的全排列!三.基本的分配问题1.定向分配问题例2六本不同的书,分给甲乙丙三人,求在下列条件下各有多少种不同的分法?(1)甲两本,乙两本,丙两本(2)甲一本,乙两本,丙三本(3)甲四本,乙一本,丙一本分析:由于分配给三人,每人分几本是一定的,属于分配问题中的定向分配问题。由分步计数原理得(1)222123411CCC=90(2)CCC=60(3)CCC=306426536212.不定向分配问题例3.六本不同的书,分给甲乙丙三人,求

6、在下列条件下各有多少种不同的分法?(1)每人两本(2)一人一本,一人两本,一人三本(3)一人四本,一人一本,一人一本分析:此题属于分配中的不定向分配问题。由于分配给三人,同一本书给不同的人是不同的分法,所以是排列问题。实际上可看作是“六本不同的书分为三组,再将这三组分给甲乙丙三人”,因此只要将元素的分组的方法数再乘以所分配对象的全排列即可!222所以有(1)C6C4C23×P=9033P3(2)1233CCC×P=3606533411(3)C6C2C13×P=9023P2结论:一般地,如果把n个不同的元素分配给k个不同的对象,并且每个不同的对象可接受的元素个数没

7、有限制,那么实际上是先分组后排列的问题,结果为分组方案数乘以不同对象数的全排列。解不定向分配题的一般原则是:先分组后排列!数学讲义上第95页排列组合本章作业第4题属于不定向分配问题(需要先分组,再分配,其中分组为不平均分组)结果为1233CCC×P=360,故选B。6533第5题属于定向分配问题,所以为123CCC=60,故选D。653第6题属于不定向分配问题(需要先分组,再分配,其中分组为平均222分组)结果为C6C4C23×P=90,故选C。33P3第28题也属于不定向分配问题,同第6题,结果为444C12C8C43444×P=CCC,故选A。331284P

8、3元素种类(1)元素相同

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。