2011高考数学总复习__计数原理与排列组合课件

计数原理与排列组合 2011201120112011高考导航高考导航高考导航高考导航 考纲解读考纲解读考纲解读考纲解读 1 理解分类加法计数原理和分步乘法计数原理 会 用两个原理分析和解决一些简单的实际问题 2 理解排列 组合的概念 3 能利用计数原理推导排列数公式 组合数公式 4 能解决简单的实际问题 2011201120112011高考导航高考导航高考导航高考导航 命题探究命题探究命题探究命题探究 1 计数原理内容考查比较稳定 试题难度起伏不 大 排列组合题目一般为选择 填空题 考查排列组合 的基础知识 思维能力 多数试题与教材习题的难度相 当 但也有个别题难度较大 2 考查热点为排列组合与两个计数原理结合命题 基 本 原 理 组合 排列排列数公式 组合数公式 应 用 问 题 1 知识结构 一 复习回顾 2 分类记数原理 分步记数原理 分步记数原理针对的是分步记数原理针对的是 分步分步 问题 各步方法相互问题 各步方法相互 依存 只有各步都完成才能依存 只有各步都完成才能 完成这件事 完成这件事 分类记数原理针对的是分类记数原理针对的是 分类分类 问题 其中各种方法问题 其中各种方法 相互独立 用其中任何一种相互独立 用其中任何一种 方法都可完成这件事 方法都可完成这件事 区别 完成一件事需要分成完成一件事需要分成n n n n个个 步骤 第一步有步骤 第一步有mmmm1 1 1 1种不同的种不同的 方法 第二步有方法 第二步有mmmm2 2 2 2种不同的种不同的 方法 方法 第 第n n n n步有步有mmmmn n n n种种 不同的方法 那么完成这件不同的方法 那么完成这件 事共事共N mN mN mN m1 1 1 1 mmmm2 2 2 2 mmmmn n n n 有种不同的方法有种不同的方法 完成一件事可以有完成一件事可以有n n类类 办法 在第一类中有办法 在第一类中有m m1 1种不种不 同的方法 在第二类中有同的方法 在第二类中有m m2 2 种不同的方法 种不同的方法 在第 在第 n n类办法中有类办法中有m mn n种不同的方种不同的方 法 那么完成这件事共法 那么完成这件事共N N m m1 1 m m2 2 m mn n有种不同的方有种不同的方 法 法 原理 分步记数原理分类记数原理 公式 看取出的两个元素互换位置是否为同一种方看取出的两个元素互换位置是否为同一种方 法 若不是 则是排列问题 若是 则是组合 法 若不是 则是排列问题 若是 则是组合 判定 与顺序无关与顺序有关区别 从从n n n n个个不同不同的元素中 的元素中 任取任取mmmm mmmm n n n n 个 个不不 同同的元素并成一组 的元素并成一组 叫做从叫做从n n n n个不同的元素个不同的元素 中取出中取出mmmm个不同的元个不同的元 素的一个素的一个组合组合 从从n n n n个个不同不同元素中 任取元素中 任取 m mm mm mm m n n n n 个个不同不同元素按元素按 照一定顺序排成一列 照一定顺序排成一列 叫做从叫做从n n n n个不同元素中取个不同元素中取 出出mmmm个不同元素的一个个不同元素的一个排排 列列 定义 组合排列 1 2 1 mnnnnA m n mn n 1 2 1 m mnnnnm n C mmn n 3 排列与组合 4 解排列组合问题基本思路 排列组合问题 有序 无序 排列 组合 分类或分步 分类或分步 直接法 直接法 间接法 不易解 不易解 5 解排列组合问题的常见方法 1 特殊元素 位置 优先安排 2 多个限定条件或含 至多 至少 问题 合理分 类合理分步 3 排列组合混合问题一般要先组合后排列 先整体 后局部 4 正难则反 等价转化 5 相邻问题 捆绑法 6 不相邻问题 插空法 7 定序问题 平均分组问题用除法 8 相同物品分配问题 名额分配问题用隔板法 9 数的大小排列问题 查字典法 10 可重复元素排列问题 住店法 基础知识梳理基础知识梳理基础知识梳理基础知识梳理 二 题型与方法 例例例例1 1 1 1 如如图 用图 用5 5 5 5种不同的颜色给图中种不同的颜色给图中A A A A B B B B C C C C D D D D四个区域涂色 规定每个区四个区域涂色 规定每个区 域只涂一种颜色 相邻区域颜色不域只涂一种颜色 相邻区域颜色不 同 求有多少种不同的涂色方法 同 求有多少种不同的涂色方法 题型1 涂色问题 解法一解法一 分步法 如题图分四个步骤来完成涂色这件事 分步法 如题图分四个步骤来完成涂色这件事 需分为四步 第一步涂需分为四步 第一步涂A A A A区有区有5 5 5 5种涂法 第二步涂种涂法 第二步涂B B B B有有4 4 4 4种种 方法 第三步涂方法 第三步涂C C C C有有3 3 3 3种方法 第四步涂种方法 第四步涂D D D D有有3 3 3 3种方法种方法 还可还可 以使用涂以使用涂A A A A的颜色的颜色 根据分步计数原理共有 根据分步计数原理共有5 5 5 5 4 4 4 4 3 3 3 3 3 3 3 3 180180180180种涂色方法 种涂色方法 解法二解法二 由于 由于A A A A B B B B C C C C两两相邻 因此三个区域的颜色两两相邻 因此三个区域的颜色 互不相同 共有互不相同 共有 60606060种涂法 又种涂法 又D D D D与与B B B B C C C C相邻 因此相邻 因此D D D D 有有3 3 3 3种涂法 由分步计数原理知共有种涂法 由分步计数原理知共有60606060 3 3 3 3 180180180180种涂法 种涂法 2011201120112011高考导航高考导航高考导航高考导航 解法三 分类法 完成涂色的方法分为两类 第一类 解法三 分类法 完成涂色的方法分为两类 第一类 四个区域涂四种不同的颜色共有四个区域涂四种不同的颜色共有 120120120120种涂法 种涂法 第二类 四个区域涂三种不同的颜色 由于第二类 四个区域涂三种不同的颜色 由于A A A A D D D D不不 相邻只能是相邻只能是A A A A D D D D两区域颜色一样 将两区域颜色一样 将A A A A D D D D看做一个区看做一个区 域 共域 共 60606060种涂法 种涂法 由分类计数原理知共有涂法由分类计数原理知共有涂法120120120120 60606060 180 180 180 180 种种 方法总结 方法总结 对涂色问题 有两种解法 法对涂色问题 有两种解法 法1 1 1 1是逐区图示法 注意不是逐区图示法 注意不 相邻可同色相邻可同色 法法2 2 2 2根据用色多少分类法根据用色多少分类法 变式变式1 1 1 1 如下图 一个地区分为如下图 一个地区分为5 5 5 5个行政区 现给地图着色 要个行政区 现给地图着色 要 求相邻区域不得使用同一颜色 现有求相邻区域不得使用同一颜色 现有4 4 4 4种颜色可供选种颜色可供选 择 则不同的着色方法共有择 则不同的着色方法共有 种 种 以数字作答以数字作答 答案 答案 答案 答案 72727272 题型2 可重复元素排列问题 例例例例2 2 2 2 若若A A A A a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4 B B B B b b b b1 1 1 1 b b b b2 2 2 2 b b b b3 3 3 3 试 试 问从问从A A A A到到B B B B可建立多少种可建立多少种 不同的映射 不同的映射 解答 解答 住店法住店法 完成建立一个从 完成建立一个从A A A A到到B B B B的映射需要分成的映射需要分成 四步 第一步 四步 第一步 a a a a1 1 1 1与与B B B B中唯一的元素对应有中唯一的元素对应有3 3 3 3种方法 第二种方法 第二 步 步 a a a a2 2 2 2与与B B B B中唯一的元素对应有中唯一的元素对应有3 3 3 3种方法 种方法 第三步 第三步 a a a a3 3 3 3与与B B B B 中唯一的元素对应有中唯一的元素对应有3 3 3 3种方法 种方法 第四步 第四步 a a a a4 4 4 4与与B B B B中唯一的中唯一的 元素对应有元素对应有3 3 3 3种方法 由分步计数原理 可建立从种方法 由分步计数原理 可建立从A A A A到到B B B B的的 映射共有映射共有34343434 81 81 81 81 个个 方法小节 方法小节 解决解决 允许重复排列问题允许重复排列问题 常用常用 住店法住店法 要注意 要注意 区分两类元素 区分两类元素 一类元素可以重复 另一类不能重一类元素可以重复 另一类不能重 复 把不能重复的元素看作复 把不能重复的元素看作 客客 能重复的元素看 能重复的元素看 作作 店店 再利用乘法原理直接求解 再利用乘法原理直接求解 变式变式变式变式2 2 2 2 1 1 1 1 五五名学生报名参加四项体育比赛 每人限报一项 报名学生报名参加四项体育比赛 每人限报一项 报 名方法的种数为多名方法的种数为多 少 五名学生争夺四项比赛的冠军少 五名学生争夺四项比赛的冠军 冠军不并列冠军不并列 获得冠军的可能性有多少种 获得冠军的可能性有多少种 解答 解答 解答 解答 报报名的方法种数为名的方法种数为4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 45 5 5 5 种种 获得冠获得冠军的可能情况有军的可能情况有5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 54 4 4 4 种种 2 2 2 2 将将3 3 3 3种作物种植在如下图的种作物种植在如下图的5 5 5 5块试验田里 每块块试验田里 每块 种植一种作物且相邻的试验田不能种植同一作种植一种作物且相邻的试验田不能种植同一作 物 不同的种植方法共有物 不同的种植方法共有 种 种 以数字作答以数字作答 解析 解析 解析 解析 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 42 42 42 42 答案 答案 答案 答案 42424242 题型3 在与不在的排序问题 常见的排列问题有三种 常见的排列问题有三种 1 1 1 1 排队 排队 2 2 2 2 排数 排数 3 3 3 3 排课程排课程 表 对于表 对于 在在 或者或者 不在不在 的排列问题的计算方法主要的排列问题的计算方法主要 是 是 1 1 1 1 位置优先法 位置优先法 2 2 2 2 元素优先法 元素优先法 3 3 3 3 间接计算法 间接计算法 例例3 3 3 3 甲 乙 丙 丁四名同学排成一排 分别计甲 乙 丙 丁四名同学排成一排 分别计 算满足下列条件的排法种数 算满足下列条件的排法种数 1 1 1 1 甲不在排头 乙不在排尾 甲不在排头 乙不在排尾 2 2 2 2 甲不在第一位 乙不在第二位 丙不在第三位 甲不在第一位 乙不在第二位 丙不在第三位 丁不在第四位 丁不在第四位 3 3 3 3 甲一定在乙的右端甲一定在乙的右端 可以不邻可以不邻 解答 解答 1 1 1 1 直接法 分为两类 第一类甲排在排尾共直接法 分为两类 第一类甲排在排尾共 有有 6 6 6 6种排法 第二类 若甲在排尾共有种排法 第二类 若甲在排尾共有 8 8 8 8种排法 由分类计数原理知共有 种排法 由分类计数原理知共有 14 14 14 14 种种 也可间接计算 也可间接计算 14 14 14 14 种种 2 树图法 位置 1 乙 丙 丁 2 甲 丁 丙 甲 丁 甲 丙 3 丁 甲 丁 丁 乙 甲 乙 乙 甲 4 丙 丙 甲 乙 甲 乙 丙 甲 乙 由树图可知有9种不同排法 3 3 3 3 可先排丙 丁有 可先排丙 丁有 种排法 则甲 乙只有一种排种排法 则甲 乙只有一种排 法 由分步计数原理满足条件的排列共有法 由分步计数原理满足条件的排列共有 1 1 1 1 12 12 12 12 种种 或看作定序问题 或看作定序问题 12 12 12 12 方法总结 2 位置分析法 在解有限定位置的排列问题时 首先 考虑特殊位置的安排方法 再考虑其他位置的排法 3 间接法又叫排除法 在解有限定条件的排列问 题时 首先求出不加限定条件的排列数 再减去不符合 条件的排列数 1 元素分析法 在解有限定元素的排列问题时 首先 考虑特殊元素的安排方法 再考虑其他元素的排法 4 树图法又称框图法 用树图或框图列出所有排列 或组合 从而求出排列数 是解决多个限定条件的排 列组合问题的常用法 5 消序法 定序问题 部分相同元素排列问题 平 均分组问题常用此法 先将所有元素全排列 再将特殊元 素在其位置上换位情况消去 通常除以特殊元素的全排列 数 只保留指定的一种顺序 变式变式变式变式3 3 3 3 1 1 1 1 从从6 6人人中选中选4 4 4 4人分别到巴黎 伦敦 悉尼 莫斯科人分别到巴黎 伦敦 悉尼 莫斯科 四个城市游览 要求每个城市有一人游览 每人只游览四个城市游览 要求每个城市有一人游览 每人只游览 一个城市 且这一个城市 且这6 6 6 6个人中甲 乙两人不去巴黎游览 则不个人中甲 乙两人不去巴黎游览 则不 同的选择方案共有同的选择方案共有 A A A A 300300300300种种 B B B B 240240240 240种种 C C C C 144144144144种种 D D D D 9696 9696种种 2 2 2 2 安排安排5 5 5 5名歌手的演出顺序时 要求某名歌手不第一名歌手的演出顺序时 要求某名歌手不第一 个出场 另一名歌手不最后一个出场 不同排法的种数个出场 另一名歌手不最后一个出场 不同排法的种数 是是 用数字作答用数字作答 解析解析解析解析 1 1 1 1 240 2 240 2 240 2 240 2 答案 答案 答案 答案 1 B 1 B 1 B 1 B 2 78 2 78 2 78 2 78 题型4 排列中的 相邻 不相邻问题 例例例例4 4 4 4 a a a a1 1 1 1 a a a a2 2 2 2 a a a a8 8 8 8共八个元素 共八个元素 分别计算满足下列 分别计算满足下列 条件的排列数 条件的排列数 1 1 1 1 八个元素排成一排 且八个元素排成一排 且a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4四个元素排在一四个元素排在一 起 起 2 2 2 2 八个元素排成一排 且八个元素排成一排 且a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4四个元素互不相四个元素互不相 邻 邻 3 3 3 3 八个元素排成一排 且八个元素排成一排 且a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4四个元素互不相四个元素互不相 邻 并且邻 并且a a a a5 5 5 5 a a a a6 6 6 6 a a a a7 7 7 7 a a a a8 8 8 8也互不相邻 也互不相邻 4 4 4 4 排成前后两排每排四个元素 排成前后两排每排四个元素 解答 解答 解答 解答 1 1 1 1 捆绑法捆绑法 先将a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4四个元素看成一四个元素看成一 个元素个元素与与a a a a5 5 5 5 a a a a6 6 6 6 a a a a7 7 7 7 a a a a8 8 8 8排列一排 有排列一排 有 种排法 再排种排法 再排a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4有 不同排法 根据分步计数原理知满足条件分步计数原理知满足条件 的排列数为的排列数为 2 880 2 880 2 880 2 880 5 5 A 4 4 A 5 5 A 4 4 A 2 2 2 2 插空法插空法 先排 先排a a a a5 5 5 5 a a a a6 6 6 6 a a a a7 7 7 7 a a a a8 8 8 8四个元素排成一排 四个元素排成一排 有有 种排法 再将元素种排法 再将元素a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4插入由插入由a a a a5 5 5 5 a a a a6 6 6 6 a a a a7 7 7 7 a a a a8 8 8 8间隔及两端的五个位置中的四个 有间隔及两端的五个位置中的四个 有 种排法 根据分种排法 根据分 步计数原理知 满足条件的排列数为步计数原理知 满足条件的排列数为 2 880 2 880 2 880 2 880 4 4 A 4 5 A 4 4 A 4 5 A 3 3 3 3 先先排排a a a a5 5 5 5 a a a a6 6 6 6 a a a a7 7 7 7 a a a a8 8 8 8 共有 共有 种排种排 法 然后排法 然后排a a a a1 1 1 1 a a a a2 2 2 2 a a a a3 3 3 3 a a a a4 4 4 4排在排在 或或 中中 的的 共有共有2 2 2 2 种排法 根据分步计数原理共有种排法 根据分步计数原理共有 2 2 2 2 1 1521 1521 1521 152种排法 种排法 4 4 4 4 前排有前排有 种排法 后排有种排法 后排有 种排法 由分步计数原种排法 由分步计数原 理知共有理知共有 8 8 8 8 种排法 种排法 4 4 A 4 4 A 4 4 A 4 4 A 4 8 A 4 4 A 4 4 A 4 8 A 方法总结 1 若某些元素必须相邻 常用捆绑法 即先把这 几个相邻元素捆在一起看成一个元素 再与其他元素全排 列 最后再考虑这几个相邻元素的顺序 2 若某些元素不相邻 常用插空法 即先将普通 元素全排列 然后再从排就的每两个元素之间及两端选出 若干个空挡插入这些特殊元素 3 前后排问题 直排法 变式变式变式变式4 4 4 4 4 4 4 4个男个男同学 同学 3 3 3 3个女同学站成一排 个女同学站成一排 1 3 1 3 1 3 1 3个女同学必须排在一起 有多少种不同的排法 个女同学必须排在一起 有多少种不同的排法 2 2 2 2 任何两个女同学彼此不相邻 有多少种不同的排任何两个女同学彼此不相邻 有多少种不同的排 法 法 3 3 3 3 其中甲 乙两同学之间必须恰有其中甲 乙两同学之间必须恰有3 3 3 3人 有多少种不人 有多少种不 同的排法 同的排法 4 4 4 4 甲 乙两人相邻 但都不与丙相邻 有多少种不甲 乙两人相邻 但都不与丙相邻 有多少种不 同的排法 同的排法 5 5 5 5 女同学从左到右按高矮顺序排 有多少种不同的排女同学从左到右按高矮顺序排 有多少种不同的排 法 法 3 3 3 3个女生身高互不相等个女生身高互不相等 解答 解答 解答 解答 1 3 1 3 1 3 1 3个女个女同学是特殊元素 我们先把她们排好 共同学是特殊元素 我们先把她们排好 共 有有 种排法 由于种排法 由于3 3 3 3个女同学必须排在一起 我们可视排个女同学必须排在一起 我们可视排 好的女同学为一整体 再与男同学排队 这时是好的女同学为一整体 再与男同学排队 这时是5 5 5 5个元素个元素 的全排列 应有的全排列 应有 种排法 由分步计数的原理种排法 由分步计数的原理 有有 720720720720 种不同排法 种不同排法 2 2 2 2 先将男生排好 共有先将男生排好 共有 种排法 再在这种排法 再在这4 4 4 4个男生的中间个男生的中间 及两头的及两头的5 5 5 5个空档中插入个空档中插入3 3 3 3个女生有个女生有 种方案 故符合条种方案 故符合条 件的排法共有件的排法共有 1 1 1 1 440440440440种不同排法 种不同排法 5 5 A 3 3 3 3 甲 乙甲 乙2 2 2 2人先排好 有人先排好 有 种排法 再从余下种排法 再从余下5 5 5 5人中选人中选3 3 3 3人人 排在甲 乙排在甲 乙2 2 2 2人中间 有人中间 有 种排法 这时把已排好的种排法 这时把已排好的5 5 5 5人视人视 为一整体 与最后剩下的为一整体 与最后剩下的2 2 2 2人再排 又有人再排 又有 种排法 这样种排法 这样 总共有总共有 720720720720种不同排法 种不同排法 4 4 4 4 先排甲 乙和丙先排甲 乙和丙3 3 3 3人以外的其他人以外的其他4 4 4 4人 有人 有 种排法 由种排法 由 于甲 乙要相邻 故再把甲 乙排好 有于甲 乙要相邻 故再把甲 乙排好 有 种排法 最后种排法 最后 把甲 乙排好的这个整体与丙分别插入原先排好的把甲 乙排好的这个整体与丙分别插入原先排好的4 4 4 4人的人的 空档中有空档中有 种排法 这样 总共有种排法 这样 总共有 960960960960种不同种不同 排法 排法 5 5 5 5 从从7 7 7 7个位置中选出个位置中选出4 4 4 4个位置把男生排好 则有个位置把男生排好 则有 种排种排 法 然后再在余下的法 然后再在余下的3 3 3 3个空位置中排女生 由于女生要按个空位置中排女生 由于女生要按 身体高矮排列 故仅有一种排法 这样总共有身体高矮排列 故仅有一种排法 这样总共有 840840840840 种不同排法种不同排法 题型5 组合问题 例例5 5 5 5 7 7 7 7个相同的小球 任意放入个相同的小球 任意放入4 4 4 4个不同的盒子中 试个不同的盒子中 试 问 问 1 1 1 1 每个盒子都不空的放法共有多少种 每个盒子都不空的放法共有多少种 2 2 2 2 某些盒子可空的放法共有多少种 某些盒子可空的放法共有多少种 解析 1 将7个相同小球 放入4个不同盒子 每个盒子 不空 即相当于把7个相同小球分成4组 每组都有小球 一种分法对应一种放法 先将7个小球排成一排有1种排 法 在小球的中间的6个空挡中选3个放入隔板 有 放 法 故满足条件放法共有 种 3 6 C 2 将7个相同小球