第十二讲 乘法原理进阶

在之前我们学习了“加法原理与乘法原理”一讲，即分类相加与分步相乘的思想．

如果完成一件事分为几个步骤，在每一个步骤中又有不同的方法，那么把每步的方法数相乘就得到所有的方法数——这就是乘法原理．

要想把过程分成几个步骤从而应用乘法原理，必须保证各步骤之间满足下面两个要求：

1. 每步都只是整件事情的一个部分，必须全部完成才算做完这件事；

2. 步骤之间要有先后顺序，先确定好一步，再做下一步，……直到最后．

那么是不是只要分步骤完成整件事情就可以直接用乘法原理呢？

如下图，把A、B、C三部分用三种不同的颜色染色，要求相邻两部分不能同色，那么一共有多少种不同的染法呢？

其实，整个染色过程是需要分为三步的，即分别给其中一块染色：

当染色顺序为A→B→C时，那么A有3种染法，B不能和A一样，有2种染法，同样C有2种，那么一共就有“ ”种染法；（C→B→A同理）

当染色顺序为B→A→C时，那么B有3种染法，A不能和B一样，有2种染法，同样C有2种，那么一共就有“ ”种染法；（B→C→A同理）

当染色顺序为A→C→B时，那么A有3种染法，第二步C没有限制，也有3种染法，但是最后的B就出问题了，我们没法确定它有2种还是1种染法——如果C和A同色，则B有2种染法；如果C和A不同色，则B只有1种染法——此时，根据分步相乘的思想计算整个过程的染色方法“ ”就不再适用了．（C→A→B同理）

因此，并不是只要分步完成整件事情就一定可以应用乘法原理，要想应用乘法原理，还必须满足第三个要求：

3. 做完一步时，这一步的结果很可能会影响后面步骤的结果，但一定不能影响后面步骤的方法数．如果这一步的不同结果会导致后面某一步的方法数发生变化，就不能直接用乘法原理计算．
   ——简称“前不影响后原则”

染色问题，是应用乘法原理最常见的一类题型，其实，从上面对A、B、C三部分的染色分析我们应该可以发现，染色的时候，要尽量避免“隔”着染，一定不要“跳”着染，而且，第一步要尽量去染“接触最多”的那一部分，这样，才能够使得后面的染色过程尽量避开“前影响后”．

例题1

如 图，把A、B、C、D、E这五部分用4种不同的颜色染色，且相邻的部分不能使用同一种颜色．请问：这幅图共有多少种不同的染色方法？

「分析」分五步染色，先染哪一块呢？能否按照A、B、C、D、E的顺序染呢？

练习1

如 图，把A、B、C、D这四部分用4种不同的颜色染色，且相邻的部分不能使用同一种颜色．请问：这幅图共有多少种不同的染色方法？

例题2

某市实行垃圾分类处理．每个地方放置五个垃圾桶，从左向右依次标明：电池、塑料、废纸、易拉罐、其它．现在准备把五个垃圾桶染成红、绿、蓝这3种颜色之一．

（1）要求相邻两个垃圾桶颜色不同，一共有多少种染色方法？

（2）要求相邻两个垃圾桶颜色不同且回收易拉罐的垃圾桶不能染成红色，一共有多少种染色方法？

「分析」如果我们先染废纸垃圾桶：当它染红色时，回收易拉罐的垃圾桶可以染绿、蓝两种颜色；而当它染绿色（蓝色）时，回收废纸的垃圾桶只能染蓝色（绿色）．因此先染废纸垃圾桶时，会影响易拉罐垃圾桶的染色方法数，就不能直接用乘法原理计算了．那么我们应该先给哪个垃圾桶染色呢？

练习2

麦兜很挑食，只吃带有鱼丸或粗面的搭配．一天它和3位同学来餐厅吃东西，一开口就要鱼丸粗面，结果老板说没有．这个时候，由于时间太晚，餐厅快打烊了，只能做牛肚河粉，鱼丸油面，猪肉米线和牛肉拉面各一份，请问它们四只猪各点一份，有几种点法？

在例题2中，有一个垃圾桶是有特殊要求的——易拉罐垃圾桶不能染成红色，我们通过尝试可知：如果一开始先染其他的垃圾桶，那么前面垃圾桶的染色方法就会影响到易拉罐垃圾桶的染色方法数，即不能满足“前不影响后”原则，而如果首先染易拉罐垃圾桶，则不会出现该问题，所以一般而言，如果题目中有些对象是有特殊要求的，那么我们分步分析计算的时候，首先要考虑这些特殊的对象．

例题3

卡莉娅、墨莫、小高和大头4名同学竞选班委．有班长、学习委员、生活委员三个职位，每个人只能担任一个职位，并且每个职位只能由一个人担任．
（1）有多少种可能的选举结果？
（2）如果班长必须由卡莉娅来担任，有多少种可能的选举结果？
（3）如果生活委员只能在墨莫和大头之中选，有多少种可能的选举结果？
（4）如果学习委员不能由小高担任，有多少种可能的选举结果？

