排列与组合中的涂色问题例析
在排列与组合的练习、检测和高考试题中,近年来多次出现了某些涂色问题。拨云破雾、还其本来面目,实质是用分类或分步计数原理导航,通过深入缜密分析题意,将原题化归成熟悉的排列、组合或其综合题型、逐类分步推理求解。
一、 带状区域的涂色题
带状区域的涂色问题的解法,与推导排列数公式m n A 的思想方法类似,可构
造排好顺序的m 个空位(格),从n 个不同元素中任取m (n m ≤)个填充.此类涂色题一般可转化成有限制条件的排列或组合问题.
例1 用红黄绿三种颜色给图1的5个带状格子涂色.要求每格涂一种颜色、且相邻格子不能图同一种颜色,共有多少种不同的涂法?
解析:从满足一格一颜色、邻格不同色的限制条件入手,分成三类:
一类是左边三个邻格从红黄绿中任取3色涂法有33A 种,且右面两相邻格涂
法有12A 种.共有121233=?A A 种.
二类是左起4格涂成红绿红绿的类似模式有33A 种,末一格涂法有12A 种,共
有121233=?A A 种.
三类是左起4格涂成红绿红黄的类似模式有44A 种,其中产生与一类重复的
有6种(如红绿红黄绿与一类的红绿红黄绿).
综上得:42)6(4412331233=-++A A A A A (种).
点评:本例由03年全国高考试题改稿而成,形异质同,也可先排在左起2格,再排第3格、4格、5格、采用逐类相加的解法。
例2 用4种不同颜色给图1的5个格子涂色,要求每个格涂一种颜色,若涂完后同颜色的格子恰有3个,则有多少种不同涂色方法?
解析:首先考虑同色的三个格子排列法有35C 种,且任选4种颜色之一涂色,
共有35C 4种。第二步,将已涂色的三格视为一个整体与未涂色两格作全排列有33
A 种,共有(35C ?4) ?33
A =240种。 点评:注意到题中没有相邻两格不同色的约束条件,放宽要求后使问题解法
简化,某同学列出算式35C 34
A 时否?为什么? 例3 用6种不同的颜色给图2的4个格子涂色,每个格子涂一种颜色,要
求最多使用3种颜色且相邻的两个格子不同色,不同的涂色方法共有多少种?(07天津市理科高考16
题)
图2
解析:题中最多使用3种颜色的言外之意是最少使用2种颜色(用1种颜色不合题意),启示我们把解法分成两类:
一类是用2种颜色涂有26C 种选法,满足相邻格异色、一个一色的4个格子
涂法有22A 种,共有26C 22
A =30种。 二类是用3种颜色涂法有36C 种选法,满足题意的3个格子涂法有33A 种,且
另一格可用余下3种颜色之一, 有13A 种法,共有36C 33A 13
A =360种。 综上,所求涂色方法总共有390种。
点评:选定颜色后,也可按格涂色分步,根据计数原理解答,请你试解07天津市文科高考16题:……(表示理科题两逗号前内容),要求相邻两个格子颜色不同,且两端格子的颜色也不同,则不同的涂色方法共有多少种?(答题630,
参考算式26A (24A +9))
二、分割四边形后区域涂色题
四边形的对角线或平行于一边与另两条邻边相交的战线都解把常见的四边形分割成有公共顶点和公共边的几个三角形或四边形,可从一对共顶点、无公共边的上述图形可涂同或异色着手突破,在解决类似的一对图形的涂色。
例4 用4种不同的颜色给4个格子组成的图3各区域涂色。要求每个格子涂一种颜色,有公共边的两格子不同色,共有多少种不同的涂法?
解析:根据图3的结构特点,可以从1、3区域的涂色探求,一类是这时有一公共顶点的格子同颜色有14A 种涂法,且2、4
区域格子涂法有14A (1
3A +23A )=36种,二类是1、3区域涂异色有2
4A 种涂法,且2、4区域有(12A +22A )种。有24A (12A +22A )=48种。综上总共有84种涂法。
点评:本例特色是各类中分步计数推算,应弄懂两类中23A 、2
2A 的含义。若
用4种不同颜色给图3的1、2、3区域格子涂色(4格不涂),要求同例4,共有多少种不同涂法?(提示:1、3格只需与2格区域不同色,答题:36)
例5 用5种不同的颜色给图4中4个三角形区域涂色,要求每个区域涂一种颜色、且有公共边的区域不同色,则共有多少种不同涂法?
图4
解析:根据标有序号的三角形区域涂色种数研思,可分成三类。
(1) 四个区域都涂不同颜色,有45A =120种涂法。
(2) 共顶点的三角形1、3区域涂同色有15A 种,且2、4区域不同色的涂
法有24A 种,共有24
15A A ?种。同理可求2、4区域同色,1、3区域异色的涂法种数,共有224
15A A ?=120种. (3) 当1、3区域,2、4区域各任染不同的颜色时,有涂法25A =20种。 综上,总共有涂法260种。
点评:分类的标准是用几种颜色,除去各区域异色,允许何条件下同区域同色?请看与本例殊途同归的问题:直线y=±x 把图-x 2+y 2=9分成四个区域,要求(以下同例5,略).
三、曲线或空间图形的涂色题
圆或椭圆时曲线内分区域涂色题,应想方设法将其化归成带状或四边形分割后区域涂色问题解决,空间图形表面或点涂色题,可化成各侧面或底面的平面图形探索,再采用通性通法处理.
例6 某市在中心广场建造一个花圃,花圃分为6个部分(如图5-1),现要栽种4种不同颜色的花,要求每部分栽种一种、且相邻部分不能栽种同颜色
的花,则不同的栽种方法有多少种?
图5-1 解析:先排中心的1区,有14A 种方法.把其余5个区视为一个圆环,沿其一
A B C 个边界剪开拉直,得图5-2在5
个格子中
图5-2
放入三种异色的花,要求邻格花异色且两段花色不同,共有15种方法,然后将此图粘成圆环,为解决两端花色相同情况,设想图5-3有6个格子,要求邻格花异色且两端花色相同也有15放法,后将此图粘成圆环,且把两端两格重合在一
起,综上共有14A (15+15)=120种
.
图5-3
点评:有人解此题列出算式34A *5,你能给出合理地解释吗?本题由03年全国高
考题改编而成,变换图5-1,你能将例6重写成地图的区域涂色问题吗?
例7 用5种不同颜色给四棱锥S-ABCD 的每一个顶点涂色,要求同一条冷的两端点颜色不同,共有多少种不同的涂色方法?
解:先从一个侧面地剖析起步,设点S 、A 、B 异色(如图6),有35A 种 C 、D 的涂法,不妨设点S 、A 、B 涂色为红、
C 涂绿色,则点
D 涂蓝、灰色,有2种涂法,若
D 有2种涂法,累计有7种涂法,根据
35A 7=420种. .研讨和分析这类涂色问关键是细心审核和识别诸元素如位置(区域或
点),颜色种类等的依存关系,或按问题中元素的互斥(异色)分类,或根据事件发生的前因后果、连续过程分布,结合排列与组合应用问题的特点,有理有据、全面妥善地敲定解题思路和方法.