论文：排列组合中的分组分配问题

2012-02-15 10:15阅读：

http://blog.sina.cn/dpool/blog/u/1600688451

排列组合中的分组分配问题
关键词：分组均匀不均匀分配
n个不同元素按照某些条件分配给k个不同得对象，称为分配问题
排列组合应用题中的分配分组问题，是一类抽象难懂的问题，包含的类型也特别多主要有以下几种：均分无分配对象、均分有分配对象、非均分组无分配对象、非均分组有分配对象、部分均分无分配对象、部分均分有分配对象。很多同学在做这类题目的时候分不清楚到底是属于哪类的分组分配问题。下面主要从一些例题分析这些不同类型的分组分配问题，从而更好的辨别这些类型的问题。
例1、六本不同的书，分为三组，求在下列条件下各有多少种不同的分配方法？
(1)每组两本。
(2)甲、乙、丙三人，每人两本
(3)一组一本，一组二本，一组三本。
(4)甲、乙、丙三人，一人一本、一人两本、一人三本。
(5)一组四本，另外两组各一本。
(6)

pan >甲、乙、丙三人，一人四本、一人一本、一人一本。
分析：显然以上6个小题分别对应一种类型的分配问题。
（1）分组与顺序无关，是组合问题。分组数是

=90（种），这90种分组实际
上重复了6次。我们不妨把六本不同的书写上1、2、3、4、5、6六个号码，考察以下两种
分法：（1，2）（3，4）（5，6）与（3，4）（1，2）（5，6），由于书是均匀分组的，三组的本
数一样，又与顺序无关，所以这两种分法是同一种分法。以上的分组方法实际上加入了组的
顺序，因此还应取消分组的顺序，即除以组数的全排列数

，所以分法是

=15（种）。所以平均分组是无序的，各组合数相乘时产生了顺序，故应消序（除以平均组数的全排列）。
（2）“分为三组，再将这三组分给甲、乙、丙三人”，因此只要将分组方法数再乘以

，即

=90（种）
（3）先分组，方法是

，那么还要不要除以

？我们发现，由于每组的书的本数是不一样的，因此不会出现相同的分法，即共有

=60（种）分法。所以不平均分组是有序的，不需要消序。
（4）类似（2）可以得到

=360（种）。
（5）分组方法是

=30（种），那么其中有没有重复的分法呢？我们发现，其中两组的书的本数都是一本，因此这两组有了顺序，而与四本书的那一组，由于书的本数不一样，不可能重复。所以实际分法是

=15（种）。所以局部平均分组应局部消序。
（6）类似（2）可以得到

=90（种）
对于分配问题做到先分组，再分配
类似的问题比如：
例2、12本不同的书分给甲、乙、丙三人按下列条件，各有多少种不同的分法？
（1）一人三本，一人四本，一人五本；
（2）甲三本，乙四本，丙五本；
（3）甲两本，乙、丙各五本；
根据上面例题的分析容易得出答案：

（1）

（2）

（3）

下面再看几个分配问题的变形问题
例3、四个不同的小球放入编号为1，2，3，4的四个盒子中，恰有一个空盒的放法有多少种？
分析：恰有一个空盒，则另外三个盒子中小球数分别为1，1，2。实际上可转化为先将四个不同的小球分为三组，两组各1个，另一组2个，分组方法有

（种），然后将这三组（即三个不同元素）分配给四个小盒（不同对象）中的3个的排列问题，即共有

=144（种）。
例4、有甲、乙、丙三项任务，甲需2人承担，乙、丙各需1人承担，从10人中选派4人承担这三项任务，不同的选法有多少种？
分析：先考虑分组，即10人中选4人分为三组，其中两组各一人，另一组二人，共有

（种）分法。再考虑排列，甲任务需2人承担，因此2人的那个组只能承担甲任务，而一个人的两组既可承担乙任务又可承担丙任务，所以共有

=2520（种）不同的选法。
例5、设集合A={1，2，3，4}，B={6，7，8}，A为定义域，B为值域，则从集合A到集合B的不同的函数有多少个？
分析：由于集合A为定义域，B为值域，即集合A、B中的每个元素都有“归宿”，而
集合B的每个元素接受集合A中对应的元素的数目不限，所以此问题实际上还是分组后分
配的问题。先考虑分组，集合A中4个元素分为三组，各组的元素数目分别为1、1、2，则
共有

（种）分组方法。再考虑分配，即排列，再乘以

，所以共有

=36（个）不同的函数。
总之，掌握上述方法，就能顺利解决任何分配问题。而且，学会了分配问题，还能将一些其他的排列组合问题转化为分配问题来解决。

举报/Report

我的更多文章

下载客户端阅读体验更佳