§101 分类加法计数原理与分步乘法计数理.ppt

山东金榜苑文化传媒集团 步步高大一轮复习讲义 分类加法计数原理与分步乘法计数原理 山东省临沂一中学多媒体教学课件 两大基本原理 选修2 3第一章 1 分类加法计数原理完成一件事有n类不同的方案 在第一类方案中有m1种不同的方法 在第二类方案中有m2种不同的方法 在第n类方案中有mn种不同的方法 则完成这件事情 共有N 种不同的方法 2 分步乘法计数原理完成一件事情需要分成n个不同的步骤 完成第一步有m1种不同的方法 完成第二步有m2种不同的方法 完成第n步有mn种不同的方法 那么完成这件事情共有N 种不同的方法 忆一忆知识要点 排列与组合 计数原理 二项式定理 通项 二项式系数性质 排列数 组合数 分类计数原理分步计数原理 性质 对称性 增减性与最大值 各二项式系数的和 两个原理 3 分类加法计数原理与分步乘法计数原理 都涉及完成一件事情的不同方法的种数 它们的区别在于 分类加法计数原理与分类有关 各种方法相互独立 用其中的任一种方法都可以完成这件事 分步乘法计数原理与分步有关 各个步骤相互依存 只有各个步骤都完成了 这件事才算完成 忆一忆知识要点 C 16 分类加法计数原理 例1 高三一班有学生50人 男生30人 女生20人 高三二班有学生60人 男生30人 女生30人 高三三班有学生55人 男生35人 女生20人 1 从高三一班或二班或三班中选一名学生任学生会主席 有多少种不同的选法 2 从高三一班 二班男生中 或从高三三班女生中选一名学生任学生会体育部长 有多少种不同的选法 解 1 50 60 55 165 种 即所求选法为165种 2 30 30 20 80 种 即所求选法有80种 分类时 首先要根据问题的特点确定一个适合于它的分类标准 然后在这个标准下进行分类 其次分类时要注意满足一个基本要求 就是完成这件事情的任何一种方法必须属于某一类 并且分别属于不同种类的两种方法是不同的方法 只有满足这些条件 才可以用分类加法计数原理 同学衣服上左 右各有一个口袋 左边口袋装有30张英语单词卡片 右边口袋装有20张英语单词卡片 这些英语单词卡片都互不相同 则从两个口袋里任取一张英语单词卡片 有 种不同的取法 从口袋中任取一张英语单词卡片的方法分两类 第一类 从左边口袋取一张英语单词卡片有30种不同的取法 第二类 从右边口袋取一张英语单词卡片有20种不同的取法 上述的其中任何一种取法都能独立完成取一张英语单词卡片这件事 应用分类加法计数原理 所以从中任取一张英语单词卡片的方法种数为30 20 50 种 50 分步乘法计数原理 例2 已知集合M 3 2 1 0 1 2 P a b 表示平面上的点 a b M 问 1 P可表示平面上多少个不同的点 2 P可表示平面上多少个第二象限的点 3 P可表示多少个不在直线y x上的点 解 1 确定平面上的点P a b 可分两步完成 第一步确定a的值 共有6种确定方法 第二步确定b的值 也有6种确定方法 根据乘法原理 得到平面上的点的个数是6 6 36 2 确定第二象限的点 可分两步完成 第一步确定a 由于a0 所以有2种确定方法 由乘法原理 得到第二象限的点的个数是3 2 6 分步乘法计数原理 3 点P a b 在直线y x上的充要条件是a b 因此a和b必须在集合M中取同一元素 共有6种取法 即在直线y x上的点有6个 由 1 得不在直线y x上的点共有36 6 30 个 利用分步乘法计数原理解决问题 要按事件发生的过程合理分步 即分步是有先后顺序的 各步中的方法互相依存 缺一不可 只有各个步骤都完成了才算完成这件事 例2 已知集合M 3 2 1 0 1 2 P a b 表示平面上的点 a b M 问 3 P可表示多少个不在直线y x上的点 已知集合M 3 2 1 0 1 2 若a b c M 则 1 y ax2 bx c可以表示多少个不同的二次函数 2 y ax2 bx c可以表示多少个图象开口向上的二次函数 解 1 a的取值有5种情况 b的取值有6种情况 c的取值有6种情况 因此y ax2 bx c可以表示5 6 6 180 个 不同的二次函数 2 y ax2 bx c的开口向上时 a的取值有2种情况 b c的取值均有6种情况 因此y ax2 bx c可以表示2 6 6 72 个 图象开口向上的二次函数 两个计数原理的综合应用 例3 用0 1 2 3 4 5可以组成多少个无重复数字的比2000大的4位偶数 解 完成这件事可分为3类方法 第一类是用0做结尾的比2000大的4位偶数 它可以分三步去完成 第一步 选取千位上的数字 只有2 3 4 5可以选择 有4种选法 第二步 选取百位上的数字 除0和千位上已选定的数字以外 还有4个数字可供选择 有4种选法 第三步 选取十位上的数字 还有3种选法 依据分步乘法计数原理 这类数的个数有4 4 3 48 个 两个计数原理的综合应用 第二类是用2做结尾的比2000大的4位偶数 它可以分三步去完成 第一步 选取千位上的数字 除去2 1 0只有3个数字可以选择 有3种选法 第二步 选取百位上的数字 在去掉已经确定的首尾两数字之后 还有4个数字可供选择 有4种选法 第三步 选取十位上的数字 还有3种选法 依据分步乘法计数原理 这类数的个数有3 4 3 36 个 第三类是用4做结尾的比2000大的4位偶数 其步骤同第二类 有3 4 3 36 个 对以上三类结论用分类加法计数原理 可得所求无重复数字的比2000大的4位偶数有48 36 36 120 个 用两个计数原理解决计数问题时 关键是明确需要分类还是分步 1 分类要做到 不重不漏 分类后再分别对每一类进行计数 最后用分类加法计数原理求和 得到总数 2 分步要做到 步骤完整 只有完成了所有步骤 才完成任务 根据分步乘法计数原理 把完成每一步的方法数相乘 得到总数 3 对于复杂问题 可同时运用两个计数原理或借助列表 画图的方法来帮助分析 解 方法一以S A B C D顺序分步染色 第一步 S点染色 有5种方法 第二步 A点染色 与S在同一条棱上 有4种方法 第三步 B点染色 与S A分别在同一条棱上 有3种方法 第四步 C点染色 也有3种方法 但考虑到D点与S A C相邻 需要针对A与C是否同色进行分类 当A与C同色时 D点有3种染色方法 当A与C不同色时 因为C与S B也不同色 所以C点有2种染色方法 D点也有2种染色方法 由分步乘法 分类加法计数原理得不同的染色方法共有5 4 3 1 3 2 2 420 种 如图所示 将一个四棱锥的每一个顶点染上一种颜色 并使同一条棱上的两端异色 如果只有5种颜色可供使用 求不同的染色方法总数 解 方法二可分为两大步进行 先将四棱锥一侧面三顶点染色 然后再分类考虑另外两顶点的染色数 用分步乘法计数原理即可得出结论 由题设 四棱锥S ABCD的顶点S A B所染的颜色互不相同 它们共有5 4 3 60 种 染色方法 当S A B染好时 不妨设其颜色分别为1 2 3 若C染2 则D可染3或4或5 有3种染法 若C染4 则D可染3或5 有2种染法 若C染5 则D可染3或4 有2种染法 可见 当S A B已染好时 C D还有7种染法 故不同的染色方法有60 7 420 种 方法三按所用颜色种数分类 第一类 5种颜色全用 共有种不同的方法 第二类 只用4种颜色 则必有某两个顶点同色 A与C 或B与D 共有2 种不同的方法 第三类 只用3种颜色 则A与C B与D必定同色 共有种不同的方法 由分类加法计数原理 得不同的染色方法总数为 420 种 如图所示 将一个四棱锥的每一个顶点染上一种颜色 并使同一条棱上的两端异色 如果只有5种颜色可供使用 求不同的染色方法总数 5分 2010 湖南 在某种信息传输过程中 用4个数字的一个排列 数字允许重复 表示一个信息 不同排列表示不同信息 若所用数字只有0和1 则与信息0110至多有两个对应位置上的数字相同的信息个数为 A 10B 11C 12D 1526 11 分类不准 计数原理使用不当致误 B 11 分类不准 计数原理使用不当致误 解 方法一分0个相同 1个相同 2个相同讨论 1 若0个相同 则信息为 1001 共1个 2 若1个相同 则信息为 0001 1101 1011 1000 共4个 3 若2个相同 又分为以下情况 若位置一与二相同 则信息为 0101 若位置一与三相同 则信息为 0011 若位置一与四相同 则信息为 0000 若位置二与三相同 则信息为 1111 若位置二与四相同 则信息为 1100 若位置三与四相同 则信息为 1010 共有6个 故与信息0110至多有两个对应位置上的数字相同的信息个数为1 4 6 11 解 方法二若0个相同 共有1个 若1个相同 共有 4 个 若2个相同 共有 6 个 故共有1 4 6 11 个 1 本题考查的是分类加法计数原理 难度不大 属中档题 2 本题要求至多有两个对应位置上的数字相同 应按照0个相同 1个相同 2个相同进行讨论 本题易错点是易漏掉0个相同的情况 1 分类加法和分步乘法计数原理 都是关于做一件事的不同方法的种数的问题 区别在于 分类加法计数原理针对 分类 问题 其中各种方法相互独立 用其中任何一种方法都可以做完这件事 分步乘法计数原理针对 分步 问题 各个步骤相互依存 只有各个步骤都完成了才算完成这件事 2 混合问题一般是先分类再分步 3 分类时标准要明确 做到不重复不遗漏 4 要恰当画出示意图或树状图 使问题的分析更直观 清楚 便于探索规律 应用两种原理解题 1 分清要完成的事情是什么 2 分清完成该事情是分类完成还是分步完成 类 间互相独立 步 间互相联系 3 有无特殊条件的限制 4 检验是否有重漏 作业布置 作业纸 课时规范训练 P 1 2 预祝各位同学 2013年高考取得好成绩 一 选择题 二 填空题 A组专项基础训练题组 三 解答题 7 如图 用四种不同颜色给图中的A B C D E F六个点涂色 要求每个点涂一种颜色 且图中每条线段的两个端点涂不同颜色 则不同的涂色方法共有多少种 解 先涂A D E三个点 共有4 3 2 24 种 涂法 然后再按B C F的顺序涂色 分为两类 一类是B与E或D同色 共有2 2 1 1 2 8 种 涂法 另一类是B与E或D不同色 共有1 1 1 1 2 3 种 涂法 所以涂色方法共有24 8 3 264 种 三 解答题 8 某外语组有9人 每人至少会英语和日语中的一门 其中7人会英语 3人会日语 从中选出会英语和日语的各一人 有多少种不同的选法 解 由题意得有1人既会英语又会日语 6人只会英语 2人只会日语 第一类 从只会英语的6人中选1人说英语 共有6种方法 则说日语的有2 1 3 种 此时共有6 3 18 种 第二类 从不只会英语的1人中选1人说英语 则只有1种方法 则选会日语的有2种 此时共有1 2 2 种 所以根据分类加法计数原理知共有18 2 20 种 选法 一 选择题 二 填空题 B组专项能力提升题组 解 1 显然对应是一一对应的 即为a1找象有4种方法 a2找象有3种方法 a3找象有2种方法 a4找象有1种方法 所以不同的f共有4 3 2 1 24 个 2 0必无原象 1 2 3有无原象不限 所以为A中每一元素找象时都有3种方法 所以不同的f共有34 81 个 三 解答题 8 已知集合A a1 a2 a3 a4 B 0 1 2 3 f是从A到B的映射 1 若B中每一元素都有原象 这样不同的f有多少个 2 若B中的元素0必无原象 这样的f有多少个 3 若f满足f a1 f a2 f a3 f a4 4 这样的f又有多少个 排列 组合 计数原理 计数原理 二项式定理 组合 通项 二项式定理 二项式系数性质 分类计数原理 分步计数原理 排列 排列的定义 排列数公式 组合的定义 组合数公式 组合数性质 应用 做一件事或完成一项工作的方法数 直接 分类 完成 间接 分步骤 完成 做一件事 完成它可以有n类办法 第一类办法中有m1种不同的方法 第二类办法中有m2种不同的方法 第n类办法中有mn种不同的方法 那么完成这件事共有N m1 m2 m3 mn种不同的方法 做一件事 完成它可以有n个步骤 做第一步中有m1种不同的方法 做第二步中有m2种不同的方法 第n步中有mn种不同的方法 那么完成这件事共有N m1 m2 m3 mn种不同的方法 1 两个原理的区别于联系 结论 集合A中有m个元素 集合B中有n个元素 那么从A到B可以构造nm个映射 解 第一步 给a找对应元素 有3种方法 第二步 给b找对应元素 有3种方法 第三步 给c找对应元素 有3种方法 第四步 给d找对应元素 有3种方法 第五步 给e找对应元素 有3种方法 例1 设A a b c d e B x y z 从A到B共有多少种不同的映射 一映射个数问题 形成一个映射 就是让A中所有元素都找到对应元素 则共有方法种数N 35 例1 设A a b c d e f B x y z 从A到B共有多少种不同的映射 1 设A 1 2 3 B 4 5 6 从A到B满足1的象是4的映射有多少种 2 设集合A x y z B 1 0 1 映射f A B满足f x f y f z 0的映射有多少种 练一练 3 已知集合A a b c d 集合B 1 2 3 4 5 集合C e f g h 1 从集合B到集合A可以建立多少个不同的映射 2 在集合A到集合B的映射中 若要求集合A中的不同元素的象也不同 这样的映射有多少个 3 从集合A到集合C可以建立多少个一一映射 练一练 例2 集合A a b c d e 它的子集个数为 真子集个数为 非空子集个数为 非空真子集个数为 二子集问题 1 集合M满足 1 2 M 0 1 2 3 4 5 则这样的集合M有多少个 变式练习 真子集有 个 非空子集个数为 非空真子集个数有 规律 n元集合 a1 a2 an 的不同子集有个 个 2n 二子集问题 解 按地图A B C D四个区域依次分四步完成 第一步 m1 3种 第二步 m2 2种 第三步 m3 1种 第四步 m4 1种 三 着色问题 例3 如图 要给地图A B C D四个区域分别涂上3种不同颜色中的某一种 允许同一种颜色使用多次 但相邻区域必须涂不同的颜色 不同的涂色方案有多少种 所以根据乘法原理 得到不同的涂色方案种数共有 N 3 2 1 1 6种 例3 如图 要给地图A B C D四个区域分别涂上3种不同颜色中的某一种 允许同一种颜色使用多次 但相邻区域必须涂不同的颜色 不同的涂色方案有多少种 三 着色问题 用红 黄 绿 黑四种不同的颜色涂入下图中的五个区域内 要求相邻的两个区域的颜色都不相同 则有多少种不同的涂色方法 当B与D不同色时 有4 3 2 1 1 24种 解 当B与D同色时 有4 3 2 1 2 48种 故共有48 24 72种不同的涂色方法 练一练 点评 像这类给区域涂色的问题 我们应该给区域依次标上相应的序号 以便分析问题 在给各区域涂色时 要注意不同的涂色顺序其解题就有繁简之分 如本例若按A B E D C顺序涂色时 在最后给区域C涂色时 就应考虑A与E是否同色 B与D是否同色这两种情况 因此在分析解决这类问题时 应按不同的涂色顺序多多尝试 看那一个最简单 本例易错点 未考虑B与D是否同色 2003年 全国高考题 如图所示 一个地区分为5个行政区域 现给地图着色 要求相邻区域不得使用同一颜色 现有4种颜色可供选择 则不同的着色方法有 种 以数字作答 同类变式 解 因区域1与其他四个区域都相邻 宜先考虑区域1 有4种涂法 同类变式 2 若区域2 4不同色 先涂区域2有3种方法 再涂区域4有2种方法 此时区域3 5也都只有1种涂法 涂法总数为4 3 2 1 24种 因此涂法共有72种 1 若区域2 4同色 有3种涂法 此时区域3 5均有两种涂法 涂法总数为4 3 2 2 48种 例4 用0 1 2 3 4 5这六个数字 1 可以组成多少个各位数字不允许重复的六位的自然数 2 可以组成多少个各位数字不允许重复的三位的奇数 3 可以组成多少个各位数字不重复的小于1000的自然数 4 可以组成多少个大于3000 小于5421且各位数字不允许重复的四位数 四 排数字问题 1 1 2 3 4数字可以组成多少个没有重复数字能被3整除的三位数 2 随着人们生活水平的提高 某城市家庭汽车拥有量迅速增长 汽车牌照号码需要扩容 交通管理部门出台了一种汽车牌照组成办法 每一个汽车牌照都必须有 个不重复的英文字母和 个不重复的阿拉伯数字 并且 个字母必须合成一组出现 个数字也必须合成一组出现 那么这种办法共能给多少辆汽车上牌照 练一练 第二步 让与甲取走的卡片相对应的人来拿 有3种拿法 例如甲拿的是2 则乙有3种拿法 总的方法数N 3 3 1 1 9 方法一 采用 分步 处理 第一步 甲先拿 按规定甲可拿2 3 4当中的一张 有3种方法 第三步 让剩余的两个人拿 都均有1种拿法 例5 同室4人各写1张贺年卡 先集中起来 然后每人从中各拿1张别人送出的贺年卡 则4张贺年卡不同的分配方式有 A 6种B 9种C 11种D 23种 五 综合问题 B 树图法 甲乙丙丁 2 134 441 313 3 144 221 412 4 133 212 321 解 四名同学分别为 甲 乙 丙 丁 所写贺卡依次为1 2 3 4 例6 自然数4320有多少个正约数 解 4320 25 33 5 其正约数的结构式为 其中 可取0 1 2 3 4 5 可取0 1 2 3 可取0 1 即在 所形成的取值集合中 各取一个元素填入上式 就得4320的一个约数 第一步 取20 21 22 23 24 25有6种 第二步 取30 31 32 33有4种 第三步 取50 51有2种 由分步计数原理 共有6 4 2 48种 1 630的不同的正约数的个数是 练一练 解 630 2 32 5 7 2 5张1元币 4张1角币 1张5分币 2张2分币 可组成 种不同的币值 1张不取 即0元0分0角不计在内 元 0 1 2 3 4 5角 0 1 2 3 4分 0 2 4 5 7 9 6 5 6 1 179 179 3 三边长均为整数 且最大边长为11的三角形共有多少个 解 另两边长用x y表示 且不妨设1 x y 11 要构成三角形 必须x y 12 当y 11时 有11个三角形 当y 10时 有9个三角形 当y 6时 有1个三角形 所以 所求三角形的个数共有 练一练 3 在所有的两位数中 个位数字大于十位数字的两位数共有多少个 分析1 按个位数字是2 3 4 5 6 7 8 9分成8类 在每一类中满足条件的两位数分别是1个 2个 3个 4个 5个 6个 7个 8个 则根据加法原理共有1 2 3 4 5 6 7 8 36 个 分析2 按十位数字是1 2 3 4 5 6 7 8分成8类 在每一类中满足条件的两位数分别是8个 7个 6个 5个 4个 3个 2个 1个 则根据加法原理共有8 7 6 5 4 3