几类经典排列组合问题

一、小球放盒子问题（分组问题）（ 1 ）6 个不同的小球放到6 个不同的盒子里。解析：分步乘法计数原理，每个小球都有六种放法答案： 66。（ 2 ）6 个不同的小球放到6 个不同的盒子里，要求每个盒子只能放一个小球。解析：思路一：分步乘法计数原理，第一个小球有6 种放法第二个小球有5 种放法第六个小球有1 种放法即 6*5*4*3*2*1 ；思路二：将小球按顺序摆放后，与不同的盒子相对应即可，即a6 6 。答案： 720 。（ 3 ）6 个不同的小球平均放到3 个相同的盒子里。解析：平均分组的问题因为盒子相同， 相当于把小球等分成三堆，设想 6 个小球编号为abcdef ， 首先从 6 个球中选出2 个，为 c2 6 ；然后从剩下的4 个球中选出2 个，为 c2 4 ；最后剩下2 个球，为c2 2 ；但是： c2 6 取出 ab 球、 c2 4 取出 cd 球、剩 ef 球； c2 6 取出 ab 球、 c2 4 取出 ef 球、剩 cd 球； c2 6 取出 cd 球、 c2 4 取出 ab 球、剩 ef 球； c2 6 取出 cd 球、 c2 4 取出 ef 球、剩 ab 球； c2 6 取出 ef 球、 c2 4 取出 ab 球、剩 cd 球； c2 6 取出 ef 球、 c2 4 取出 cd 球、剩 ab 球；得到的结果是一样的，故按照c2 6c24c22 组合完成后还应除去a3 3 ，答案： c2 6c2 4c2 2/a3 3（ 4 ）6 个不同的小球平均放到3 个不同的盒子里。解析：平均分组后再分配的问题平均分组得到的结果为c2 6c2 4c2 2/a3 3，分完组后三堆小球还要放到不同的盒子里，即再进行一个a3 3 的排列答案： c2 6c2 4c2 2（ 5 ）6 个不同的小球按1、2 、3 的数量，分别放到3 个相同的盒子里。解析：非平均分组的问题因为盒子相同，相当于把小球分成数量不等的三堆，首先从 6 个球中选出1 个，为 c1 6 ；然后从剩下的5 个球中选出2 个，为 c2 5 ；最后剩下3 个球，为c3 3 ；注意：因为这个问题是非平均分组，故不存在（3）中出现的重复的情况， 因此 c1 6c2 5c3 3即为最后结果，不需要再除以a3 3答案： c1 6c2 5c3 3（ 6 ）6 个不同的小球按1、2 、3 的数量，分别放到3 个不同的盒子里。解析：非平均分组再分配的问题非平均分组得到的结果为c1 6c2 5c3 3/a3 3 ，分完组后三堆小球还要放到不同的盒子里，即再进行一个a3 3 的排列答案： c1 6c2 5c3 3a3 3（ 7 ）6 个不同的小球按1、1 、1、 3 的数量，分别放到4 个相同的盒子里。解析：部分平均分组的问题分成的四堆中，有三堆数量一样，设想6 个小球编号为abcdef ，首先从 6 个球中选出3 个，为 c3 6 ；然后从剩下的3 个球中选出1 个，为 c1 3 ； 再从剩下的2 个球中选出1 个 ， 为 c1 2 ； 最后剩下1 个球，为c1 1 ；但是： c3 6 取出 abc 球、 c1 3 取出 d 球、 c1 2 取出 e 球、剩 f 球； c3 6 取出 abc 球、 c1 3 取出 d 球、 c1 2 取出 f 球、剩 e 球； c3 6 取出 abc 球、 c1 3 取出 e 球、 c1 2 取出 d 球、剩 f 球；c3 6 取出 abc 球、 c1 3 取出 e 球、 c1 2 取出 f 球、剩 d 球； c3 6 取出 abc 球、 c1 3 取出 f 球、 c1 2 取出 d 球、剩 e 球； c3 6 取出 abc 球、 c1 3 取出 f 球、 c1 2 取出 e 球、剩 d 球； 得到的结果是一样的，故按照 c3 6c1 3c1 2c1 1组合完成后还应除去 a3 3 ，答案： c3 6c1 3c1 2c1 1/a3 3（ 8 ）6 个不同的小球按1、1 、1、 3 的数量，分别放到4 个不同的盒子里。解析：部分平均分组再分配的问题部分平均分组得到的结果为c3 6c1 3c1 2c1 1/a3 3，分完组后四堆小球还要放到不同的盒子里，即再进行一个a4 4 的排列答案： (c3 6c1 3c1 2c1 1/a3 3)a4 4（ 9 ）6 个不同的小球按1、1 、2、 2 的数量，分别放到4 个相同的盒子里。解析：部分平均分组再分配的问题答案： c2 6c2 4c1 2/（ a2 2a2 2 ）（ 10） 6 个不同的小球按1、 1、2 、2 的数量，分别放到4 个不同的盒子里。解析：部分平均分组再分配的问题答案： c2 6c2 4c1 2/（a2 2a2 2 ） a4 4（ 11） 6 个不同的小球放到5 个不同的盒子里，要求每个盒子至少放一个。解析：分类讨论分组再分配的问题，首先应该确定小球个数的分配方案，5 个盒子 6 个球，满足每盒至少一个，那么有且只有一个盒子放2 个，其他盒子放一个； 即小球按照2 、1 、1、1、1 的数量， 分别放到5 个不同的盒子中。答案：（ c2 6c1 4c1 3c1 2c1 1/a4 4） a6 6（ 12） 6 个不同的小球放到3 个不同的盒子里，要求每个盒子至少放一个。解析：分类讨论分组再分配的问题，首先应该确定小球个数的分配方案：1 1 4 ，部分平均分组再分配的问题：（ c1 6c1 5c4 4/a2 2)a3 31 2 3 ，非平均分组再分配的问题的问题：c1 6c2 5c3 3a3 32 2 2 ，完全平均分组再分配的问题：c2 6c2 4c2 2答案：（ c1 6c1 5c4 4/a2 2)a3 3+c1 6c2 5c3 3a3 3+c2 6c2 4c2 2（ 13） 6 个相同的小球放到3 个不同的盒子里，要求每个盒子至少放一个。解析：思路一：首先应该确定小球个数的分配方案，再分类讨论：1 1 4 ，小球相同小盒不同，只需选出一个盒子装4 个小球： c131 2 3 ，3 堆不同数量的小球，排序后往3 个不同的盒子里装：a332 2 2 ，每个盒子装2 个小球，只有一种方案：1思路二：隔板法相当于在 6 个小球之间放2 个板儿第一个板儿左侧的球放第一个盒子里两个板儿中间的球放第二个盒子里 第二个板儿右侧的球放第三个盒子里答案： c1 3+a3 3+1（ 14） 6 个不同的小球放到3 个相同的盒子里，要求每个盒子至少放一个。解析：分类讨论分组的问题，首先应该确定小球个数的分配方案：1 1 4 ，部分平均分组的问题：c1 6c1 5c4 4/a2 21 2 3 ，非平均分组的问题：c1 6c2 5c3 32 2 2 ，平均分组的问题：c2 6c2 4c2 2/a3 3答案： c1 6c1 5c4 4/a2 2+c1 6c2 5c3 3+c2 6c2 4c2 2/a3 3（ 15） 6 个相同的小球放到3 个相同的盒子里，要求每个盒子至少放一个。解析：首先应该确定小球个数的分配方案：1 1 41 2 32 2 2因为盒子没有区别，随便放，则小球的分配方案就是最后的方案答案： 3二、排列的捆绑法（ 1 ）6 个座位坐6 个人，要求甲乙丙3 个人必须相邻；解析：将甲乙丙三个人捆绑为一个元素，与另外三个人进行排列a44 ，然后对甲乙丙松绑 a3 3 。人人人甲乙丙答案： a4 4a3 3（ 2 ）6 个座位坐甲乙丙3 个人，要求3 个人必须相邻；解析：将甲乙丙三个人捆绑为一个元素，与三个空位进行排列a14 ，然后对甲乙丙松绑 a3 3 。空位空位空位甲乙丙答案： a1 4a3 3（ 3 ）6 个座位坐3 个人，要求3 个空位相邻；解析：将三个空位捆绑为一个元素，与三个人进行排列a4 4 。人人人空位空位空位注意：空位不用进行松绑。答案： a4 4三、排列的插空法（ 1 ）6 个座位坐6 个人，要求甲乙丙3 个人不相邻；解析：先排另外的三个人a3 3 ，再将甲乙丙进行插空排列a3 4 （c3 4a3 3 ） 。人人人答案： a3 3a3 4（ 2 ）6 个座位坐甲乙丙3 个人，要求这3 个人都不相邻；解析：只需将空座位摆上，甲乙丙进行插空排列a3 4 即可空位空位空位答案： a3 4（ 3 ）6 个座位坐3 个人，要求这3 个空位都不相邻； 解析：先排三个人a3 3 ，再将空位进行插空c3 4人人人注意：空位插空时只选不排，因此不是a3 4答案： a3 3c3 4四、捆绑法和插空法相结合（ 1 ）6 个座位坐6 个人，甲乙相邻，丙与甲乙都不相邻；解析：先排三个人a3 3 ，甲乙整体捆绑后和丙进行插空a2 4 ，再将甲乙松绑a2 2人人人答案： a3 3a2 4a2 2（ 2 ）6 个座位坐3 个人，要求甲乙相邻，丙与甲乙都不相邻；解析：需将空座位摆上，甲乙整体捆绑后和丙进行插空a2 4 ，再将甲乙松绑a2 2空位空位空位答案： a2 4a2 2（ 3 ）6 个座位坐3 个人，要求两个空位相邻，另一个空位不相邻； 解析：先排三个人a3 3 ，再将空位进行插空a2 4人人人注意：空位不用松绑答案： a3 3a2 4五、两类人和多面手的问题（ 1 ）11 个人中 5 人会唱， 6 人会跳，从中选出6 个人去参加晚会。解析：选出去6 个人没有任何限制，从11 个人中任意选择即可c6 11=c0 5c6 6+c1 5c5 6+c2 5c4 6+c3 5c3 6+c4 5c2 6+c5 5c1 6答案： c6 11（ 2 ）11 个人中 5 人会唱， 6 人会跳，从中选出6 个人去参加晚会，会唱和会跳的都不少于两个人。解析：分类讨论，确定会唱和会跳的人数的可能情况2 人 唱 4 人跳3 人 唱 3 人跳4 人唱 2 人跳c2 5c4 6+c3 5c3 6+c4 5c2 6答案： c2 5c4 6+c3 5c3 6+c4 5c2 6（ 3 ）11 个人中 4 人会唱， 5 人会跳，还有2 个既会唱又会跳，从中选出3 个会唱 3 个会跳的去参加晚会。解析：有多面手参与，分类讨论没有多面手参与的情况：c3 4c3 5有一个多面手参与的情况：先用c1 2 选出被选中的多面手， 多面手唱： c1 2c2 4c3 5多面手跳： c1 2c3 4c2 5有两个多面手参与的情况两个多面手都唱：c1 4c3 5两个多面手都跳：c3 4c1 5多面手一个唱一个跳：c2 4c2 5a2 2答案： c3 4c3 5 + （ c1 2c2 4c3 5+c1 2c3 4c2 5） +（ c1 4c3 5+c3 4c1 5+c2 4c2 5a2 2 ）（ 4 ）将 8 名医护人员（ 3 医生、 5 护士）分配到甲乙两所医院，有多少种方案？解析：思路一：每个人都有两种分配方法，用分步乘法计数原理：28思路二：用分组的思想：c08+c18+c28+c38+c48+c58+c68+c78+c8 8c0 8代表将0个人分配到医院甲，8 个人分配到医院乙；c1 8代表将1个人分配到医院甲，7 个人分配到医院乙；c2 8代表将2个人分配到医院甲，6 个人分配到医院乙；c3 8代表将3个人分配到医院甲，5 个人分配到医院乙；c4 8代表将4个人分配到医院甲，4 个人分配到医院乙；c5 8代表将5个人分配到医院甲，3 个人分配到医院乙；c6 8代表将6个人分配到医院甲，2 个人分配到医院乙；c7 8代表将7个人分配到医院甲，1 个人分配到医院乙；c8 8代表将8个人分配到医院甲，0 个人分配到医院乙；注意：连接思路一和思路二的桥梁正是二项式定理，而思路而又能拆解成如下形式，想一想为什么。28=（ 1+1 ）8 =c0 8+c1 8+c2 8+c3 8+c4 8+c5 8+c6 8+c7 8+c8 8。c0 8=c0 3c0 5；c1 8=c0 3c1 5+c1 3c0 5；c2 8=c0 3c2 5+c1 3c1 5+c2 3c0 5；c3 8=c0 3c3 5+c1 3c2 5+c2 3c1 5+c3 3c0 5 ； c4 8=c0 3c4 5+c1 3c3 5+c2 3c2 5+c3 3c1 5 ； c5 8=c0 3c5 5+c1 3c4 5+c2 3c3 5+c3 3c2 5 ；c6 8=c1 3c5 5+c2 3c4 5+c3 3c3 5；c7 8=c2 3c5 5+c3 3c4 5；c8 8=c3 3c5 5。答案： 28六、隔板法（ 1 ）6 本相同的书放到4 个不同的盒子中，每个盒子至少放一本书解析：先把6 本书并排成一排，它们之间有5 个空，在5 个空中选出3 个空放 3个板。 6 本书自动被隔成了四组，对应着四个盒子放入即可。注意：经典隔板法的条件是：对相同元素进行分组