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

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

2、组 4 本，另外两组各 1 本；分析：(1) 每组 2 本（均分三堆）；642642分组与顺序无关，是组合问题。可分三步，应是c 2 c 2 c 2 种方法，但是这里出现了重复。不妨把 6 本不同的书标记为 a，b，c，d，e，f，若第一步取了 ab， 第二步取了 cd，第三步取了 ef，记这种分法为（ab，cd，ef），那么c 2 c 2 c 2种分法中包含着（ab，ef，cd），（cd，ab，ef），（cd，ef ，ab），（ef，cd ，ab），（ef，ab ，cd ），共 a3 种情况，而这 a3 种情况仅是 ab，cd，ef33的顺序不同，因此只能作为一种分法，应该除序，所以正确的分

3、组数是：c 2 c 2 c 2a3 642 =15(种)。37(2) 一组 1 本，一组 2 本，一组 3 本；分组方法是c1 c 2 c3 ，还要不要除以 a3 呢？我们发现，由于每组的书的本6533653数是不一样的，因此不会出现相同的分法，即共有c1 c 2 c3 =60(种) 分法。或c 2 c3 c1 或c3 c1 c 2 或c3 c 2 c1 或c 2 c1 c3641632631643(3) 一组 4 本，另外两组各 1 本；621分组方法是c 4 c1 c1 ，有没有重复的分法？我们发现，其中两组的书的本数都是一本，因此这两组有了顺序，而与四本书的那一组，由于书的本数不一样，c

4、 4 c1 c1a2不可能重复。所以实际分法是 621 = 152c1 c1 c 4a2(种)，或 654 = 152(种)。小结：分组问题属于组合问题，一般与顺序无关，常见的分组问题有：（1） 完全均分的分组：每组元素个数相等，不管它们的顺序如何，都是一种情况，应该除序，即除以相等组数的阶乘；一般地，k m 个不同的元素分成 k 组，cm cm cmkm每组 m 个，则不同的分法种数为：(k -1)mmak k（2） 全非均分的分组：各组元素个数均不等，无需考虑重复现象；一般地， 把 n 个不同元素分成 k 组，每组分别有m1 , m2 , m3 ,mk 个，且m1 , m2 , m3 ,m

5、k 互不相等， m1 + m2 + m3 + + mk= n ，则不同分法种数为：c cm1m2nn- m1m3 cn- (m1 +m2 ) cmkmk（3） 部分均分的分组：部分组元素个数相等，应除以部分相等组数的阶乘； 一般地，把 n 个不同元素分成 k 组，每组分别有m1 , m2 , m3 ,mk 个，且 m1 + m2 + m3 + + mk= n ，如果 m1 , m2 , m3 ,mk 中有且仅有 i 个相等，则不同cm1 cm2 cm3 cmk的分法种数为： nn- m1n- (m1 +m2 )mk ai i三、分配问题、定向分配问题例 2、六本不同的书，分给甲、乙、丙三人，求

6、在下列条件下各有多少种不同的分配方法？(1) 甲 2 本、乙 2 本、丙 2 本；(2) 甲 1 本、乙 2 本、丙 3 本；(3) 甲 4 本、乙 1 本、丙 1 本；分析：由于分配给三人，每人分几本是一定的，这是分配问题中的定向分配问题，由分步计数原理不难解出：642（） c 2 c 2 c 2 = 90 (种)（） c1 c 2 c3 = 60 (种)，或c 2 c3 c1 或c3 c1 c 2 或c3 c 2 c1653641632631（） c 4 c1 c1 = 30 (种)，或c1 c1 c 4 或c1 c 4 c1621654651小结：定向分配问题可用分步计数原理计算。、不定

7、向分配问题例 3、六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1) 每人 2 本；(2) 一人 1 本，一人 2 本，一人 3 本；(3) 一人 4 本、一人 1 本、一人 1 本；分析：此组题属于分配中的不定向分配问题，是分配问题中比较困难的问题。由于分配给三人，同一本书给不同的人是不同的分法，所以是排列问题。实际上可看作“分为三组，再将这三组分给甲、乙、丙三人”，因此只要将分组方法数再乘以 a3 即可。（ a3 可理解为三人分别有 3 种、2 种、1 种选择法）33c 2 c 2 c 2（） 642 a3 = 90 (种)a333（） c1 c 2 c3 a

8、3 = 360 (种)，或c 2 c3 c1 a3 或c3 c1 c 2 a36533641363236313或c3 c 2 c1 a3c 4 c1 c1c1 c1 c 4c1 c 4 c1（） 621 a3 = 90 (种)，或 654 a3 或 651 a3aaa232323222小结：不定向分配问题的解决办法是先分组后分配。例 4、12 支笔按 3：3：2：2：2 分给 a、b、c、d、e 五个人有多少种不同的分法？分析：问题可转化为先分组后分配。c3 c3 c 2 c 2 c 2先分组：分组法数有 129642 23a2 a35后分配：将这五组(即五个不同元素)分配给五个人(不同对象)

