10信息学奥赛CSP-J数学课件-计数原理与排列组合（下）

《 CSP - J 初级组 算法 中 数学 》 Day10 - 计数原理与排列组合 (下 ) 课程大纲 else 处理条件不满足 排列与组合 真题演练 备战 CSP 初赛 排列与组合 排列 组合 n 个不同元素中取出 m个元素的一个组合 n 个不同元素中取出 m个元素并按一定顺序排成一列 捆绑法 例 1 -照相 （相邻问题捆绑处理） 有 6 个人排成一队照相，其中甲乙两人必须相邻，请问有多少种排法？ 方法一： 方法二： 捆绑法 例 2 -开会 (相邻问题捆绑处理，特殊情况优先考虑 ) 在某场新冠肺炎疫情视频会议中，甲、乙、丙、丁、戊五位疫情防控专家分别按 一定的顺序发言，其中甲必须排在前两位，丙、丁必须排在一起，则五位专家不 同的发言顺序共有多少种？ 甲 甲 甲在 1 时： 甲在 2 时 ： 第一只能放乙和戊，剩下两个位置 捆绑法 例 3 - 放小球 把 4 个不同的小球全部放入 3 个不同的盒子中，使每个盒子都不空的放法总数为？ 1 1 2 插空法 例 1 -考试 (不相邻就插空 ) 本次模拟考试结束后，班级要排一张语文、数学、英语、物理、化学、生物六科试卷讲 评顺序表，化学排在生物前面，数学与物理不相邻且都不排在最后，则不同的排表方法 共有多少种？ 分析 第一步： 先放化、生 , 再放语、英 第二步： 数 、 物插空 或 B A 捆绑法 例 2 排数字 只用 1,2,3,4 四个数字组成一个 5 位数，规定这四个数字必须同时使用，且同一数字不 能相邻出现，这样的五位数有多少个？ 分析 当重复为 1 的时候，先排列 2,3,4, 再放 1 其他数字同理，因此，最终结果为： 特殊优先 特殊元素，优先处理；特殊位置，优先考虑。 例 1 ： 六人站成一排，求： ⑴ 甲、乙既不在排头也不在排尾的排法数 ⑵ 甲不在排头，乙不在排尾，且甲乙不相邻的排法数 分析（ 1 ） × × 先排剩下的，再把甲乙插空 ,(甲乙还可以相邻 ) 4个位置选 2个放甲乙，剩下的全排列 特殊优先 例 1 ： 六人站成一排，求： ⑴ 甲、乙既不在排头也不在排尾的排法数 ⑵ 甲不在排头，乙不在排尾，且甲乙不相邻的排法数 第一类：甲在排尾，乙在排头 第二类：甲在排尾，乙不在排头，甲乙不相邻 第三类：乙在排头，甲不在排尾 第四类：甲不在排尾也不在排头，乙不在排头也不在排尾 分析（ 2 ） 乙 甲 捆绑与插空 例 ： 8 人排成一队 ⑴ 甲乙必须相邻 ⑵ 甲乙不相邻 ⑶ 甲乙必须相邻且与丙不相邻 ⑷ 甲乙必须相邻，丙丁必须相邻 CSP 真题 例 2 10 个三好学生名额分配到 7 个班级，每个班至少有一个名额，一共有多少种不同的 分配方案？ 1 1 1 1 1 1 1 十个名额，有 9个空，插入 6个板，会分成 7个区域，每个区域就是每个班的名额数。 CSP 真题 例 4 有五副不同颜色的手套（共 10 只手套，每副手套左右手各 1 只），一次性从中取 6 只手套， 请问 恰好 能配成两副手套的不同取法有（ ）种。 分析 ： 6 只手套，恰好配成 2 副，意味着从五副手套选两套，剩下的三套里面选两种，每种各选一只 抽屉原理 桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉 里面放不少于两个苹果。这一现象就是我们所说的“ 抽屉原理 ”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有 n+1 个元素放到 n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为 鸽巢原理。 1、把 98 个苹果放到 10 个抽屈里，无论怎么放，我们一定能找到一个含苹果最多的抽屉，它里面 至少有 ？ 个苹果。 10 2、 1000 只鸽子飞进 50 个巢，无论怎么飞，我们一定能找到一个含鸽子最多的巢，它里面至少有？ 只鸽子。 20 3、从 8个抽屉里拿出 17 个苹果，无论怎么拿，我们一定能拿到苹果最多的那个抽屉，从它里面至 少拿出 ?个苹果。 3 总结