分组与分配问题

《分组与分配问题》由会员分享，可在线阅读，更多相关《分组与分配问题（10页珍藏版）》请在金锄头文库上搜索。

1、分组与分配问题(整理他人所得)将 n 个不同元素按照某些条件分成 k 组，称为分组问题。分组问题有完全均 分、全非均分和部分均分三种情况。将 n 个不同元素按照某些条件分配给 k 个不同的对象，称为分配问题。分配 问题有分为定向分配和不定向分配两种情况。分组问题和分配问题是有区别的，前者组与组之间只要元素个数相同是不区 分的；而后者即使两组元素个数相同，但因对象不同，仍然是可区分的。对于后 者必须先分组后排列。二、分组问题例 1、六本不同的书，分为三组，求在下列条件下各有多少种不同的分组方法？(1) 每组2 本(均分三堆)；(2)一组1 本，一组2 本，一组3 本；(3)一组4 本，另外两组各

2、1 本；分析：(1) 每组2 本(均分三堆)；分组与顺序无关，是组合问题。可分三步，应是C2 X C2 x C2种方法，但是这里642出现了重复。不妨把6本不同的书标记为A, B，C, D, E, F,若第一步取了 AB,第二步取了 CD,第三步取了 EF,记这种分法为(AB, CD, EF),那么C2 x C2 x C2642种分法中包含着(AB, EF, CD),(CD, AB, EF),(CD, EF , AB),(EF, CD ,AB),(EF, AB , CD),共A；种情况，而这A；种情况仅是AB, CD, EF的顺 序不同，因此只能作为一种分法，应该除序，所以正确的分组数是：C2

3、xC2xC26 4=15(种)。A3（2） 一组1 本，一组2 本，一组3 本；分组方法是C6 X C5 X C3，还要不要除以A3呢？我们发现，由于每组的书的本 6533数是不一样的，因此不会出现相同的分法，即共有C6XC5XC3=60（种）分法。或653C 2 XC 3X C1 或C 3X C1X C 2 或 C 3X C 2 X C1或 C 2X C1X C 3641632631643（3） 一组 4 本，另外两组各1 本；分组方法是X C2 X C1，有没有重复的分法？我们发现，其中两组的书的本6 2 1 数都是一本，因此这两组有了顺序，而与四本书的那一组，由于书的本数不一样C4 XC

4、1XC1C1XC1XC4不可能重复。所以实际分法是亠工 1=15 （种），或亠无 4=15 （种）。22 小结：分组问题属于组合问题，一般与顺序无关，常见的分组问题有：1）完全均分的分组：每组元素个数相等，不管它们的顺序如何，都是一种情况，应该除序，即除以相等组数的阶乘；一般地，k m个不同的元素分成k组,Cm X Cm XX Cm每组m个，则不同的分法种数为：4 予 -k（2）全非均分的分组：各组元素个数均不等，无需考虑重复现象；一般地 把n个不同元素分成k组，每组分别有m ,m ,m ,m个，且m ,m ,m ,m互123 k123 k不相等，m + m + m + m二n，则不同分法种数

5、为：123kCm1 X Cm2 X Cm3XX Cmknn m1 n_（m1 +m2）mk（3）部分均分的分组：部分组元素个数相等，应除以部分相等组数的阶乘般地，把n个不同元素分成k组，每组分别有m1，m m3, 役个,且m + m + m + + m二n，如果m ,m ,m , m中有且仅有i个相等，则不同123k123kCm1 X Cm2X Cm3X X的分法种数为：nn mn (m + m )mAi三、分配问题1、定向分配问题例 2、六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1) 甲 2 本、乙 2 本、丙 2 本；(2) 甲 1 本、乙 2 本、丙 3

6、 本；(3) 甲 4 本、乙 1 本、丙 1 本； 分析：由于分配给三人，每人分几本是一定的，这是分配问题中的定向分配问 题，由分步计数原理不难解出：(1) C 2 - C 2 - C 2 = 90 (种)642(2) C1 - C2 - C3 = 60(种)，或 C2 - C3 - C1 或 C3 - C1 - C2 或 C3 - C2 - C16536 4 1 6 3 2631(3) C4 - C1 - C1 = 30(种)，或 C1 - C1 - C4 或 C1 - C4 - Ci6216 5 4 6 51小结：定向分配问题可用分步计数原理计算。2、不定向分配问题例 3、六本不同的书，分

7、给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1) 每人2 本；(2) 一人 1 本，一人 2 本，一人 3 本；(3) 一人 4 本、一人 1 本、一人 1 本；分析：此组题属于分配中的不定向分配问题，是分配问题中比较困难的问题 由于分配给三人，同一本书给不同的人是不同的分法，所以是排列问题。实际上 可看作“分为三组，再将这三组分给甲、乙、丙三人”，因此只要将分组方法数再 乘以A3C1 X C2 X C3 X A3 = 360 (种)，或 C2 X C3 X C1 X A3 或 C3 X C1 X C2 X A3 653364136323即可。(A33可理解为三人分别有3种、2

8、种、1种选择法)、C 2 X C 2 X C 2人 心丄(1) 42 X A3 = 90(种)A333(3)小结：或 C3 X C2 X C1 X A36313C4XC1XC16 2 1A23W 丿，只A222不定向分配问题的解决办法是先分组后分配。C1XC1XC4C1XC4XC1XA；= 90(种)或 6 A24XA；或 HLXA；2例 4、12 支笔按 3：3：2：2：2 分给 A、B、C、D、E 五个人有多少种不同的分法？分析：问题可转化为先分组后分配。C 3 X C 3 X C 2 X C 2 X C 2先分组：分组法数有29A xa 423A55。后分配：将这五组（即五个不同元素）分

