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

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

2、组）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次。以上的分组 实际上加入

3、了组的顺序，同理其他情况也是如此，因此还应取消分组 的顺序，即除以P33,于是最后知分法为C6cp4c2=960=i5.先分组，分组方法是C；C；C3=6O，那么还要不要除以P；3? （很 关键的问题）由于每组的书的本数是不一样的，因此不会出现相同的分法，即共有 c6c；c； = 60。（3）先分组，分组方法是C；c2g甲两本，乙两本，丙两本 =30，这其中有没有重复的分法 ?（需 要好好考虑）现还把六本不同的书标上1,234,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次，原因是其中两组的的书的本 数都是一本，这两组有了顺序，需要把分组的顺序取消掉，而四本的 那一组，由于书的本数不一样，不可重复，故最后的结果为CQC； = 30 = 15P；2'通过以上三个小题的分析，可以得出分组问题的一般结论如下：一般地，将n个不同的元素分成p组，各组内元素个数分别为耳,口2,?, mp，其中k组内元素个数相等，那么分组方法数为C m1 C m2 ? C

5、 mi? C mpn n_mi ? n_ (mi +m2 +? +mi-1) mp(2) 人一本，一人两本，一人三本(3) 人四本，一人一本，一人一本 分析：此题属于分配中的不定向分配问题。由于分配给三人，同一本 书给不同的人是不同的分法，所以是排列问题。实际上可看作是“六本不同的书分为三组，再将这三组分给甲乙丙三人”，因此只要将元 素的分组的方法数再乘以所分配对象的全排列即可！所以有(1)P33XF33 = 90(2) C：c2c3 XF3甲四本，乙一本，丙一本分析：由于分配给三人，每人分几本是一定的，属于分配问题中的定 向分配问题。由分步计数原理得(1) C6* 1 2 3c2c|=90(

6、2) c6c；C；=60(3) C：c2c1 = 302. 不定向分配问题例3.六本不同的书，分给甲乙丙三人，求在下列条件下各有多少种 不同的分法？(1) 每人两本 = 360(3) X3 = 90结论：一般地，如果把n个不同的元素分配给k个不同的对象，并且 每个不同的对象可接受的元素个数没有限制，那么实际上是先分组后 排列的问题，结果为分组方案数乘以不同对象数的全排列。解不定向 分配题的一般原则是：先分组后排列！数学讲义上第95页排列组合本章作业 第4题 属于不定向分配问题(需要先分组，再分配，其中分组为不 平均分组)结果为C6C2C； XP33 = 360,故选B。第5题属于定向分配问题，

7、所以为C；C2C； = 6O,故选D。第6题属于不定向分配问题(需要先分组，再分配，其中分组为平均 分组)结果为 CC程XP33 = 90，故选C。第28题也属于不定向分配问题，同第6题，结果为C2評 XP33=G：C：C：,故选 A元素种类（1）元素相同（2）元素不同1分配对象相同 2）分配对象不同1）分配对象相同 2）分配对象不同分组（分堆）问题 隔板法解决分组（分堆）问题 可重复和不可重复此时要依据每组的数量来区别要依据每组的数量和元素特征来区别可重复：投信，人进房间问题 不可重复：组合，排列问题例：现有6个球，4个盒子，每个盒子至少一个球，在下列各种情况下各有多少 种放法？（1）球不同

8、，盒子不同（2）球不同，盒子相同（3）球相同，盒子不同（4）球相同，盒子相同解:（1）属于组合，排列问题，需要先分组，再分配给不同的对象。分组有两种分法:1）2 2 1 12）3 1 1 122113111?2 C2113111 ?则有 CeC4C2C1 +C6C3C2C1，最后结果为?CeC4C2C1 +C6C3C2C1?xp4.P2R3? P2P3 ?由于分配对象相同，没有区别，所以实质上为分组问题分组有两种分法：1）2 2 1 12）3 1 1 1C ?c ?c 1C1 c 3c1 c 1C1则有ggG2cl + ggGcl，即为最后结果。P22戌（3）球相同，即元素相同，但分配对象不同，又要求每个盒子至少一个球，故为隔板问题，需用隔板法来解决，即 c；=1o种。（4