分组分配问题(上课用)PPT课件

1、2021/7/2312021/7/232一、一、 提出分组与分配问题，澄清模糊概念提出分组与分配问题，澄清模糊概念n个不同元素按照某些条件分配给k个不同的对象，称为分配问题分配问题，分定向分配和不定向分配两种问题；将n个不同元素按照某些条件分成k组，称为分组问题.分组问题有不平均分组、平均分组、和部分平均分组三种情况。分组问题和分配问题是有区别的，前者组与组之间只要元素个数相同是不区分的；而后者即使2组元素个数相同，但因对象不同，仍然是可区分的.对于后者必须先分组后排列。2021/7/2331 1 把把abcdabcd分成平均两组分成平均两组ababcdcdacacbdbdadadbcbc有有

2、_多少种分法？多少种分法？C4 42 2C2 22 2A2 22 23cdcdbdbdbcbcadadacacabab这两个在分组时只能算一个这两个在分组时只能算一个记住记住： 平均分成的组，不管平均分成的组，不管它们的顺序如何，都它们的顺序如何，都是一种情况，所以分是一种情况，所以分组后要除以组后要除以m!，其，其中中m表示组数表示组数。引旧育新引旧育新2021/7/2341、平均分组问题平均分组问题：n个不同元素平均分成个不同元素平均分成m组，每组，每组组k个元素，则分组的方法个元素，则分组的方法:例例1.有两本不同的书，平均分成两组有几种不同分法？有两本不同的书，平均分成两组有几种不同分

3、法？ 有三本不同的书，平均分成三组有几种不同分法？有三本不同的书，平均分成三组有几种不同分法？ 有四本不同的书，平均分成两组有几种不同分法？有四本不同的书，平均分成两组有几种不同分法？ 有六本不同的书，平均分成两组有几种不同分法？有六本不同的书，平均分成两组有几种不同分法？结论结论:n个不同元素平均分成个不同元素平均分成m组，每组组，每组k个元素，则分组的方法为个元素，则分组的方法为:2kkkknn knkkmmC CCCA平均分组平均分组2021/7/235二、基本的分组问题二、基本的分组问题 例1 六本不同的书，分为三组，求在下列条件下各有多少种不同的分配方法？ (1)每组两本. (2)一

4、组一本，一组二本，一组三本. (3)一组四本，另外两组各一本.22264233115( )C C CA123653(2)60C C C41162122315( )C C CA2021/7/236 通过以上三个小题的分析，我们可以得出分组问题的一般方法： 结论结论1： 一般地，一般地，n个不同的元素分成个不同的元素分成p组，组，各组内元素数目分别为各组内元素数目分别为m，m，m，其中其中k组内元素数目相等，那么分组方法数组内元素数目相等，那么分组方法数是是321112ppmmmmnn mn mmmkkC CCCA2021/7/237三、基本的分配的问题三、基本的分配的问题(一一)定向分配问题定向

5、分配问题例2 六本不同的书，分给甲、乙、丙三人求在下列条件下各有多少种不同的分配方法？（1）甲两本、乙两本、丙两本.（2）甲一本、乙两本、丙三本.（3）甲四本、乙一本、丙一本. 分析：由于分配给三人，每人分几本是一定的,属分配问题中的定向分配问题，由分布计数原理不难解出：222642190( )C C C123653(2)60C C C411621330( )C C C2021/7/238(二二)不定向分配问题不定向分配问题例3六本不同的书，分给甲、乙、丙三人，求在下列条件下各有多少种不同的分配方法？(1) 每人两本.(2) 一人一本、一人两本、一人三本.(3) 一人四本、一人一本、一人一本.

6、分析：此组题属于分配中的不定向分配问题，是该类题中比较困难的问题。由于分配给三人，同一本书给不同的人是不同的分法，所以是排列问题。实际上可看作“分为三组，再将这三组分给甲、乙、丙三人”，因此只要将分组方法数再乘以 ， 33A2223642333190( )C C CA2)ACC C4113621322390( )C C CAA2021/7/239结论结论2. 一般地，如果把不同的元素分配给几一般地，如果把不同的元素分配给几个不同对象，并且每个不同对象可接受的个不同对象，并且每个不同对象可接受的元素个数没有限制，那么实际上是先分组元素个数没有限制，那么实际上是先分组后排

7、列的问题，即分组方案数乘以不同对后排列的问题，即分组方案数乘以不同对象数的全排列数。象数的全排列数。 通过以上分析不难得出解不定向分配题的一般原则：先分组后排列先分组后排列。2021/7/2310例4 六本不同的书，分给甲、乙、丙三人，每人至少一本，有多少种分法？分析：六本书和甲、乙、丙三人都有“归宿”，即书要分完，人不能空手。因此，考虑先分组，后排列。先分组，六本书怎么分为三组呢？有三类分法(1)每组两本(2)分别为一本、二本、三本(3)两组各一本，另一组四本。所以根据加法原理，分组法是再考虑排列，即再乘以 。所以一共有540种不同的分法。 222411642621123653323290C

8、 C CC C CC C CAA33A2021/7/2311四、分配问题的变形问题四、分配问题的变形问题例5 四个不同的小球放入编号为1，2，3，4的四个盒子中，恰有一个空盒的放法有多少种？11243222C C CA1124323422144C C CAA分析：恰有一个空盒，则另外三个盒子中小球数分别为1，1，2。实际上可转化为先将四个不同的小球分为三组，两组各1个，另一组2个，分组方法有然后将这三组(即三个不同元素)分配给四个小盒(不同对象)中的3个的排列问题，即共有2021/7/23123 有六本不同的书分给甲、乙、丙三名同学，按下条有六本不同的书分给甲、乙、丙三名同学，按下条件，各有多

9、少种不同的分法？件，各有多少种不同的分法？（1）每人各得两本；）每人各得两本；（2）甲得一本，乙得两本，丙得三本；）甲得一本，乙得两本，丙得三本；（3）一人一本，一人两本，一人三本；）一人一本，一人两本，一人三本；（4）甲得四本，乙得一本，丙得一本；）甲得四本，乙得一本，丙得一本；（5）一人四本，另两人各一本）一人四本，另两人各一本(3)(4)(5)C5 52 2C3 33 3C6 61 1A3 33 3C5 52 2C3 33 3C6 61 1C2 21 1C1 11 1C6 64 4A3 31 1C2 21 1C1 11 1C6 64 4(2)C4 42 2C2 22 2C6 62 2(1)2021/7/2313二二. .元素相同元素相同问题隔板策略问题隔板策略例例3.3.有有1010个运动员名额，再分给个运动员名额，再分给7 7个班，每个班，每班至少一个班至少一个, ,有多少种分配方案？有多少种分配方案？ 解：因为解：因为1010个名额没有差别，把它们排成个名额没有差别，把它们排成一排。相邻名额之间形成个空隙。一排。相邻名额之间形成个空隙。在个空档中选个位置插个隔板，在个空档中选个位置插个隔板，可把名额分成份，对应地分给个可把名额分成份，对应地分给个班级，每一种插板方法对应一种分法班级，每一种插板方法对应