例谈排列组合中的分组分配问题

《例谈排列组合中的分组分配问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、例谈排列组合中的分组分配问题湖北省咸宁市通城县第二高级中学何国雄一、提山分组与分配问题，澄清概念将n个不同元素按照某些条件分成k组，称为分组问题。n个不同元素按照某些条件分配给k个不同的对象，称为分配问题，分定向分配和不定向分配两种。二、分组问题常见形式及处理方法1.编号分组：(1)相同元素编号分组“编号分组”的意思是：即使分岀来两个或多个组中元素的个数相同,仍然看成不同的组例题1:10个相同的小球，放入5个不同的盒子里面，每个盒子至少要放一个球。问有几种放法？方法(隔板法)：10个相同小球排成一行，中间有9个空，将4块隔板，插入从这9个空中任意选取的4个空,就得到

2、5组小球，再放入5个不同的盒子，有.种分组方法。(2)不同元素编号分组分成两种情况：(i)非均匀编号分组(每组元素个数不同)例题2:10个人分成三组，各组人数分别为2、3、5,去参加不同(在这里体现“编号分组”)劳动，问有几种安排方法？方法：分步选人，分别选各组人数，然后要乘以组数的全排列。有.种(ii)均匀编号分组(包括部分均匀、全部均匀)例题3:10个人分成三组，各组人数分别为2、2、6,去参加不同劳动，问有几种安排方法？方法：分步选人，分别选各组人数。但是，由于有两个组人数相同，而选人时又是分步选人的（即冇顺序在里面），所以必然会造成重复。比如：甲乙、丙丁和丙

3、丁、甲乙是一种情况，我们却多算了。要除以元素相同的2个组的组数的全排列.，选人完之后要放进编好号码的组里面，所以乘以总组数的全排列.，即有.种。1.不编号分组：与编号分组不同的是，在不编号分组中，各个组元素的个数成为了区别不同组的唯一标志，换言之，只要冇两个或者多个组冇相14个数的元素，它们就被视为相同的组。在这里，由于组已经没有编号了，如果要放进组里面的元素再不可区分，那问题就变得没什么意义，而且很简单了。比如：三个相同的球，放入两个相同的盒子里面，只有一种放法，那就是其中一个盒子放一个球，另外那个盒子放剩下的那两个球。所以用列举法就可以了。在这里主要讨论不冋元素

4、的情况。（1）不同元素，不编号不均匀分组。例题4:10个人分成三组，各组人数分别为2、3、5,去参加相同（在这里体现“不编号分组”）劳动，问有几种安排方法？方法：和“不同元素，编号不均匀分组”相比，不必乘以组数的全排列，因为三个组参加的是相同的劳动（这里“相同”的言下之意是：劳动内容相同,又是同吋去的，如果不同吋，还要当作编号分组）有.种（2）不同元素不编号均匀分组（部分均匀、全部均匀）例题5:10个人分成三组，各组人数分别为2、2、6,去参加相冋劳动，问有几种安排方法？方法：要除以相同元素个数的那几个组的组数的全排列.，但是不必乘以总组数的全排列。有.三分配问题常

5、见形式及处理方法：1定向分配问题例6六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1)甲两本、乙两本、丙两本.(2)甲一本、乙两本、丙三本.(3)甲四本、乙一本、丙一本.分析：由于分配给三人，每人分几本是一定的，属分配问题中的定向分配问题，由分步计数原理，第一步分给甲，第二步分给乙，第三步分给丙，则有：2、不定向分配问题例7六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1)每人两本(2)一人一本、一人两本、一人三本(3)一人四本、一人一本、一人一本分析：此组题属于分配中的不定向分配问题，是该类题中比较困难的

6、问题。由于分配给三人，相同的书给不同的人是不同的分法，所以是排列问题。实际上可看作“分为三组，再将这三组分给甲、乙、丙三人”，因此将分组方法数再乘以.=6，即结论2.—般地，如果把不同的元素分配给几个不同对象，并每个不同对象可接受的元素个数没有限制，那么实际上是先分组后排列的问题，即分组方案数乘以不同对象数的全排列数。解不定向分配题的一般原则：先分组后排列。变式训练2:六本不同的书，分给甲、乙、丙三人，每人至少一本，冇多少种分法？分析：六本书和甲、乙、丙三人都有“归宿”，即书要分完，人不能空手。因此，考虑先分组，后排列。先分组，六本书怎么分为三组呢？有三类分法：(1

7、＞每组两本；(2＞分别为一本、二本、三本；(3)两组各一本，另一组四本。由以上变式训练1的求解可知这三类分组方法数，根据加法原理，分组法共是15+60+15=90（种）。再考虑排列，即再乘以.。所以一共有540种不同的分法。