几类经典排列组合问题

一、小球放盒子问题（分组问题）（1）6个不同的小球放到6个不同的盒子里。解析：分步乘法计数原理，每个小球都有六种放法答案：66。（2）6个不同的小球放到6个不同的盒子里，要求每个盒子只能放一个小球。解析：思路一：分步乘法计数原理，第一个小球有6种放法第二个小球有5种放法……第六个小球有1种放法即6*5*4*3*2*1；思路二：将小球按顺序摆放后，与不同的盒子相对应即可，即A66。答案：720。（3）6个不同的小球平均放到3个相同的盒子里。解析：平均分组的问题因为盒子相同，相当于把小球等分成三堆，设想6个小球编号为ABCDEF，首先从6个球中选出2个，为C26；然后从剩下的4个球中选出2个，为C24；最后剩下2个球，为C22；但是：C26取出AB球、C24取出CD球、剩EF球；C26取出AB球、C24取出EF球、剩CD球；C26取出CD球、C24取出AB球、剩EF球；C26取出CD球、C24取出EF球、剩AB球；C26取出EF球、C24取出AB球、剩CD球；C26取出EF球、C24取出CD球、剩AB球；得到的结果是一样的，故按照C26C24C22组合完成后还应除去A33，答案：C26C24C22/A33（4）6个不同的小球平均放到3个不同的盒子里。解析：平均分组后再分配的问题平均分组得到的结果为C26C24C22/A33，分完组后三堆小球还要放到不同的盒子里，即再进行一个A33的排列答案：C26C24C22（5）6个不同的小球按1、2、3的数量，分别放到3个相同的盒子里。解析：非平均分组的问题因为盒子相同，相当于把小球分成数量不等的三堆，首先从6个球中选出1个，为C16；然后从剩下的5个球中选出2个，为C25；最后剩下3个球，为C33；注意：因为这个问题是非平均分组，故不存在（3）中出现的重复的情况，因此C16C25C33即为最后结果，不需要再除以A33答案：C16C25C33（6）6个不同的小球按1、2、3的数量，分别放到3个不同的盒子里。解析：非平均分组再分配的问题非平均分组得到的结果为C16C25C33/A33，分完组后三堆小球还要放到不同的盒子里，即再进行一个A33的排列答案：C16C25C33A33（7）6个不同的小球按1、1、1、3的数量，分别放到4个相同的盒子里。解析：部分平均分组的问题分成的四堆中，有三堆数量一样，设想6个小球编号为ABCDEF，首先从6个球中选出3个，为C36；然后从剩下的3个球中选出1个，为C13；再从剩下的2个球中选出1个，为C12；最后剩下1个球，为C11；但是：C36取出ABC球、C13取出D球、C12取出E球、剩F球；C36取出ABC球、C13取出D球、C12取出F球、剩E球；C36取出ABC球、C13取出E球、C12取出D球、剩F球；C36取出ABC球、C13取出E球、C12取出F球、剩D球；C36取出ABC球、C13取出F球、C12取出D球、剩E球；C36取出ABC球、C13取出F球、C12取出E球、剩D球；得到的结果是一样的，故按照C36C13C12C11组合完成后还应除去A33，答案：C36C13C12C11/A33（8）6个不同的小球按1、1、1、3的数量，分别放到4个不同的盒子里。解析：部分平均分组再分配的问题部分平均分组得到的结果为C36C13C12C11/A33，分完组后四堆小球还要放到不同的盒子里，即再进行一个A44的排列答案：(C36C13C12C11/A33)A44（9）6个不同的小球按1、1、2、2的数量，分别放到4个相同的盒子里。解析：部分平均分组再分配的问题答案：C26C24C12/（A22A22）（10）6个不同的小球按1、1、2、2的数量，分别放到4个不同的盒子里。解析：部分平均分组再分配的问题答案：[C26C24C12/（A22A22）]A44（11）6个不同的小球放到5个不同的盒子里，要求每个盒子至少放一个。解析：分类讨论分组再分配的问题，首先应该确定小球个数的分配方案，5个盒子6个球，满足每盒至少一个，那么有且只有一个盒子放2个，其他盒子放一个；即小球按照2、1、1、1、1的数量，分别放到5个不同的盒子中。答案：（C26C14C13C12C11/A44）A66（12）6个不同的小球放到3个不同的盒子里，要求每个盒子至少放一个。解析：分类讨论分组再分配的问题，首先应该确定小球个数的分配方案：114，部分平均分组再分配的问题：（C16C15C44/A22)A33123，非平均分组再分配的问题的问题：C16C25C33A33222，完全平均分组再分配的问题：C26C24C22答案：（C16C15C44/A22)A33+C16C25C33A33+C26C24C22（13）6个相同的小球放到3个不同的盒子里，要求每个盒子至少放一个。解析：思路一：首先应该确定小球个数的分配方案，再分类讨论：114，小球相同小盒不同，只需选出一个盒子装4个小球：C13123，3堆不同数量的小球，排序后往3个不同的盒子里装：A33222，每个盒子装2个小球，只有一种方案：1思路二：隔板法__________相当于在6个小球之间放2个板儿第一个板儿左侧的球放第一个盒子里两个板儿中间的球放第二个盒子里第二个板儿右侧的球放第三个盒子里答案：C13+A33+1（14）6个不同的小球放到3个相同的盒子里，要求每个盒子至少放一个。解析：分类讨论分组的问题，首先应该确定小球个数的分配方案：114，部分平均分组的问题：C16C15C44/A22123，非平均分组的问题：C16C25C33222，平均分组的问题：C26C24C22/A33答案：C16C15C44/A22+C16C25C33+C26C24C22/A33（15）6个相同的小球放到3个相同的盒子里，要求每个盒子至少放一个。解析：首先应该确定小球个数的分配方案：114123222因为盒子没有区别，随便放，则小球的分配方案就是最后的方案答案：3二、排列的捆绑法（1）6个座位坐6个人，要求甲乙丙3个人必须相邻；解析：将甲乙丙三个人捆绑为一个元素，与另外三个人进行排列A44，然后对甲乙丙松绑A33。答案：A44A33（2）6个座位坐甲乙丙3个人，要求3个人必须相邻；解析：将甲乙丙三个人捆绑为一个元素，与三个空位进行排列A14，然后对甲乙丙松绑A33。人甲乙丙人人空位甲乙丙空位空位答案：A14A33（3）6个座位坐3个人，要求3个空位相邻；解析：将三个空位捆绑为一个元素，与三个人进行排列A44。注意：空位不用进行松绑。答案：A44三、排列的插空法（1）6个座位坐6个人，要求甲乙丙3个人不相邻；解析：先排另外的三个人A33，再将甲乙丙进行插空排列A34（C34A33）。________________________________答案：A33A34（2）6个座位坐甲乙丙3个人，要求这3个人都不相邻；解析：只需将空座位摆上，甲乙丙进行插空排列A34即可________________________________答案：A34（3）6个座位坐3个人，要求这3个空位都不相邻；解析：先排三个人A33，再将空位进行插空C34________________________________注意：空位插空时只选不排，因此不是A34答案：A33C34四、捆绑法和插空法相结合（1）6个座位坐6个人，甲乙相邻，丙与甲乙都不相邻；解析：先排三个人A33，甲乙整体捆绑后和丙进行插空A24，再将甲乙松绑A22________________________________答案：A33A24A22（2）6个座位坐3个人，要求甲乙相邻，丙与甲乙都不相邻；解析：需将空座位摆上，甲乙整体捆绑后和丙进行插空A24，再将甲乙松绑A22________________________________答案：A24A22（3）6个座位坐3个人，要求两个空位相邻，另一个空位不相邻；空位空位空位人人人人人人空位空位空位人人人人人人空位空位空位解析：先排三个人A33，再将空位进行插空A24________________________________注意：空位不用松绑答案：A33A24五、两类人和多面手的问题（1）11个人中5人会唱，6人会跳，从中选出6个人去参加晚会。解析：选出去6个人没有任何限制，从11个人中任意选择即可C611=C05C66+C15C56+C25C46+C35C36+C45C26+C55C16答案：C611（2）11个人中5人会唱，6人会跳，从中选出6个人去参加晚会，会唱和会跳的都不少于两个人。解析：分类讨论，确定会唱和会跳的人数的可能情况2人唱4人跳3人唱3人跳4人唱2人跳C25C46+C35C36+C45C26答案：C25C46+C35C36+C45C26（3）11个人中4人会唱，5人会跳，还有2个既会唱又会跳，从中选出3个会唱3个会跳的去参加晚会。解析：有多面手参与，分类讨论没有多面手参与的情况：C34C35有一个多面手参与的情况：先用C12选出被选中的多面手，多面手唱：C12C24C35多面手跳：C12C34C25有两个多面手参与的情况两个多面手都唱：C14C35两个多面手都跳：C34C15多面手一个唱一个跳：C24C25A22答案：C34C35+（C12C24C35+C12C34C25）+（C14C35+C34C15+C24C25A22）（4）将8名医护人员（3医生、5护士）分配到甲乙两所医院，有多少种方案？解析：思路一：每个人都有两种分配方法，用分步乘法计数原理：28思路二：用分组的思想：C08+C18+C28+C38+C48+C58+C68+C78+C88C08代表将0个人分配到医院甲，8个人分配到医院乙；C18代表将1个人分配到医院甲，7个人分配到医院乙；C28代表将2个人分配到医院甲，6个人分配到医院乙；C38代表将3个人分配到医院甲，5个人分配到医院乙；C48代表将4个人分配到医院甲，4个人分配到医院乙；C58代表将5个人分配到医院甲，3个人分配到医院乙；C68代表将6个人分配到医院甲，2个人分配到医院乙；C78代表将7个人分配到医院甲，1个人分配到医院乙；C88代表将8个人分配到医院甲，0个人分配到医院乙；人人人注意：连接思路一和思路二的桥梁正是二项式定理，而思路而又能拆解成如下形式，想一想为什么。28=（1+1）8=C08+C18+C28+C38+C48+C58+C68+C78+C88。C08=C03C05；C18=C03C15+C13C05；C28=C03C25+C13C15+C23C05；C38=C03C35+C13C25+C23C15+C33C05；C48=C03C45+C13C35+C23C25+C33C15；C58=C03C55+C13C45+C23C35+C33C25；C68=C13C55+C23C45+C33C35；C78=C23C55+C33C45；C88=C33C55。答案：28六、隔板法（1）6本相同的书放到4个不同的盒子中，每个盒子至少放一本书解析：先把6本书并排成一排，它们之间有5个空，在5个空中选出3个空放3个板。6本书自动被隔成了四组，对应着四个盒子放入即可。注意：经典隔板法的条件是：对相同元素进行分组；每组至少含有一个元素。答案：C35（2）10本相同的书放到4个不同的盒子中，每个盒子至少放两本书解析：思路一：10本书拿出4本来，分别放到4个盒子中，就变成了问题（1）思路二：分类讨论，首先确定书的数量的分法2224C14选出一个盒子放4本书2332C24选出两个盒子放3本书答案：C35=C24+C14（3）X+Y+Z=10，X、Y、Z属于正整数（4）X+Y+Z=10，X、Y、Z属于正整数，且X≥2，Y≥2，Z≥2。（5）X+Y+Z=10，X、Y、Z属于非负整数