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

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

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

3、子涂色，要求每个格涂一种颜色，若 涂完后同颜色的格子恰有3个，则有多少种不同涂色方法？解析：首先考虑同色的三个格子排列法有 C53种，且任选4种颜色之一涂色， 共有C；4种。第二步，将已涂色的三格视为一个整体与未涂色两格作全排列有 A3 种，共有（C； *4） Af =240种。点评：注意到题中没有相邻两格不同色的约束条件，放宽要求后使问题解法简化，某同学列出算式C；A：时否？为什么？例3用6种不同的颜色给图2的4个格子涂色，每个格子涂一种颜色，要 求最多使用3种颜色且相邻的两个格子不同色，不同的涂色方法共有多少种？（07天津市理科高考16题）解析：题中最多使用3种颜色的言外之意是最少使用2种

4、颜色（用1种颜色不合题意），启示我们把解法分成两类:一类是用2种颜色涂有C；种选法，满足相邻格异色、一个一色的4个格子涂法有A种，共有d A =30种二类是用3种颜色涂法有C63种选法，满足题意的3个格子涂法有A；种，且另一格可用余下3种颜色之一， 有A3种法，共有C；A；a3=360种。综上，所求涂色方法总共有390种。点评：选定颜色后，也可按格涂色分步，根据计数原理解答，请你试解07天津市文科高考16题：（表示理科题两逗号前内容），要求相邻两个格子颜 色不同，且两端格子的颜色也不同，则不同的涂色方法共有多少种？（答题630, 参考算式A（ A4+9）二、分割四边形后区域涂色题四边形的对角线

5、或平行于一边与另两条邻边相交的战线都解把常见的四边 形分割成有公共顶点和公共边的几个三角形或四边形，可从一对共顶点、无公共 边的上述图形可涂同或异色着手突破，在解决类似的一对图形的涂色。例4用4种不同的颜色给4个格子组成的图3各区域涂色。要求每个格子 涂一种颜色，有公共边的两格子不同色，共有多少种不同的涂法？解析：根据图3的结构特点，可以从1、3区域的涂色探求，一类是这时有 一公共顶点的格子同颜色有 A；种涂法，且2、4区域格子涂法有a4 （ A；+A；）=36种，二类是1、3区域涂异色有A2种涂法，且2、4区域有（A2 + A2 ）种 有A2 （ A2+A2） =48种。综上总共有84种涂法

6、。点评：本例特色是各类中分步计数推算，应弄懂两类中 Af、a2的含义。若 用4种不同颜色给图3的1、2、3区域格子涂色（4格不涂），要求同例4,共有 多少种不同涂法？（提示：1、3格只需与2格区域不同色，答题：36）例5用5种不同的颜色给图4中4个三角形区域涂色，要求每个区域涂一 种颜色、且有公共边的区域不同色，则共有多少种不同涂法？解析：根据标有序号的三角形区域涂色种数研思，可分成三类。（1）四个区域都涂不同颜色，有 A；=120种涂法。（2）共顶点的三角形1、3区域涂同色有A种，且2、4区域不同色的涂 法有A：种，共有a5 A4种。同理可求2、4区域同色，1、3区域异色 的涂法种数，共有2

7、A5，A：=120种.（3） 当1、3区域，2、4区域各任染不同的颜色时，有涂法 A5=20种。综上，总共有涂法260种。点评：分类的标准是用几种颜色，除去各区域异色，允许何条件下同区域同 色？请看与本例殊途同归的问题：直线y=_x把图-x 2 +y2 =9分成四个区域， 要求（以下同例5,略）.三、曲线或空间图形的涂色题圆或椭圆时曲线内分区域涂色题，应想方设法将其化归成带状或四边形分割后区域涂色问题解决，空间图形表面或点涂色题，可化成各侧面或底面的平 面图形探索，再采用通性通法处理例6某市在中心广场建造一个花圃，花圃分为 6个部分（如图5-1），现要 栽种4种不同颜色的花，要求每部分栽种一种

8、、且相邻部分不能栽种同颜色45的花，则不同的栽种方法有多少种?图5-1解析：先排中心的1区，有A；种方法.把其余5个区视为一个圆环，沿其个边界剪开拉直，得图5-2在5个格子中*L 1L4J)图5-2放入三种异色的花，要求邻格花异色且两段花色不同，共有 15种方法，然后将 此图粘成圆环，为解决两端花色相同情况，设想图5-3有6个格子，要求邻格花 异色且两端花色相同也有15放法，后将此图粘成圆环，且把两端两格重合在一起，综上共有A4（15+15）=120种.图5-3点评：有人解此题列出算式A：*5，你能给出合理地解释吗？本题由03年全国高 考题改编而成，变换图5-1，你能将例6重写成地图的区域涂色问题吗？例7用5种不同颜色给四棱锥S-ABCD勺每一个顶点涂色，要求同一条冷的两端点颜色不同，共有多少种不同的涂色方法？图6解：先从一个侧面地剖析起步，设点 S、A B异色（如图6），有A种涂法，第 二步确认点C、D的涂法，不妨设点S、A B涂色为红、黄、蓝，若点C涂绿色, 则点D涂蓝、灰色，有2种涂法，若点C涂灰色，同理点D有2种涂法，累计有7种涂法，根据分布计数原理，共有涂法A； 7=420