(完整版)分组与分配问题(整理他人所得)

1分组与分配问题（整理他人所得）一、分组与分配的概念将n个不同元素按照某些条件分成k组，称为分组问题。分组问题有完全均分、全非均分和部分均分三种情况。将n个不同元素按照某些条件分配给k个不同的对象，称为分配问题。分配问题有分为定向分配和不定向分配两种情况。分组问题和分配问题是有区别的，前者组与组之间只要元素个数相同是不区分的；而后者即使两组元素个数相同，但因对象不同，仍然是可区分的。对于后者必须先分组后排列。二、分组问题例1、六本不同的书，分为三组，求在下列条件下各有多少种不同的分组方法？(1)每组2本（均分三堆）；(2)一组1本，一组2本，一组3本；(3)一组4本，另外两组各1本；分析：(1)每组2本（均分三堆）；分组与顺序无关，是组合问题。可分三步，应是222642CCC种方法，但是这里出现了重复。不妨把6本不同的书标记为A，B，C，D，E，F，若第一步取了AB，第二步取了CD，第三步取了EF，记这种分法为（AB，CD，EF），那么222642CCC种分法中包含着（AB，EF，CD），（CD，AB，EF），（CD，EF，AB），（EF，CD，AB），（EF，AB，CD），共33A种情况，而这33A种情况仅是AB，CD，EF的顺序不同，因此只能作为一种分法，应该除序，所以正确的分组数是：22264233CCCA=15(种)。2(2)一组1本，一组2本，一组3本；分组方法是123653CCC，还要不要除以33A呢？我们发现，由于每组的书的本数是不一样的，因此不会出现相同的分法，即共有123653CCC=60(种)分法。或231641CCC或312632CCC或321631CCC或213643CCC(3)一组4本，另外两组各1本；分组方法是411621CCC，有没有重复的分法？我们发现，其中两组的书的本数都是一本，因此这两组有了顺序，而与四本书的那一组，由于书的本数不一样，不可能重复。所以实际分法是4116212215CCCA(种)，或1146542215CCCA(种)。小结：分组问题属于组合问题，一般与顺序无关，常见的分组问题有：（1）完全均分的分组：每组元素个数相等，不管它们的顺序如何，都是一种情况，应该除序，即除以相等组数的阶乘；一般地，km个不同的元素分成k组，每组m个，则不同的分法种数为：(1)mmmkmkmmkkCCCA（2）全非均分的分组：各组元素个数均不等，无需考虑重复现象；一般地，把n个不同元素分成k组，每组分别有123,,,kmmmm个，且123,,,kmmmm互不相等，123kmmmmn，则不同分法种数为：312112()kkmmmmnnmnmmmCCCC（3）部分均分的分组：部分组元素个数相等，应除以部分相等组数的阶乘；一般地，把n个不同元素分成k组，每组分别有123,,,kmmmm个，且123kmmmmn，如果123,,,kmmmm中有且仅有i个相等，则不同的分法种数为：312112()kkmmmmnnmnmmmiiCCCCA三、分配问题１、定向分配问题3例2、六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1)甲2本、乙2本、丙2本；(2)甲1本、乙2本、丙3本；(3)甲4本、乙1本、丙1本；分析：由于分配给三人，每人分几本是一定的，这是分配问题中的定向分配问题，由分步计数原理不难解出：（１）22264290CCC(种)（２）12365360CCC(种)，或231641CCC或312632CCC或321631CCC（３）41162130CCC(种)，或114654CCC或141651CCC小结：定向分配问题可用分步计数原理计算。２、不定向分配问题例3、六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1)每人2本；(2)一人1本，一人2本，一人3本；(3)一人4本、一人1本、一人1本；分析：此组题属于分配中的不定向分配问题，是分配问题中比较困难的问题。由于分配给三人，同一本书给不同的人是不同的分法，所以是排列问题。实际上可看作“分为三组，再将这三组分给甲、乙、丙三人”，因此只要将分组方法数再乘以33A即可。（33A可理解为三人分别有3种、2种、1种选择法）（１）222364233390CCCAA(种)（２）12336533360CCCA(种)，或23136413CCCA或31236323CCCA4或32136313CCCA（３）411362132290CCCAA(种)，或1143654322CCCAA或1413651322CCCAA小结：不定向分配问题的解决办法是先分组后分配。例4、12支笔按3：3：2：2：2分给A、B、C、D、E五个人有多少种不同的分法？分析：问题可转化为先分组后分配。先分组：分组法数有332221296422323CCCCCAA后分配：将这五组(即五个不同元素)分配给五个人(不同对象)，分配方法数有55A。根据分步计数原理共有33222512964252323CCCCCAAA种不同的分法。例5、四个不同的小球放入编号为1，2，3，4的四个盒子中，恰有一个空盒的放法有多少种？分析：恰有一个空盒，则另外三个盒子中小球数分别为1，1，2。于是问题可转化为先分组后分配。先分组：四个不同的小球分为三组，两组各1个，另一组2个，分组方法数有11243222CCCA。后分配：将这三组(即三个不同元素)分配给四个小盒(不同对象)，分配方法数有34A。根据分步计数原理共有1123432422144CCCAA例6、有甲、乙、丙三项任务，甲需2人承担，乙、丙各需1人承担，从10人中4人承担这三项任务，不同的选派法有多少种？5分析：问题可转化为先分组后分配。先分组：第一步从10人中选4人，选法有410C，第二步分为三组，其中两组各1人，另一组2人，分组方法数有11243222CCCA，共有11244321022CCCCA；后分配：第一步分配甲任务，分配法只有1种，第二步分配乙、丙任务，分配法有22A。根据分步计数原理共有11242432102222520CCCCAA种不同的选派法。例7、设集合A={1，2，3，4}，B={6，7，8}，A为定义域，B为值域，则从集合A到集合B的不同的函数有多少个？分析：由于集合A为定义域，B为值域，即集合A、B中的每个元素都有“归宿”，而集合B的每个元素接受集合A中对应的元素的数目不限，所以问题可转化为先分组后分配。先分组：集合A中4个元素分为三组，各组的元素数目分别为1、1、2，则共有11243222CCCA种。后分配：将这三组(看作三个不同元素)分配给B中的三个不同元素，分配方法数有33A种。根据分步计数原理共有112343232236CCCAA个不同的函数。例8、六本不同的书，分给甲、乙、丙三人，每人至少一本，有多少种分法？分析：六本书和甲、乙、丙三人都有“归宿”，即书要分完，人不能空手。因此，先分组，后分配。先分组：六本书怎么分为三组呢？有三类分法：每组2本，有22264233CCCA＝15种；三组分别有1本、2本、3本，有123653CCC＝60种；两组各1本，另一6组4本，有4116212215CCCA种。所以根据加法原理，分组法有15+60+15=90种。后分配：将这三组(即三个不同元素)分配给三个人(不同对象)，分配方法数有336A(种)。根据分步计数原理共有906540种不同的分法。四、元素相同问题的等效转化——隔板分割法例9、5本相同的书全部分给3个人，每人至少1本，有多少种分法？分析：5本相同的书没有差别，可把它们排成一排，相邻两书之间形成4个空隙，在4个空隙中选2个空隙，每个空隙插入1个隔板，可把5本相同的书分成3部分，对应地分给3个人，每一种插板方法对应一种分法。因为两个隔板无顺序，所以共有24C种分法。例10、5本相同的书分给3个人，有多少种分法?分析1：把5本相同的书排成一排，相邻两书之间有4个空隙及两端有2个空隙，在这6个空隙位置插2个隔板，这样第2个人至少能分到1本，为了让第2个人可能分到0本，我们在这6个空隙位置上再增加一个位置，形成7个位置2个隔板进行分割，所以共有27C种分法。分析2：以第2个人为标准，问题可分为两类，第一类：第2人至少分到1本，相当于在4个空隙位置及两端共6个空隙位置插2个隔板，有26C种插种法；第一类：第2个人分到0本，在上述的6个空隙位置同时插2个隔板，有16C种插法；于是共有26C+16C种。下列问题用隔板分割法如何解释？有待高人帮助。例11、3本相同的书全部分给5个人，每人至多1本，有多少种分法？分析：从5人中选3人来分书，因为分给的书相同，所以无顺序，有35C种分法。7例12、3本相同的书全部分给5个人，有多少种分法？分析：问题可分为三类，第一类：把3本相同的书分给1人，可从5人中选1人，有15C种；第二类：3本相同的书分给2人，可从5人中选2人，有2252CA种（先选人，后分配）；第三类：3本相同的书分给3人，可从5人中选3人，有35C种；共有1223552535CCAC。最后，相同元素分配给相同对象的问题很简单，这里不再赘述。如5个相同的小球放入2个相同的盒子里，有0+5，1+4，2+3三种分法。