9、，分配方法数有 a5 。c3 c3 c 2 c 2 c 2根据分步计数原理共有 129642 a5 种不同的分法。23a2 a35例 5、四个不同的小球放入编号为 1，2，3，4 的四个盒子中，恰有一个空盒的放法有多少种？分析：恰有一个空盒，则另外三个盒子中小球数分别为 1，1，2。于是问题可转化为先分组后分配。先分组：四个不同的小球分为三组，两组各 1 个，另一组 2 个，分组方法数有 432 c1 c1 c 2a2。24后分配：将这三组(即三个不同元素)分配给四个小盒(不同对象)，分配方法数有 a3。c1 c1 c 2根据分步计数原理共有 432 a3 = 144a242例 6、有甲、乙、

10、丙三项任务，甲需 2 人承担，乙、丙各需 1 人承担，从 10人中 4 人承担这三项任务，不同的选派法有多少种？ 分析：问题可转化为先分组后分配。10先分组：第一步从 10 人中选 4 人，选法有c 4 ，第二步分为三组，其中两组c1 c1 c 2c1 c1 c 2各 1 人，另一组 2 人，分组方法数有 432 ，共有c 4 432 ；aa210222后分配：第一步分配甲任务，分配法只有 1 种，第二步分配乙、丙任务，分2配法有 a2 。根据分步计数原理共有c 4c1 c1 c 2 432 a2= 2520 种不同的选派法。a10222例 7、设集合 a=1，2，3，4，b=6，7，8，a

11、为定义域，b 为值域，则从集合 a 到集合 b 的不同的函数有多少个？分析：由于集合 a 为定义域，b 为值域，即集合 a、b 中的每个元素都有“归宿”，而集合 b 的每个元素接受集合 a 中对应的元素的数目不限，所以问题可转化为先分组后分配。先分组：集合 a 中 4 个元素分为三组，各组的元素数目分别为 1、1、2，则 432 c1 c1 c 2a共有2种。2后分配：将这三组(看作三个不同元素)分配给 b 中的三个不同元素，分配方法3数有 a3 种。c1 c1 c 2根据分步计数原理共有 432 a3 = 36 个不同的函数。a232例 8、六本不同的书，分给甲、乙、丙三人，每人至少一本，有

12、多少种分法？分析：六本书和甲、乙、丙三人都有“归宿”，即书要分完，人不能空手。因此，先分组，后分配。c 2 c 2 c 2a3先分组：六本书怎么分为三组呢？有三类分法：每组 2 本，有 642 15 种 ；3653三组分别有 1 本、2 本、3 本，有 c1 c 2 c3 60 种；两组各 1 本，另一组 4c 4 c1 c1a2本，有 621 = 15 种。所以根据加法原理，分组法有 15+60+15=90 种。2后分配：将这三组(即三个不同元素)分配给三个人(不同对象)，分配方法数有3a3 = 6 (种)。根据分步计数原理共有90 6 = 540 种不同的分法。四、元素相同问题的等效转化隔

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

14、，我们在这 6 个空隙位置上再增加一个位置，形成 7 个位置 2 个隔板进行分割，所以共有c 2 种分法。66分析 2：以第 2 个人为标准，问题可分为两类，第一类：第 2 人至少分到 1 本， 相当于在 4 个空隙位置及两端共 6 个空隙位置插 2 个隔板，有c 2 种插种法；第一类：第 2 个人分到 0 本，在上述的 6 个空隙位置同时插 2 个隔板，有c1 种插法；于是共有c 2 + c1 种。66下列问题用隔板分割法如何解释？有待高人帮助。例 11、3 本相同的书全部分给 5 个人，每人至多 1 本，有多少种分法？5分析：从 5 人中选 3 人来分书，因为分给的书相同，所以无顺序，有c

15、3 种分法。例 12、3 本相同的书全部分给 5 个人，有多少种分法？分析：问题可分为三类，第一类：把 3 本相同的书分给 1 人，可从 5 人中选 1 人，有c1 种；第二类：3 本相同的书分给 2 人，可从 5 人中选 2 人，有c 2 a2 种（先选5525人，后分配）；第三类：3 本相同的书分给 3 人，可从 5 人中选 3 人，有c3 种；共有5525c1 + c 2 a2 + c3 = 35 。最后，相同元素分配给相同对象的问题很简单，这里不再赘述。如 5 个相同的小球放入 2 个相同的盒子里，有 0+5，1+4，2+3 三种分法。“”“”at the end, xiao bian

16、 gives you a passage. minand once said, people who learn to learn are very happy people. in every wonderful life, learning is an eternal theme. as a professional clerical and teaching position, i understand the importance of continuous learning, life is diligent, nothing can be gained, only continuous learning can achieve better self. only by constantly learning and mastering the latest relevant knowledge, can employees