第五讲 计数综合

从三年级开始到现在，我们已经学了很多有关计数的讲次，其中包括枚举法、加乘原理、排列组合、容斥原理等．我们先来做一个简单的小结和复习．

枚举法是万能的方法，只要有足够多的时间和精力．并且往往在一些复杂棘手的题目中，别的方法都不能适用，此时就能体会到枚举法的“威力”．使用枚举法时一定要注意有序思考．

加法原理强调的是分类，计数时我们只需选择其中的某一类即可以满足要求，类与类之间可以相互替代．

乘法原理强调的是分步，每一步只是整个事情的一部分，必须全部完成才能满足结论，缺一不可．在乘法原理中，步骤顺序的安排往往非常重要．

排列与组合：排列的计算公式由乘法原理推导而来，组合的计算公式由排列公式推导而来．

从n个不同的元素中取出m个（ ），并按照一定的顺序排成一列，其方法数叫做从n个不同元素中取出m个的排列数，记作 ．

从n个不同元素中取出m个（ ）作为一组（不计顺序），可选择的方法数叫做从n个不同元素中取出m个的组合数，记作 ．

_{在运用排列组合时，有特殊要求的我们往往优先考虑，有时还会用到“捆绑法”和“插空法”}.

我们今天主要来学习计数中的分类思想，以及正面分类和反面排除的合理选择．

分类讨论是一种重要的数学思想方法，当问题所给对象不能进行统一研究时，就需要对研究的对象进行分类，将整体问题划分为局部问题，把复杂问题转化为单一问题，然后分而治之、各个击破，最后综合各类的结果得到整个问题的解答．

例题1．

五张卡片上分别写有0、1、2、3、5，每张卡片各用一次可以组成一些五位数．其中5的倍数有多少个？4的倍数有多少个？

分析：一个数是5的倍数，它要满足什么条件？4的倍数呢？



练习1．

五张卡片上分别写有0、1、2、3、5，每张卡片只能用一次可以组成多少个三位偶数？

例题2．

（1）用2个1、2个2和1个3可以组成多少个不同的五位数？
（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有某些相同的特点，每一个数都是以1为首的四位数，且每个数恰好只有两个数字相同（1112，1222，1122这样的数不算），这样的数共有多少个？

分析：根据题意可知这样的四位数由三种数字组成，其中有一种数字出现了2次．那么可以根据这个数字所在的数位来分类．

练习3．

用1、2、3、4这4个数字组成四位数，至多允许有1个数字重复一次．例如1234、1233和2434是满足条件的，而1212、3331和4444就是不满足条件的．那么，所有这样的四位数共有多少个？

例题4

和2468相加至少会发生一次进位的四位数有多少个？

分析：和2486相加发生进位有好多种情况，比如发生一次进位、发生两次进位、发生三次进位等等，不同的类型太多了．这时不妨考虑下反面．

练习4．

和250相加至少会发生一次进位的三位数有多少个？

例题5．

有10名外语翻译，其中5名是英语翻译，4名日语翻译，另外1名英语和日语都很精通，从中找出7人，使他们可以组成两个翻译小组，其中4人翻译英语，另3人翻译日语，这两个小组能同时工作，则不同的分配方案共有多少种？

分析：这个英语和日语都很精通的人很麻烦，应该优先考虑他．

例题6．

将 右图中的“○”分别用四种颜色染色，只要求有实线段连接的两个相邻的“○”都涂成不同的颜色，共有多少种涂法？如果还要求虚线段连接的两个“○”也涂成不同的颜色，共有多少种涂法？

分析：染色时顺序很重要，要遵循“前不影响后”的原则．

四色定理

四色定理指出每个可以画出来的无飞地地图（飞地是指与本土不相连的土地）都可以至多用4种颜色来上色，而且没有两个相邻的区域会是相同的颜色．被称为相邻的两个区域是指它们共有一段边界，而不是一个点．

这一定理最初是由Francis Guthrie在1853年提出的猜想．很明显，3种颜色不会满足条件，而且也不难证明5种颜色满足条件且绰绰有余．但是，直到1977年四色猜想才最终由Kenneth Appel 和Wolfgang Haken证明．他们得到了J. Koch在算法工作上的支持．

证明方法将地图上的无限种可能情况减少为1,936种状态（稍后减少为1,476种），这些状态由计算机一个挨一个的进行检查．这一工作由不同的程序和计算机独立的进行了复检．在1996年，Neil Robertson、Daniel Sanders、Paul Seymour和Robin Thomas使用了一种类似的证明方法，检查了633种特殊的情况．这一新证明也使用了计算机，如果由人工来检查的话是不切实际的．

四色定理是第一个主要由计算机证明的理论，这一证明并不被所有的数学家接受，因为它不能由人工直接验证．最终，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任．参见实验数学．

缺乏数学应有的规范成为了另一个方面；以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本电话簿！”

虽然四色定理证明了任何地图可以只用四种颜色着色，但是这个结论对于现实中的应用却相当有限．现实中的地图常会出现飞地，即两个不相连的土地属于同一个国家的情况（例如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，四个颜色将会是不够用的．

1. 计算：（1） _________； （2） _________；
   （3） _________； （4） _________．

2. 王老师家装修新房，需要2个木匠和2个电工．现有木匠3人、电工4人，另有1人既能做木匠也能做电工．要从这8人中挑选出4人完成这项工作，共有多少种不同的选法？

3. 用2个3、3个1和1个0可以组成多少个不同的六位数？

4. 用2个5、1个2和1个0可以组成多少个不同的三位数？

5. 与1357相加会发生进位的四位数有多少个？