排列组合中的分组分配问题

精心整理摆列组合中的分组分派问题分组分派问题是摆列组合教课中的一个要点和难点。某些摆列组合问题看似非分派问题，实质上可运用分派问题的方法来解决。一、提出分组与分派问题，澄清模糊观点n个不同元素依据某些条件分派给k个不同得对象，称为分派问题，分定向分派和不定向分派两种问题；将n个不同元素依据某些条件分红k组，称为分组问题.分组问题有不均匀分组、均匀分组、和部分均匀分组三种情况。分组问题和分派问题是有区其余，前者组与组之间只需元素个数同样是不划分的；尔后者即便2组元素个数同样，但因对象不同，仍旧是可划分的.关于后者一定先分组后摆列。二、基本的分组问题例1六本不同的书，分为三组，求在以下条件下各有多少种不同的分派方法？(1)每组两本.(2)一组一本，一组二本，一组三本.(3)一组四本，此外两组各一本.剖析：(1)分组与次序没关，是组合问题。分组数是222=90(种)，这90种分组实质上重复C6C4C2了6次。我们不如把六本不同的书写上1、2、3、4、5、6六个号码，观察以下两种分法：(1，2)(3，4)(5，6)与(3，4)(1，2)(5，6)，因为书是均匀分组的，三组的本数同样，又与次序没关，所以这两种分法是同一种分法。以上的分组方法实质上加入了组的次序，所以还应撤消分组的次序，即除以2223C6C4C2=15(种)。组数的全摆列数A3，所以分法是3A31233(2)先分组，方法是C6C5C3，那么还要不要除以A3？我们发现，因为每组的书的本数是不同样的，所以不会出现同样的分法，即共有123C6C5C3=60(种)分法。411此中两组的书的本(3)分组方法是C6C2C1=30(种)，那么此中有没有重复的分法呢？我们发现，数都是一本，所以这两组有了次序，而与四本书的那一组，因为书的本数不同样，不行能重复。所411以实质分法是C6C2C1=15(种)。2A2经过以上三个小题的剖析，我们能够得出分组问题的一般方法。结论1：一般地，n个不同的元素分红p组，各组内元素数量分别为m1，m2，，mp，其mm2mmpCmpCn1Cnm1Cnm1m2中k组内元素数量相等，那么分组方法数是k。Ak精心整理精心整理三、基本的分派的问题(一)定向分派问题例2六本不同的书，分给甲、乙、丙三人，求在以下条件下各有多少种不同的分派方法？甲两本、乙两本、丙两本.甲一本、乙两本、丙三本.甲四本、乙一本、丙一本.剖析：因为分派给三人，每人分几本是必定的,属分派问题中的定向分派问题，由散布计数原理不难解出：分别有222123411=30(种)。C6C4C2=90(种)，C6C5C3=60(种)，C6C2C1(二)不定向分派问题例3六本不同的书，分给甲、乙、丙三人，求在以下条件下各有多少种不同的分派方法？每人两本.(2)一人一本、一人两本、一人三本.(3)一人四本、一人一本、一人一本.剖析：此组题属于分派中的不定向分派问题，是该类题中比较困难的问题。因为分派给三人，同一本书给不同的人是不同的分法，所以是摆列问题。实质上可看作“分为三组，再将这三组分给2223，即C6C4C23=90(种)，甲、乙、丙三人”，所以只需将分组方法数再乘以A33A3A34111233=360(种)C6C2C13=90(种)。C6C5C3A32A3A2结论2.一般地，假如把不同的元素分派给几个不同对象，并且每个不同对象可接受的元素个数没有限制，那么其实是先分组后摆列的问题，即分组方案数乘以不同对象数的全摆列数。经过以上剖析不难得出解不定向分派题的一般原则：先分组后摆列。例4六本不同的书，分给甲、乙、丙三人，每人起码一本，有多少种分法？剖析：六本书和甲、乙、丙三人都有“归宿”，即书要分完，人不可以空手。所以，考虑先分组，后摆列。先分组，六本书怎么分为三组呢？有三类分法(1)每组两本(2)分别为一本、二本、三本(3)22212341121两组各一本，另一组四本。所以依据加法原理，分组法是64+C6C5C3+62=90(种)。再32A3A2考虑摆列，即再乘以A33。所以一共有540种不同的分法。四、分派问题的变形问题例5四个不同的小球放入编号为1，2，3，4的四个盒子中，恰有一个空盒的放法有多少种？剖析：恰有一个空盒，则此外三个盒子中小球数分别为1，1，2。实质上可转变为先将四个不1122同的小球分为三组，两组各1个，另一组2个，分组方法有43(种)，而后将这三组(即三个不2A2精心整理精心整理112同元素)分派给四个小盒(不同对象)中的3个的摆列问题，即共有C4C3C232A4=144(种)。A2例6有甲、乙、丙三项任务，甲需2人担当，乙、丙各需1人担当，从10人中选派4人担当这三项任务，不同的选法有多少种？1121098(种)剖析：先考虑分组，即10人中选4人分为三组，此中两组各一人，另一组二人，共有CC2CA2分法。再考虑摆列，甲任务需2人担当，所以2人的那个组只好担当甲任务，而一个人的两组既112可担当乙任务又可担当丙任务，所以共有10982CC2CA2=2520(种)不同的选法。A2例7设会合A={1，2，3，4}，B={6，7，8}，A为定义域，B为值域，则从会合A到会合B的不同的函数有多少个？剖析：因为会合A为定义域，B为值域，即会合A、B中的每个元素都有“归宿”，而会合B的每个元素接受会合A中对应的元素的数量不限，所以此问题实质上仍是分组后分派的问题。先112考虑分组，会合A中4个元素分为三组，各组的元素数量分别为1、1、2，则共有C4C3C2(种)分2A2112组方法。再考虑分派，即摆列，再乘以3，所以共有C4C3C23=36(个)不同的函数。A32A3A2总之，掌握上述两个结论，就能顺利解决任何分派问题。并