排列与组合中的涂色问题例析

1、排列与组合中的涂色问题例析北京师大燕化附中（102500） 钱月华 史树德在排列与组合的练习、检测和高考试题中，近年来多次出现了某些涂色问题。拨云破雾、还其本来面目，实质是用分类或分步计数原理导航，通过深入缜密分析题意，将原题化归成熟悉的排列、组合或其综合题型、逐类分步推理求解。一、 带状区域的涂色题 带状区域的涂色问题的解法，与推导排列数公式的思想方法类似，可构造排好顺序的个空位（格），从n个不同元素中任取（）个填充.此类涂色题一般可转化成有限制条件的排列或组合问题.例1 用红黄绿三种颜色给图1的5个带状格子涂色.要求每格涂一种颜色、且相邻格子不能图同一种颜色，共有多少种不同的涂法？ 解析：

2、从满足一格一颜色、邻格不同色的限制条件入手，分成三类：一类是左边三个邻格从红黄绿中任取3色涂法有种，且右面两相邻格涂法有种.共有种. 二类是左起4格涂成红绿红绿的类似模式有种，末一格涂法有种，共有种.三类是左起4格涂成红绿红黄的类似模式有种，其中产生与一类重复的有6种（如红绿红黄绿与一类的红绿红黄绿）.综上得：（种）.点评：本例由03年全国高考试题改稿而成，形异质同，也可先排在左起2格，再排第3格、4格、5格、采用逐类相加的解法。例2 用4种不同颜色给图1的5个格子涂色，要求每个格涂一种颜色，若涂完后同颜色的格子恰有3个，则有多少种不同涂色方法？解析：首先考虑同色的三个格子排列法有种，且任选4

3、种颜色之一涂色，共有4种。第二步，将已涂色的三格视为一个整体与未涂色两格作全排列有种，共有(4) =240种。点评：注意到题中没有相邻两格不同色的约束条件，放宽要求后使问题解法简化，某同学列出算式时否？为什么？例3 用6种不同的颜色给图2的4个格子涂色，每个格子涂一种颜色，要求最多使用3种颜色且相邻的两个格子不同色，不同的涂色方法共有多少种？（07天津市理科高考16题） 图2解析：题中最多使用3种颜色的言外之意是最少使用2种颜色（用1种颜色不合题意），启示我们把解法分成两类：一类是用2种颜色涂有种选法，满足相邻格异色、一个一色的4个格子涂法有种，共有=30种。二类是用3种颜色涂法有种选法，满足

4、题意的3个格子涂法有种，且另一格可用余下3种颜色之一， 有种法，共有=360种。综上，所求涂色方法总共有390种。点评：选定颜色后，也可按格涂色分步，根据计数原理解答，请你试解07天津市文科高考16题：（表示理科题两逗号前内容），要求相邻两个格子颜色不同，且两端格子的颜色也不同，则不同的涂色方法共有多少种？（答题630，参考算式（+9）二、分割四边形后区域涂色题四边形的对角线或平行于一边与另两条邻边相交的战线都解把常见的四边形分割成有公共顶点和公共边的几个三角形或四边形，可从一对共顶点、无公共边的上述图形可涂同或异色着手突破，在解决类似的一对图形的涂色。例4 用4种不同的颜色给4个格子组成的图

5、3各区域涂色。要求每个格子涂一种颜色，有公共边的两格子不同色，共有多少种不同的涂法？图3解析：根据图3的结构特点，可以从1、3区域的涂色探求，一类是这时有一公共顶点的格子同颜色有种涂法，且2、4区域格子涂法有（+）=36种，二类是1、3区域涂异色有种涂法，且2、4区域有（+）种。有（+）=48种。综上总共有84种涂法。点评：本例特色是各类中分步计数推算，应弄懂两类中、的含义。若用4种不同颜色给图3的1、2、3区域格子涂色（4格不涂），要求同例4，共有多少种不同涂法？（提示：1、3格只需与2格区域不同色，答题：36）例5 用5种不同的颜色给图4中4个三角形区域涂色，要求每个区域涂一种颜色、且有公

6、共边的区域不同色，则共有多少种不同涂法？ 图4解析：根据标有序号的三角形区域涂色种数研思，可分成三类。（1） 四个区域都涂不同颜色，有=120种涂法。（2） 共顶点的三角形1、3区域涂同色有种，且2、4区域不同色的涂法有种，共有种。同理可求2、4区域同色，1、3区域异色的涂法种数，共有2=120种.（3） 当1、3区域，2、4区域各任染不同的颜色时，有涂法=20种。综上，总共有涂法260种。点评：分类的标准是用几种颜色，除去各区域异色，允许何条件下同区域同色？请看与本例殊途同归的问题：直线y=x把图-x+y=9分成四个区域，要求（以下同例5，略）.三、曲线或空间图形的涂色题圆或椭圆时曲线内分区

7、域涂色题，应想方设法将其化归成带状或四边形分割后区域涂色问题解决，空间图形表面或点涂色题，可化成各侧面或底面的平面图形探索，再采用通性通法处理.例6 某市在中心广场建造一个花圃，花圃分为6个部分（如图5-1），现要栽种4种不同颜色的花，要求每部分栽种一种、且相邻部分不能栽种同颜色的花，则不同的栽种方法有多少种？图5-1解析：先排中心的1区，有种方法.把其余5个区视为一个圆环，沿其一个边界剪开拉直，得图5-2在5个格子中图5-2放入三种异色的花，要求邻格花异色且两段花色不同，共有15种方法，然后将此图粘成圆环，为解决两端花色相同情况，设想图5-3有6个格子，要求邻格花异色且两端花色相同也有15放

8、法，后将此图粘成圆环，且把两端两格重合在一起，综上共有(15+15)=120种. 图5-3点评：有人解此题列出算式*5，你能给出合理地解释吗？本题由03年全国高考题改编而成，变换图5-1，你能将例6重写成地图的区域涂色问题吗？例7 用5种不同颜色给四棱锥S-ABCD的每一个顶点涂色，要求同一条冷的两端点颜色不同，共有多少种不同的涂色方法？ 图6解：先从一个侧面地剖析起步，设点S、A、B异色（如图6），有种涂法，第二步确认点C、D的涂法，不妨设点S、A、B涂色为红、黄、蓝，若点C涂绿色，则点D涂蓝、灰色，有2种涂法，若点C涂灰色，同理点D有2种涂法，累计有7种涂法，根据分布计数原理，共有涂法7=420种.点评：以上