「分析」可以按照职位一一确定，第（2）问中，班长只能由卡莉娅来担任，那么先确定哪一个职位的人选呢？其他小问呢？

练习3

甲、乙、丙、丁、戊5个人竞选班委．有班长、副班长、纪律委员、卫生委员四个职位，每个人只能担任一个职位，并且每个职位只能由一个人担任：请问：（1）一共有多少种可能的选举结果？（2）如果副班长只能在甲、丁和戊中选，有多少种可能的选举结果？（3）如果卫生委员不能由乙、丙担任，有多少种可能的选举结果？

例题4

甲、乙、丙、丁四个人要住进A、B、C、D四间房间，每个房间住一个人．其中甲不住A房间，丙只住D房间．请问：这四个人住进四个房间有多少种住法？

「分析」本题中甲和丙有特殊要求，我们应该先考虑甲还是丙呢？

练习4

甲、乙、丙、丁四个人要住进A、B、C、D四间房间，每个房间住一个人．其中甲只住A或B房间，丙只住A、B或C房间．请问：这四个人住进四个房间有多少种住法？

例题5

甲、乙、丙、丁、戊五人要驾驶A、B、C、D、E这五辆不同型号的汽车，请计算在下列情况下，分别共有多少种不同的安排方案：
（1）只有甲能开汽车A，乙不会开汽车B；
（2）会开A的只有甲和乙，会开E的只有甲、乙、丙．

「分析」第（1）问中，甲和丙两人有特殊要求，我们应该先考虑哪一个人呢？第（2）问中，A和E两车有特殊要求，我们应该先考虑哪辆车呢?

接下来我们分析一下“放相同棋子”的问题．

如 右图，将2枚相同的棋子放入2×2的方格内，每个格子只能放1枚，且要求每行每列最多只能放1枚，那么一共会有几种方法呢？

其实，要把两枚相同的棋子放进格子内，只需要选出两个格子即可，然后每个格子里放一枚棋子．

一共有两行，所以必定会是每行一枚，所以我们完全可以分行选格子，第一行有两种选法，第一行选好后，第二行就只有一种选法了，所以一共有2×1=2种．

例题6

右图是一个阶梯形方格表，在方格中放入五枚相同的棋

子，使得每行、每列中都只有一枚棋子，这样的放法共有多少种？

「分析」容易看出，每行只能有1枚棋子，每列也只能由一枚棋子，我们可以把放五枚棋子的过程分成五步：一行一行或一列一列的放．

课堂内外

四色定理

四 色定理与费马大定理、哥德巴赫猜想并称为近代数学三大难题．

四色定理的内容是：对于任何一张地图，只用四种颜色，就可以把有相邻边界的国家染上不同的颜色．

四色问题的提出来自英国．1852年，在大学读书的格
斯里向他的老师——著名数学家摩根提出了这个问题，摩根没有能找到解决这个问题的途径．

“四色问题”提出以后，最初并没有引起广泛的重视，许多数学家低估了它的难度．就连素以谦虚著称的德国数论专家闵可夫斯基在大学上拓扑课时也说：四色问题之所以一直没有获得解决，那仅仅是由于没有一流的数学家来解决它．说罢，他拿起粉笔，竟要当堂给学生推导出来，结果没有成功．下一节课他又去试，还是没有成功．过了几个星期，仍无进展．有一天，他刚跨进教室，适逢天上雷声大作，震耳欲聋．他马上对学生说：“上天在责备我自大，我也无法解决四色问题．”这样，四色问题就成了世界最著名的问题之一．l00多年中，“四色问题”使数学家们深为困扰．没有人能证明它，也没有人推翻它．

电 子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了四色猜想的证明进程．

就在1976年6月，哈肯与阿佩尔在美国伊利诺斯大学
的两台不同的电子计算机上，用了1200个小时，作了
100亿次判断，终于完成了四色定理的证明，
轰动了世界．

作业

1. 五个座位排成一排，小高、墨莫、萱萱、阿呆、阿瓜每人选一个座位坐下，其中每个座位只能坐一个人，且萱萱不坐在中间的位置．这五个人有多少种坐法？
   
   
   

2. 如图，把A、B、C这三部分用4种不同的颜色染色，且相邻的部分不能使用同一种颜色．请问，这幅图共有多少种不同的染色方法？
   
   
   

3. 把A、B、C、D、E这五部分用4种不同的颜色染色，且相邻的部分不能使用同一种颜色．这幅图共有多少种不同的染色方法？（96）
   
   
   

4. 甲、乙、丙、丁四个人排成一队，甲不当排头，乙不当排头也不当排尾，共有多少种不同的排法？
   
   
   
   

5. 在 的方格中放入两枚相同的棋子，要求两枚棋子既不在同一行也不在同一列，共有多少种放法？