9、配给五个人（不同对象），分配方法数有C3 XC3XC2XC2XC2根据分步计数原理共有丄 9Axa 4 厶X A5种不同的分法。23例5、四个不同的小球放入编号为1， 2， 3， 4 的四个盒子中，恰有一个空盒 的放法有多少种？分析：恰有一个空盒，则另外三个盒子中小球数分别为1，1，2。于是问题可 转化为先分组后分配。先分组：四个不同的小球分为三组，两组各1个，另一组2 个，分组方法数C1XC1XC2432_有A2。2后分配：将这三组（即三个不同元素）分配给四个小盒（不同对象），分配方法数 有 A43 。C1XC1XC2根据分步计数原理共有亠云 L X今=1442例 6、有甲、乙、丙三项任务，

10、甲需 2 人承担，乙、丙各需 1 人承担，从 10人中 4 人承担这三项任务，不同的选派法有多少种？分析：问题可转化为先分组后分配。先分组：第一步从10人中选4人，选法有C咋，第二步分为三组，其中两组C1 XC1XC2C1XC1XC2A210A222 后分配：第一步分配甲任务，分配法只有 1 种，第二步分配乙、丙任务，分各1人，另一组2人，分组方法数有亠V ，共有C0 乂亠飞2厶；C1XC1XC2根据分步计数原理共有CoX亠比 X A； =2520种不同的选派法。配法有 A22 。A22例 7、设集合 A=1， 2， 3， 4， B=6， 7， 8， A 为定义域， B 为值域，则从 集合 A

11、 到集合 B 的不同的函数有多少个？分析：由于集合A为定义域，B为值域，即集合A、B中的每个元素都有“归宿”，而集合 B 的每个元素接受集合 A 中对应的元素的数目不限，所以问题可转化为先分组后分配。C1XC1XC2共有3种。先分组：集合 A 中 4 个元素分为三组，各组的元素数目分别为 1、 1、 2，则A22后分配：将这三组（看作三个不同元素）分配给B中的三个不同元素，分配方法C1XC1XC2根据分步计数原理共有亠V L X A； = 36个不同的函数。数有 A33 种。A22例 8、六本不同的书，分给甲、乙、丙三人，每人至少一本，有多少种分法？分析：六本书和甲、乙、丙三人都有“归宿”，即

12、书要分完，人不能空手。因C 2 X C 2 X C 2 先分组：六本书怎么分为三组呢？有三类分法：每组2本，有 一42 =此，先分组，后分配。A3315种；三组分别有1本、2本、3本，有C1 x C2 x C3 =60种；两组各1本，另一653C4 X Cl X Cl y组4本，有6 A；1 = 15种。所以根据加法原理，分组法有15+60+15=90种。2后分配：将这三组（即三个不同元素）分配给三个人（不同对象），分配方法数有 A3 - 6（种）。根据分步计数原理共有90 x 6 = 540种不同的分法。四、元素相同问题的等效转化隔板分割法例9、5 本相同的书全部分给3 个人，每人至少1 本

13、，有多少种分法？ 分析：5 本相同的书没有差别，可把它们排成一排，相邻两书之间形成4个空 隙，在4个空隙中选2个空隙，每个空隙插入1 个隔板，可把5 本相同的书分成3 部分，对应地分给3 个人，每一种插板方法对应一种分法。因为两个隔板无顺序 所以共有c ；种分法。4例10、5 本相同的书分给 3 个人，有多少种分法?分析1：把5 本相同的书排成一排，相邻两书之间有4个空隙及两端有2个空 隙，在这 6 个空隙位置插 2 个隔板，这样第 2 个人至少能分到 1 本，为了让第 2 个人可能分到 0 本，我们在这 6 个空隙位置上再增加一个位置，形成7 个位置 2 个隔板进行分割，所以共有C7种分法。

14、分析 2：以第 2 个人为标准，问题可分为两类，第一类：第 2 人至少分到 1 本，相当于在4个空隙位置及两端共6个空隙位置插2个隔板，有C-2种插种法；6第一类：第2个人分到0本，在上述的6个空隙位置同时插2个隔板，有C6种插6法；于是共有Cf + C6种。66下列问题用隔板分割法如何解释？有待高人帮助。 例11、3本相同的书全部分给5 个人，每人至多1 本，有多少种分法？分析：从5人中选3人来分书，因为分给的书相同，所以无顺序，有C ；种分 法。例 12、3 本相同的书全部分给 5 个人，有多少种分法？分析：问题可分为三类，第一类：把3本相同的书分给1 人，可从5人中选 1人，有C5种；第二类：3本相同的书分给2人,可从5人中选2人，有A2种（先 选人，后分配）；第三类：3本相同的书分给3人，可从5人中选3人，有C种； 共有 C1 + C2 A 2 + C3 = 3555 25。最后，相同元素分配给相同对象的问题很简单，这里不再赘述。如 5 个相同 的小球放入2个相同的盒子里，有0+5， 1+4， 2+3三种分法。