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

分组与分配问题（整理他人所得）一、分组与分配的概念 将n个不同元素按照某些条件分成k组，称为分组问题。分组问题有完全均分、全非均分和部分均分三种情况。 将n个不同元素按照某些条件分配给k个不同的对象，称为分配问题。分配问题有分为定向分配和不定向分配两种情况。分组问题和分配问题是有区别的，前者组与组之间只要元素个数相同是不区分的；而后者即使两组元素个数相同，但因对象不同，仍然是可区分的。对于后者必须先分组后排列。二、分组问题例1、六本不同的书，分为三组，求在下列条件下各有多少种不同的分组方法？(1)每组2本（均分三堆）；(2)一组1本，一组2本，一组3本；(3)一组4本，另外两组各1本；分析：(1) 每组2本（均分三堆）；分组与顺序无关，是组合问题。可分三步，应是种方法，但是这里出现了重复。不妨把6本不同的书标记为A，B，C，D，E，F，若第一步取了AB，第二步取了CD，第三步取了EF，记这种分法为（AB，CD，EF），那么种分法中包含着（AB，EF，CD），（CD，AB，EF），（CD，EF ，AB），（EF，CD ，AB），（EF，AB ，CD ），共种情况，而这种情况仅是AB，CD，EF的顺序不同，因此只能作为一种分法，应该除序，所以正确的分组数是：=15(种)。(2) 一组1本，一组2本，一组3本；分组方法是，还要不要除以呢？我们发现，由于每组的书的本数是不一样的，因此不会出现相同的分法，即共有=60(种) 分法。或或或或(3) 一组4本，另外两组各1本；分组方法是，有没有重复的分法？我们发现，其中两组的书的本数都是一本，因此这两组有了顺序，而与四本书的那一组，由于书的本数不一样，不可能重复。所以实际分法是 (种)，或 (种)。小结：分组问题属于组合问题，一般与顺序无关，常见的分组问题有：（1）完全均分的分组：每组元素个数相等，不管它们的顺序如何，都是一种情况，应该除序，即除以相等组数的阶乘；一般地，k m个不同的元素分成k组，每组m个，则不同的分法种数为： （2）全非均分的分组：各组元素个数均不等，无需考虑重复现象；一般地，把n个不同元素分成k组，每组分别有个，且互不相等，则不同分法种数为： （3）部分均分的分组：部分组元素个数相等，应除以部分相等组数的阶乘；一般地，把n个不同元素分成k组，每组分别有个，且，如果中有且仅有i个相等，则不同的分法种数为：三、分配问题、定向分配问题例2、六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1) 甲2本、乙2本、丙2本；(2) 甲1本、乙2本、丙3本；(3) 甲4本、乙1本、丙1本； 分析：由于分配给三人，每人分几本是一定的，这是分配问题中的定向分配问题，由分步计数原理不难解出：（）(种)（）(种)，或或或（）(种)，或或小结：定向分配问题可用分步计数原理计算。、不定向分配问题例3、六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1) 每人2本；(2) 一人1本，一人2本，一人3本；(3) 一人4本、一人1本、一人1本；分析：此组题属于分配中的不定向分配问题，是分配问题中比较困难的问题。由于分配给三人，同一本书给不同的人是不同的分法，所以是排列问题。实际上可看作“分为三组，再将这三组分给甲、乙、丙三人”，因此只要将分组方法数再乘以即可。（可理解为三人分别有3种、2种、1种选择法）（）(种)（）(种)，或或 或（）(种)，或或小结：不定向分配问题的解决办法是先分组后分配。例4、12支笔按3：3：2：2：2分给A、B、C、D、E五个人有多少种不同的分法？分析：问题可转化为先分组后分配。先分组：分组法数有后分配：将这五组(即五个不同元素)分配给五个人(不同对象)，分配方法数有。根据分步计数原理共有种不同的分法。例5、四个不同的小球放入编号为1，2，3，4的四个盒子中，恰有一个空盒的放法有多少种？分析：恰有一个空盒，则另外三个盒子中小球数分别为1，1，2。于是问题可转化为先分组后分配。先分组：四个不同的小球分为三组，两组各1个，另一组2个，分组方法数有。后分配：将这三组(即三个不同元素)分配给四个小盒(不同对象)，分配方法数有。根据分步计数原理共有例6、有甲、乙、丙三项任务，甲需2人承担，乙、丙各需1人承担，从10人中4人承担这三项任务，不同的选派法有多少种？分析：问题可转化为先分组后分配。先分组：第一步从10人中选4人，选法有，第二步分为三组，其中两组各1人，另一组2人，分组方法数有，共有；后分配：第一步分配甲任务，分配法只有1种，第二步分配乙、丙任务，分配法有。根据分步计数原理共有种不同的选派法。例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，则共有种。后分配：将这三组(看作三个不同元素)分配给B中的三个不同元素，分配方法数有种。根据分步计数原理共有个不同的函数。例8、六本不同的书，分给甲、乙、丙三人，每人至少一本，有多少种分法？分析：六本书和甲、乙、丙三人都有“归宿”，即书要分完，人不能空手。因此，先分组，后分配。先分组：六本书怎么分为三组呢？有三类分法：每组2本，有15种；三组分别有1本、2本、3本，有60种；两组各1本，另一组4本，有种。所以根据加法原理，分组法有15+60+15=90种。后分配：将这三组(即三个不同元素)分配给三个人(不同对象)，分配方法数有(种)。根据分步计数原理共有种不同的分法。四、元素相同问题的等效转化隔板分割法例9、5本相同的书全部分给3个人，每人至少1本，有多少种分法？分析：5本相同的书没有差别，可把它们排成一排，相邻两书之间形成4个空隙，在4个空隙中选2个空隙，每个空隙插入1个隔板，可把5本相同的书分成3部分，对应地分给3个人，每一种插板方法对应一种分法。因为两个隔板无顺序，所以共有种分法。例10、5本相同的书分给3个人，有多少种分法?分析1：把5本相同的书排成一排，相邻两书之间有4个空隙及两端有2个空隙，在这6个空隙位置插2个隔板，这样第2个人至少能分到1本，为了让第2个人可能分到0本，我们在这6个空隙位置上再增加一个位置，形成7个位置2个隔板进行分割，所以共有种分法。分析2：以第2个人为标准，问题可分为两类，第一类：第2人至少分到1本，相当于在4个空隙位置及两端共6个空隙位置插2个隔板，有种插种法；第一类：第2个人分到0本，在上述的6个空隙位置同时插2个隔板，有种插法；于是共有+种。下列问题用隔板分割法如何解释？有待高人帮助。例11、3本相同的书全部分给5个人，每人至多1本，有多少种分法？分析：从5人中选3人来分书，因为分给的书相同，所以无顺序，有种分法。例12、3本相同的书全部分给5个人，有多少种分法？ 分析：问题可分为三类，第一类：把