计数原理与排列组合ppt课件

计数原理与排列组合 基本原理 组合 排列 排列数公式 组合数公式 应用问题 1 知识结构 一 复习回顾 2 分类记数原理 分步记数原理 3 排列与组合 4 解排列组合问题基本思路 排列组合问题 有序 无序 排列 组合 分类或分步 分类或分步 直接法 直接法 间接法 不易解 不易解 题型2可重复元素排列问题 例2 五名学生报名参加四项体育比赛 每人限报一项 报名方法的种数为多少 五名学生争夺四项比赛的冠军 冠军不并列 获得冠军的可能性有多少种 解答 报名的方法种数为4 4 4 4 4 45 种 获得冠军的可能情况有5 5 5 5 54 种 方法小节 解决 允许重复排列问题 常用 住店法 要注意区分两类元素 一类元素可以重复 另一类不能重复 把不能重复的元素看作 客 能重复的元素看作 店 再利用乘法原理直接求解 基础知识梳理 二 题型与方法 例3 如图 用5种不同的颜色给图中A B C D四个区域涂色 规定每个区域只涂一种颜色 相邻区域颜色不同 求有多少种不同的涂色方法 题型3涂色问题 解法一 分步法 如题图分四个步骤来完成涂色这件事需分为四步 第一步涂A区有5种涂法 第二步涂B有4种方法 第三步涂C有3种方法 第四步涂D有3种方法 还可以使用涂A的颜色 根据分步计数原理共有5 4 3 3 180种涂色方法 2011高考导航 解法二 分类法 完成涂色的方法分为两类 第一类 四个区域涂四种不同的颜色共有 120种涂法 第二类 四个区域涂三种不同的颜色 由于A D不相邻只能是A D两区域颜色一样 将A D看做一个区域 共 60种涂法 由分类计数原理知共有涂法120 60 180 种 方法总结 对涂色问题 有两种解法 法1是逐区图示法 注意不相邻可同色 法2根据用色多少分类法 题型4排列中的 相邻 不相邻问题 例4 a1 a2 a8共八个元素 分别计算满足下列条件的排列数 1 八个元素排成一排 且a1 a2 a3 a4四个元素排在一起 2 八个元素排成一排 且a1 a2 a3 a4四个元素互不相邻 3 八个元素排成一排 且a1 a2 a3 a4四个元素互不相邻 并且a5 a6 a7 a8也互不相邻 4 排成前后两排每排四个元素 解答 1 捆绑法 先将a1 a2 a3 a4四个元素看成一个元素与a5 a6 a7 a8排列一排 有种排法 再排a1 a2 a3 a4有不同排法 根据分步计数原理知满足条件的排列数为 2880 2 插空法 先排a5 a6 a7 a8四个元素排成一排 有种排法 再将元素a1 a2 a3 a4插入由a5 a6 a7 a8间隔及两端的五个位置中的四个 有种排法 根据分步计数原理知 满足条件的排列数为 2880 3 先排a5 a6 a7 a8 共有种排法 然后排a1 a2 a3 a4排在 或 中的 共有2种排法 根据分步计数原理共有 2 1152种排法 4 前排有种排法 后排有种排法 由分步计数原理知共有 8 种排法 方法总结 1 若某些元素必须相邻 常用捆绑法 即先把这几个相邻元素捆在一起看成一个元素 再与其他元素全排列 最后再考虑这几个相邻元素的顺序 2 若某些元素不相邻 常用插空法 即先将普通元素全排列 然后再从排就的每两个元素之间及两端选出若干个空挡插入这些特殊元素 3 前后排问题 直排法 变式44个男同学 3个女同学站成一排 1 3个女同学必须排在一起 有多少种不同的排法 2 任何两个女同学彼此不相邻 有多少种不同的排法 3 其中甲 乙两同学之间必须恰有3人 有多少种不同的排法 4 甲 乙两人相邻 但都不与丙相邻 有多少种不同的排法 5 女同学从左到右按高矮顺序排 有多少种不同的排法 3个女生身高互不相等 解答 1 3个女同学是特殊元素 我们先把她们排好 共有种排法 由于3个女同学必须排在一起 我们可视排好的女同学为一整体 再与男同学排队 这时是5个元素的全排列 应有种排法 由分步计数的原理 有 720种不同排法 2 先将男生排好 共有种排法 再在这4个男生的中间及两头的5个空档中插入3个女生有种方案 故符合条件的排法共有 1440种不同排法 3 甲 乙2人先排好 有种排法 再从余下5人中选3人排在甲 乙2人中间 有种排法 这时把已排好的5人视为一整体 与最后剩下的2人再排 又有种排法 这样总共有 720种不同排法 4 先排甲 乙和丙3人以外的其他4人 有种排法 由于甲 乙要相邻 故再把甲 乙排好 有种排法 最后把甲 乙排好的这个整体与丙分别插入原先排好的4人的空档中有