1、第五讲 计数综合 从三年级开始到现在， 我们已经学了很多有关计数的讲次， 其中包括枚举法、 加乘原理、 排列组合、容斥原理等我们先来做一个简单的小结和复习 枚举法是万能的方法， 只要有足够多的时间和精力 并且往往在一些复杂棘手的题目中， 别的方法都不能适用， 此时就能体会到枚举法的“威力” 使用枚举法时一定要注意有序思考有序思考 加法原理强调的是分类分类， 计数时我们只需选择其中的某一类即可以满足要求， 类与类之 间可以相互替代 乘法原理强调的是分步分步，每一步只是整个事情的一部分，必须全部完成才能满足结论， 缺一不可在乘法原理中，步骤顺序的安排往往非常重要 排列与组合： 排列的计算公式由乘法
2、原理推导而来， 组合的计算公式由排列公式推导而 来 从 n 个不同的元素中取出 m 个（m n ） ，并按照一定的顺序排成一列，其方法数叫做 从 n 个不同元素中取出 m 个的排列数，记作 m n A ! 121 ! m n n Annnnm nm 从 n 个不同元素中取出 m 个（mn）作为一组（不计顺序） ，可选择的方法数叫做从 n 个不同元素中取出 m 个的组合数，记作 m n C 121 !121 m mn n nnnnmA C mmmm 在运用排列组合时，有特殊要求的我们往往优先考虑，有时还会用到“捆绑法”和“插空 法”. 我们今天主要来学习计数中的分类思想，以及正面分类和反面排除的
3、合理选择 分类讨论是一种重要的数学思想方法， 当问题所给对象不能进行统一研究时， 就需要对研究 的对象进行分类， 将整体问题划分为局部问题， 把复杂问题转化为单一问题， 然后分而治之、 各个击破，最后综合各类的结果得到整个问题的解答 例题 1 五张卡片上分别写有 0、1、2、3、5，每张卡片各用一次可以组成一些五位数其中 5 的倍 数有多少个？4 的倍数有多少个？ 分析：一个数是 5 的倍数，它要满足什么条件？4 的倍数呢？ 练习 1 五张卡片上分别写有 0、1、2、3、5，每张卡片只能用一次可以组成多少个三位偶数？ 例题 2 （1）用 2 个 1、2 个 2 和 1 个 3 可以组成多少个不
4、同的五位数？ （2）用 1 个 0、2 个 1 和 2 个 2 可以组成多少个不同的五位数？ （3）用 1 个 0、2 个 1 和 2 个 2 可以组成多少个不同的四位数？ 分析：先选好 1 的位置，再选好 2 的位置，最后选好 3 的位置，就可以组成五位数那么有 多少种不同的选法？ 练习 2 （1）用 1 个 1、1 个 2、2 个 3 可以组成多少个不同的四位数？ （2）用 1 个 0、1 个 2、2 个 3 可以组成多少个不同的四位数？ （3）用 1 个 0、1 个 2、2 个 3 可以组成多少个不同的三位数？ 例题 3 数 1447、1225、1031 有某些相同的特点，每一个数都是以
5、 1 为首的四位数，且每个数恰好 只有两个数字相同（1112，1222，1122 这样的数不算） ，这样的数共有多少个？ 分析：根据题意可知这样的四位数由三种数字组成，其中有一种数字出现了 2 次那么可以 根据这个数字所在的数位来分类 练习 3 用 1、2、3、4 这 4 个数字组成四位数，至多允许有 1 个数字重复一次例如 1234、1233 和 2434 是满足条件的，而 1212、3331 和 4444 就是不满足条件的那么，所有这样的四位 数共有多少个？ 例题 4 和 2468 相加至少会发生一次进位的四位数有多少个？ 分析：和 2486 相加发生进位有好多种情况，比如发生一次进位、发
6、生两次进位、发生三次 进位等等，不同的类型太多了这时不妨考虑下反面 练习 4 和 250 相加至少会发生一次进位的三位数有多少个？ 例题 5 有 10 名外语翻译，其中 5 名是英语翻译，4 名日语翻译，另外 1 名英语和日语都很精通， 从中找出 7 人，使他们可以组成两个翻译小组，其中 4 人翻译英语，另 3 人翻译日语，这两 个小组能同时工作，则不同的分配方案共有多少种？ 分析：这个英语和日语都很精通的人很麻烦，应该优先考虑他 例题 6 将右图中的“”分别用四种颜色染色， 只要求有实线段连接的两个相邻的“”都涂成不同的颜 色，共有多少种涂法？如果还要求虚线段连接的两个“”也涂成不同的颜色，
7、共有多少种涂 法？ 分析：染色时顺序很重要，要遵循“前不影响后”的原则 四色定理 四色定理四色定理指出每个可以画出来的无飞地地图（飞地是指与本土不相连的土地）都可以至 多用 4 种颜色来上色， 而且没有两个相邻的区域会是相同的颜色 被称为相邻的两个区域是 指它们共有一段边界，而不是一个点 这一定理最初是由 Francis Guthrie 在 1853 年提出的猜想很明显，3 种颜色不会满足条 件，而且也不难证明 5 种颜色满足条件且绰绰有余但是，直到 1977 年四色猜想才最终由 Kenneth Appel 和 Wolfgang Haken 证明他们得到了 J. Koch 在算法工作上的支持
8、证明方法将地图上的无限种可能情况减少为 1,936 种状态（稍后减少为 1,476 种），这 些状态由计算机一个挨一个的进行检查这一工作由不同的程序和计算机独立的进行了复 检在 1996 年，Neil Robertson、Daniel Sanders、Paul Seymour 和 Robin Thomas 使用了一种 类似的证明方法，检查了 633 种特殊的情况这一新证明也使用了计算机，如果由人工来检 查的话是不切实际的 四色定理是第一个主要由计算机证明的理论，这一证明并不被所有的数学家接受，因为 它不能由人工直接验证 最终， 人们必须对计算机编译的正确性以及运行这一程序的硬件设 备充分信任参
9、见实验数学 缺乏数学应有的规范成为了另一个方面；以至于有人这样评论“一个好的数学证明应当 像一首诗而这纯粹是一本电话簿！” 虽然四色定理证明了任何地图可以只用四种颜色着色， 但是这个结论对于现实中的应用 却相当有限现实中的地图常会出现飞地，即两个不相连的土地属于同一个国家的情况（例 如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种 情况下，四个颜色将会是不够用的 作业1. 计算： （1） 3 8 C _； （2） 4 8 A _； （3） 8 10 C_； （4） 012345 555555 CCCCCC_ 作业2. 王老师家装修新房，需要 2 个木匠和 2 个
10、电工现有木匠 3 人、电工 4 人，另有 1 人既能做木匠也能做电工 要从这 8 人中挑选出 4 人完成这项工作， 共有多少种不同的 选法？ 作业3. 用 2 个 3、3 个 1 和 1 个 0 可以组成多少个不同的六位数？ 作业4. 用 2 个 5、1 个 2 和 1 个 0 可以组成多少个不同的三位数？ 作业5. 与 1357 相加会发生进位的四位数有多少个？ 第五讲 计数综合 例题1. 答案：42，18 详解：5 的倍数分为两类，末位是 5 的有3 32 118 个，末位是 0 的有4 3 2 124 个，共 42 个4 的倍数：末两位是 20 的有 6 个，末两位是 12 的有 4 个
11、，末两位是 32 的有 4 个，末两位是 52 的有 4 个，共有 18 个 例题2. 答案： （1）30； （2）24； （3）24 详解： （1）先给 1 选位置，再给 2 选位置，再给 3 选位置，共可组成 221 531 30CCC个不同的五位 数（2） 先给 0 选位置， 再给 1 选位置， 再给 2 选位置， 共可组成 122 442 24CCC个不同的五位数（3） 注意这个地方是要组成四位数， 所以有一个数字不会用到 如果有1个1没用， 可以组成 121 331 9CCC 个不同的四位数；如果有 1 个 2 没用，可以组成 121 331 9CCC个不同的四位数；如果 0 没有用
12、，可 以组成 6 个不同的四位数一共可以组成 24 个不同的四位数 例题3. 答案：432 详解：按重复的数字是不是 1 可以分成两类，若重复的数字是 1，则有 12 39 216CA个，若重复的数 字不是 1，则有 121 938 216CCC个，一共是 432 个 例题4. 答案：8661 详解：一共有 9000 个四位数考虑与 2468 相加不会进位的四位数，个位可以是 01，有 2 种可能； 十位可以是 03，有 4 种可能；百位可以是 05，有 6 种可能；千位可以是 1 7，有 7 种可能那么 这样的四位数有2467336 个那么至少会发生一次进位的四位数有90003368664个
13、 例题5. 答案：90 详解：按“自由人”的归属来分类：不选这个“自由人” ，有 43 54 20CC种；让“自由人”翻译英语， 有 33 54 40CC种；让“自由人”翻译日语，有 42 54 30CC种；一共是 90 种 例题6. 答案：432，336 详解：如果不考虑虚线，有4 3 2 3 3 2432 种涂法 如果考虑虚线，先染四边形顶点上的四个“”，有 84 种染法，然后再染剩下的 2 个“”，有 8422336 种染法 练习1. 答案：21 简答：末尾数字可以是 0 或 2末尾数字是 0 的三位偶数有4 3 112 个，末尾数字是 2 的三位偶数 有3 3 19 个，一共有 21
14、个 练习2. 答案： （1）12； （2）9； （3）9 简答： （1） 112 432 12CCC； （2） 112 332 9CCC； （3）4 个数字中有一个没有被选如果没有选 0， 有 12 32 3CC个如果没有选 2，有 12 22 2CC个如果没有选的是 3，有 111 221 4CCC个一共有 9 个 练习3. 答案：168 简答：根据相同数字所在的位置来分类即可 练习4. 答案：550 简答：所有的三位数有 900 个，其中与 250 相加不会发生进位的有75 10350 个，那么会发生进 位的有900350550个 作业1. 答案： （1）56； （2）1680； （3）45； （4）32 简答：略 作业2. 答案：48 简答：根据既能做木匠又能做电工那个人的挑选情况分类讨论，可以分三类：没有选，做电工和做木 匠 作业3. 答案：50 简答： 123 553 CCC50 作业4. 答案：9 简答：如果三位数中不含有 0，有 2 3 C3个；如果含有 0，剩下的两个数字可能是 2 个 5，也有可能是 1 个 5 和 1 个 2，共有246个一共可以组成 9 个不同的三位数 作业5. 答案：8160 简答：利用反面排除的方法，90008 75 38160