《排列组合中分组(分堆)与分配问题》由会员分享，可在线阅读，更多相关《排列组合中分组(分堆)与分配问题（5页珍藏版）》请在金锄头文库上搜索。
1、太奇太奇 MBAMBA 数学助教数学助教李瑞玲李瑞玲 一分组（分堆）与分配问题 将n个不同元素按照某些条件分配给k个不同的对象，称为分配问 题，又分为定向分配和不定向分配两种问题。 将n个不同元素按照某些条件分成k组，称为分组问题。分组问题 有不平均分组，平均分组，部分平均分组三情况。 分组问题和分配问题是有区别的， 前者组与组之间只要元素个数相 同是不区分的，而后者即使两组的元素个数相同，但因所要分配的对 象不同，仍然是可区分的。对于后者必须先分组后排列。 一基本的分组问题 例 1.六本不同的书，分为三组，求在下列条件下各有多少种不同 的分配方法？ （1）每组两本（均分三组）（平均分组问题）
2、 （2）一组一本，一组两本，一组三本（不平均分组问题） （3）一组四本，另外两组各一本（部分平均分组问题） 分析： （1）分组和顺序无关，是组合问题。分组数为90 2 2 2 4 2 6 =CCC, 而这90种分组方法实际上重复了 6 次。现把六本不同的书标上 6 , 5 , 4 , 3 , 2 , 1六个号码，先看一下这种情况： （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） 由于书是均匀分组的，三组的本数都一样，又与顺序无关，所以
3、这种 情况下这六种分法是同一种分法，于是可知重复了 6 次。以上的分组 实际上加入了组的顺序，同理其他情况也是如此，因此还应取消分组 的顺序，即除以 3 3 P,于是最后知分法为15 6 90 3 3 2 2 2 4 2 6 = P CCC . (2)先分组，分组方法是60 3 3 2 5 1 6 =CCC，那么还要不要除以 3 3 P?（很 关键的问题） 由于每组的书的本数是不一样的，因此不会出现相同的分法，即 共有60 3 3 2 5 1 6 =CCC。 （3） 先分组， 分组方法是30 1 1 1 2 4 6 =CCC， 这其中有没有重复的分法?(需 要好好考虑） 现还把六本不同的书标上
4、6 , 5 , 4 , 3 , 2 , 1六个号码，先看以下情况 1）先取四本分一组，剩下的两本，一本一组，情况如下 （1,2,3,4）56（1,2,3,4）65 2）先取一本分一组，再取四本分一组，剩余的一本为一组， 情 况如下 5（1,2,3，4）66（1,2,3,4） 5 3）先取一本分一组，再取一本为一组，剩下的四本为一组， 情 况如下 56（1,2,3,4）65（1,2,3,4） 由此可知每一种分法重复了 2 次，原因是其中两组的的书的本 数都是一本，这两组有了顺序，需要把分组的顺序取消掉，而四本的 那一组，由于书的本数不一样，不可重复，故最后的结果为 15 2 30 2 2 1 1
5、 1 2 4 6 = P CCC . 通过以上三个小题的分析，可以得出分组问题的一般结论如下： 一般地，将n个不同的元素分成p组，各组内元素个数分别为 p mmm, 21 ，其中k组内元素个数相等，那么分组方法数为 () k k m m m mmmn m mn m n P CCCC p p i i 121 2 1 1 + ，即选完元素后要除以元素相同 的总组数的全排列！ 三基本的分配问题 1.定向分配问题 例 2 六本不同的书，分给甲乙丙三人，求在下列条件下各有多少种 不同的分法？ （1）甲两本，乙两本，丙两本 （2）甲一本，乙两本，丙三本 （3）甲四本，乙一本，丙一本 分析：由于分配给三人，
6、每人分几本是一定的，属于分配问题中的定 向分配问题。由分步计数原理得 （1） 2 2 2 4 2 6 CCC=90(2)60 3 3 2 5 1 6 =CCC(3)30 1 1 1 2 4 6 =CCC 2.不定向分配问题 例 3.六本不同的书，分给甲乙丙三人，求在下列条件下各有多少种 不同的分法？ （1）每人两本 （2）一人一本，一人两本，一人三本 （3）一人四本，一人一本，一人一本 分析：此题属于分配中的不定向分配问题。由于分配给三人，同一本 书给不同的人是不同的分法，所以是排列问题。实际上可看作是“六 本不同的书分为三组，再将这三组分给甲乙丙三人” ，因此只要将元 素的分组的方法数再乘以
7、所分配对象的全排列即可！ 所以有（1）90 3 3 3 3 2 2 2 4 2 6 =P P CCC （2）360 3 3 3 3 2 5 1 6 =PCCC (3)90 3 3 2 2 1 1 1 2 4 6 =P P CCC 结论：一般地，如果把n个不同的元素分配给k个不同的对象，并且 每个不同的对象可接受的元素个数没有限制， 那么实际上是先分组后 排列的问题，结果为分组方案数乘以不同对象数的全排列。解不定向 分配题的一般原则是：先分组后排列！ 数学讲义上第 95 页排列组合本章作业 第 4 题 属于不定向分配问题（需要先分组，再分配，其中分组为不 平均分组）结果为360 3 3 3 3
8、2 5 1 6 =PCCC,故选B。 第 5 题属于定向分配问题，所以为60 3 3 2 5 1 6 =CCC,故选D。 第 6 题属于不定向分配问题（需要先分组，再分配，其中分组为平均 分组）结果为90 3 3 3 3 2 2 2 4 2 6 =P P CCC ，故选C。 第 28 题 也 属 于 不 定 向 分 配 问 题 ， 同 第 6 题 ， 结 果 为 4 4 4 8 4 12 3 3 3 3 4 4 4 8 4 12 CCCP P CCC =,故选A。 元素种类 （1） 元素相同（2）元素不同 1）分配对象相同2）分配对象不同1）分配对象相同2）分配对象不同 分组（分堆）问题隔板法
9、解决分组（分堆）问题可重复和不可重复 此时要依据每组的数量来区别 要依据每组的数量和元素特征来区别 可重复：投信，人进房间问题 不可重复：组合，排列问题 例：现有 6 个球，4 个盒子，每个盒子至少一个球，在下列各种情况下各有多少 种放法？ （1）球不同，盒子不同 （2）球不同，盒子相同 （3）球相同，盒子不同 （4）球相同，盒子相同 解： （1）属于组合，排列问题，需要先分组，再分配给不同的对象。 分组有两种分法：1）2211 2）3111 则有 3 3 1 1 1 2 1 3 3 6 2 2 1 1 1 2 2 4 2 6 P CCCC P CCCC +，最后结果为 4 4 3 3 1 1 1 2 1 3 3 6 2 2 1 1 1 2 2 4 2 6 P P CCCC P CCCC +. (2)由于分配对象相同，没有区别，所以实质上为分组问题。 分组有两种分法：1）2211 2）3111 则有 3 3 1 1 1 2 1 3 3 6 2 2 1 1 1 2 2 4 2 6 P CCCC P CCCC +，即为最后结果。 （3）球相同，即元素相同，但分配对象不同，又要求每个盒子至少一个球， 故 为隔板问题，需用隔板法来解决，即10 3 5 =C种。 （4）球相同，盒子相同，就有两种方法，即 2211 和 3111 这两 种方法。
