列组合中涂色问题的常见方法及策略[1]
解决排列组合中涂色问题的常见方法及策略
于涂色问题有关的试题新颖有趣, 其中包含着丰富的数学思想。解决涂色问题方法技巧性强且灵活多变,故这类问题的利于培养学生的创新思维能力、分析问题与观察问题的能力,有利于开发学生的智力。本文拟总结涂色问题的常见类型及求解方法。
一、区域涂色问题
1、 根据分步计数原理,对各个区域分步涂色,这是处理染色问题的基本方法。 例1、 用5种不同的颜色给图中标①、②、③、④的各部分涂色,每部分只涂一种
颜色,相邻部分涂不同颜色,则不同的涂色方法有多少种?
分析:先给①号区域涂色有5种方法,再给②号涂色有4种方法,接着给③号涂色方法有3种,由于④号与①、②不相邻,因此④号有4种涂法,根据分步计数原理,不同的涂色方法有5⨯4⨯3⨯4=240
2、 根据共用了多少种颜色讨论,分别计算出各种出各种情形的种数,再用加法原理求出不同的涂色方法种数。
例2、(2003江苏卷)四种不同的颜色涂在如图所示的6个区域,且相邻两个区域不能同色。
分析:依题意只能选用4种颜色,要分四类:
4(1)②与⑤同色、④与⑥同色,则有A 4; ⑤
⑥
① ④ (2)③与⑤同色、④与⑥同色,则有A ;
(3)②与⑤同色、③与⑥同色,则有A ; 4
444
44(4)③与⑤同色、② 与④同色,则有A 4;(5)②与④同色、③与⑥同色,则有A 4;
4所以根据加法原理得涂色方法总数为5A 4=120
例3、(2003年全国高考题)如图所示,一个地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有4种颜色可供选择,则不同的着方法共有多少种? 分析:依题意至少要用3种颜色
1) 当先用三种颜色时,区域2与4必须同色, 2) 区域3与5必须同色,故有A 4种;
3
3) 当用四种颜色时,若区域2与4同色,
44) 则区域3与5不同色,有A 4种;若区域3与5同色,则区域2与4不同色,
44有A 4种,故用四种颜色时共有2A 4种。由加法原理可知满足题意的着色方
34法共有A 4+2A 4=24+2⨯24=72
3、 根据某两个不相邻区域是否同色分类讨论,从某两个不相邻区域同色与不同色入
手,分别计算出两种情形的种数,再用加法原理求出不同涂色方法总数。
例4用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内,每个区域涂一种颜色,相邻两个区域涂不同的颜色,如果颜色可以反复使用,共有多少种不同的涂色方法?
分析:可把问题分为三类: 4(1) 四格涂不同的颜色,方法种数为A 5;
(2) 有且仅两个区域相同的颜色,即只
122
C 5A 4;
25) 两组对角小方格分别涂相同的颜色,涂法种数为A 5,
2122因此,所求的涂法种数为A 5+2C 5A 4+A 5=260 4、 根据相间区使用颜色的种类分类
例5如图, 6个扇形区域A 、B 、C 、D 、E 、F ,现给这6个区域着色,要求同一区域涂同一种颜色,相邻的两个区域不得使用同一种颜色,现有4种不同的颜色可A 1解(1)当相间区域A 、C 、E 着同一种颜色时,
有4种着色方法,此时,B 、D 、F 各有3种着色方法,
此时,B 、D 、F 各有3种着色方法故有4⨯3⨯3⨯3=108
种方法。
22 (2)当相间区域A 、C 、E 着色两不同的颜色时,有C 3A 4种着色方法,此时B 、
D 、F 有3⨯2⨯2种着色方法,故共有C 3A 4⨯3⨯2⨯2=432种着色方法。
(3)当相间区域A 、C 、E 着三种不同的颜色时有A 4种着色方法,此时B 、D 、F 各有2种着色方法。此时共有A 4⨯2⨯2⨯2=192种方法。
3322
故总计有108+432+192=732种方法。
说明:关于扇形区域区域涂色问题还可以用数列中的递推公来解决。
如:如图,把一个圆分成n (n ≥2) 个扇形,每个扇形用红、白、蓝、黑四色之一染色,要求相邻扇形不同色,有多少种染色方法?
解:设分成n 个扇形时染色方法为a n 种
2(1) 当n=2时A 1、A 2有A 4=12种,即a 2=12 (2) 当分成n 个扇形,如图,A ,A n -1 A 2与A 3 不同色,1与A 2不同色,
与A n 不同色,共有4⨯3n -1种染色方法, 但由于A n 与A 所以应排除A n 与A 1邻,1
n -2个扇形加在一起为同色的情形;A n 与A 1同色时,可把A n 、 A 1看成一个扇形,与前
n -1个扇形,此时有a n -1种染色法,故有如下递推关系:
a n =4⨯3n -1-a n -1
∴a n =-a n -1+4⨯3n -1=-(-a n -2+4⨯3n -2) +4⨯3n -1
2=a n -2-4⨯3n -2+4⨯3n -1=-a n -3+4⨯3n -3-4⨯3n -+4⨯3n -1
==4⨯[3n -1-3n -2+
n n +(-1) n ⨯3]=(-1) ⨯3+3
二、点的涂色问题
方法有:(1)可根据共用了多少种颜色分类讨论,(2)根据相对顶点是否同色分类讨论,(3)将空间问题平面化,转化成区域涂色问题。
例6、将一个四棱锥S -ABCD 的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有5种颜色可供使用,那么不同的染色方法的总数是多少?
解法一:满足题设条件的染色至少要用三种颜色。
(1) 若恰用三种颜色,可先从五种颜色中任选一种染顶点S ,再从余下的
四种颜色中任选两种涂A 、B 、C 、D 四点,此时只能A 与C 、B 与D
分别同色,故有C 5A 4=60种方法。
(2) 若恰用四种颜色染色,可以先从五种颜色中任选一种颜色染顶点S ,
12
再从余下的四种颜色中任选两种染A 与B ,由于A 、B 颜色可以交换,
2故有A 4种染法;再从余下的两种颜色中任选一种染D 或C ,而D 与
C ,而D 与C 中另一个只需染与其相对顶点同色即可,故有
1211C 5A 4C 2C 2=240种方法。
5(3) 若恰用五种颜色染色,有A 5=120种染色法
综上所知,满足题意的染色方法数为60+240+120=420种。
解法二:设想染色按S —A —B —C —D 的顺序进行,对S 、A 、B 染色,有5⨯4⨯3=60种染色方法。
由于C 点的颜色可能与A 同色或不同色,这影响到D 点颜色的选取方法数,故分类讨论:
C 与A 同色时(此时C 对颜色的选取方法唯一),D 应与A (C )、S 不同色,有3种选择;C 与A 不同色时,C 有2种选择的颜色,D 也有2种颜色可供选择,从而对C 、D 染色有1⨯3+2⨯2=7种染色方法。
由乘法原理,总的染色方法是60⨯7=420
解法三:可把这个问题转化成相邻区域不同色问题:如图,
对这五个区域用5种颜色涂色,有多少种不同的涂色方法? 解答略。 三、线段涂色问题
1) 根据共用了多少颜色分类讨论
2) 根据相对线段是否同色分类讨论。
例7、用红、黃、蓝、白四种颜色涂矩形ABCD 的四条边,每条边只涂一种颜色 ,且使相邻两边涂不同的颜色,如果颜色可以反复使用,共有多少种不同的涂色方法?
4解法一:(1)使用四颜色共有A 4种
112 (2)使用三种颜色涂色,则必须将一组对边染成同色,故有C 4 C 2A 3种,
2 (3)使用二种颜色时,则两组对边必须分别同色,有A 4种
因此,所求的染色方法数为A 4+C 4C 2A 3+A 4=84种
解法二:涂色按AB -BC -CD -DA 的顺序进行,对AB 、BC 涂色有4⨯3=12种涂色方法。
由于CD 的颜色可能与AB 同色或不同色,这影响到DA 颜色的选取方法数,故41122
分类讨论:
当CD 与AB 同色时,这时CD 对颜色的选取方法唯一,则DA 有3种颜色可供选择CD 与AB 不同色时,CD 有两种可供选择的颜色,DA 也有两种可供选择的颜色,从而对CD 、DA 涂色有1⨯3+2⨯2=7种涂色方法。
由乘法原理,总的涂色方法数为12⨯7=84种
例8、用六种颜色给正四面体A -BCD 的每条棱染色,要求每条棱只染一种颜色且共顶点的棱涂不同的颜色,问有多少种不同的涂色方法?
解:(1)若恰用三种颜色涂色,则每组对棱必须涂同一颜色,而这三组间的颜色不同,
3故有A 6种方法。
(2)若恰用四种颜色涂色,则三组对棱中有二组对棱的组内对棱涂同色,但组
34与组之间不同色,故有C 6A 6种方法。
15 (3)若恰用五种颜色涂色,则三组对棱中有一组对棱涂同一种颜色,故有C 3A 6
种方法。
6 (4)若恰用六种颜色涂色,则有A 6种不同的方法。
324156 综上,满足题意的总的染色方法数为A 6+C 3A 6+C 3A 6+A 6=4080种。
四、面涂色问题
例9、从给定的六种不同颜色中选用若干种颜色,将一个正方体的6个面涂色,每两个具有公共棱的面涂成不同的颜色,则不同的涂色方案共有多少种?
分析:显然,至少需要3三种颜色,由于有多种不同情况,仍应考虑利用加法原理分类、乘法原理分步进行讨论
解:根据共用多少种不同的颜色分类讨论
(1)用了六种颜色,确定某种颜色所涂面为下底面,则上底颜色可有5种选择,在上、下底已涂好后,再确定其余4种颜色中的某一种所涂面为左侧面,则其余3个面有3!种涂色方案,根据乘法原理n 1=5⨯3! =30
(2)共用五种颜色,选定五种颜色有C 6=6种方法,必有两面同色(必为相对面),确定为上、下底面,其颜色可有5种选择,再确定一种颜色为左侧面,此时的方法数取决于右侧面的颜色,有3种选择(前后面可通过翻转交换)
5n 2=C 6⨯5⨯3=90 5
(3)共用四种颜色, 仿上分析可得
42n 3=C 6C 4=90
3(4)共用三种颜色, n 4=C 6=20
例10、四棱锥P -ABCD ,用4种不同的颜色涂在四棱锥的各个面上,要求相邻不同色,有多少种涂法?
⇒C B
解:这种面的涂色问题可转化为区域涂色问题,如右图,区域1、2、3、4相当于四个侧面,区域5相当于底面;根据共用颜色多少分类:
3(1) 最少要用3种颜色,即1与3同色、2与4同色,此时有A 4种;
14(2) 当用4种颜色时,1与3同色、2与4两组中只能有一组同色,此时有C 2 A 4;
314故满足题意总的涂色方法总方法交总数为A 4+C 2A 4=72
排列与组合中的涂色问题例析
北京师大燕化附中(102500) 钱月华 史树德
在排列与组合的练习、检测和高考试题中,近年来多次出现了某些涂色问题。拨云破雾、还其本来面目,实质是用分类或分步计数原理导航,通过深入缜密分析题意,将原题化归成熟悉的排列、组合或其综合题型、逐类分步推理求解。
一、 带状区域的涂色题
m 带状区域的涂色问题的解法,与推导排列数公式A n 的思想方法类似,可构
造排好顺序的m 个空位(格),从n 个不同元素中任取m (m ≤n )个填充. 此类涂色题一般可转化成有限制条件的排列或组合问题.
例1 用红黄绿三种颜色给图1的5个带状格子涂色. 要求每格涂一种颜
色、且相邻格子不能图同一种颜色,共有多少种不同的涂法?
解析:从满足一格一颜色、邻格不同色的限制条件入手,分成三类:
3一类是左边三个邻格从红黄绿中任取3色涂法有A 3种,且右面两相邻格涂
131法有A 2种. 共有A 3⋅A 2=12种.
1 二类是左起4格涂成红绿红绿的类似模式有A 33种,末一格涂法有A 2种,共
31有A 3⋅A 2=12种.
4三类是左起4格涂成红绿红黄的类似模式有A 4种,其中产生与一类重复的
有6种(如红绿红黄绿与一类的红绿红黄绿).
31314综上得:A 3A 2+A 3A 2+(A 4-6) =42(种).
点评:本例由03年全国高考试题改稿而成,形异质同,也可先排在左起2格,再排第3格、4格、5格、采用逐类相加的解法。
例2 用4种不同颜色给图1的5个格子涂色,要求每个格涂一种颜色,若涂完后同颜色的格子恰有3个,则有多少种不同涂色方法?
3解析:首先考虑同色的三个格子排列法有C 5种,且任选4种颜色之一涂色,
3共有C 54种。第二步,将已涂色的三格视为一个整体与未涂色两格作全排列有333种,共有(C 5=240种。 ∙4) ∙A 3A 3
点评:注意到题中没有相邻两格不同色的约束条件,放宽要求后使问题解
33法简化,某同学列出算式C 5时否?为什么? A 4
例3 用6种不同的颜色给图2的4个格子涂色,每个格子涂一种颜色,要求最多使用3种颜色且相邻的两个格子不同色,不同的涂色方法共有多少种?(07天津市理科高考16题)
图2
解析:题中最多使用3种颜色的言外之意是最少使用2种颜色(用1种颜色不合题意),启示我们把解法分成两类:
2一类是用2种颜色涂有C 6种选法,满足相邻格异色、一个一色的4个格子
222涂法有A 2种,共有C 6=30种。 A 2
33二类是用3种颜色涂法有C 6种选法,满足题意的3个格子涂法有A 3种,
1331且另一格可用余下3种颜色之一, 有A 3种法,共有C 6=360种。 A 3A 3
综上,所求涂色方法总共有390种。
点评:选定颜色后,也可按格涂色分步,根据计数原理解答,请你试解07天津市文科高考16题:……(表示理科题两逗号前内容),要求相邻两个格子颜色不同,且两端格子的颜色也不同,则不同的涂色方法共有多少种?(答题
22630,参考算式A 6(A 4+9))
二、分割四边形后区域涂色题
四边形的对角线或平行于一边与另两条邻边相交的战线都解把常见的四边形分割成有公共顶点和公共边的几个三角形或四边形,可从一对共顶点、无公共边的上述图形可涂同或异色着手突破,在解决类似的一对图形的涂色。
例4 用4种不同的颜色给4个格子组成的图3各区域涂色。要求每个格子涂一种颜色,有公共边的两格子不同色,共有多少种不同的涂法?
图3
解析:根据图3的结构特点,可以从1、3区域的涂色探求,一类是这时有
112一公共顶点的格子同颜色有A 4种涂法,且2、4区域格子涂法有A 4(A 1
3+A 3)
12=36种,二类是1、3区域涂异色有A 2
4种涂法,且2、4区域有(A 2+A 2)种。
12有A 2
4(A 2+A 2)=48种。综上总共有84种涂法。
2点评:本例特色是各类中分步计数推算,应弄懂两类中A 3、A 2
2的含义。
若用4种不同颜色给图3的1、2、3区域格子涂色(4格不涂),要求同例4,共有多少种不同涂法?(提示:1、3格只需与2格区域不同色,答题:36)
例5 用5种不同的颜色给图4中4个三角形区域涂色,要求每个区域涂一种颜色、且有公共边的区域不同色,则共有多少种不同涂法?
图4
解析:根据标有序号的三角形区域涂色种数研思,可分成三类。
(1) 四个区域都涂不同颜色,有A 54=120种涂法。
1(2) 共顶点的三角形1、3区域涂同色有A 5种,且2、4区域不同色的涂
212法有A 4种,共有A 5种。同理可求2、4区域同色,1、3区域异⋅A 4
12色的涂法种数,共有2A 5=120种. ⋅A 4
(3) 当1、3区域,2、4区域各任染不同的颜色时,有涂法A 52=20种。 综上,总共有涂法260种。
点评:分类的标准是用几种颜色,除去各区域异色,允许何条件下同区域同色?请看与本例殊途同归的问题:直线y=±x 把图-x 2+y2=9分成四个区域,要求(以下同例5,略).
三、曲线或空间图形的涂色题
圆或椭圆时曲线内分区域涂色题,应想方设法将其化归成带状或四边形分割后区域涂色问题解决,空间图形表面或点涂色题,可化成各侧面或底面的平面图形探索,再采用通性通法处理.
例6 某市在中心广场建造一个花圃,花圃分为6个部分(如图5-1),现要栽种4种不同颜色的花,要求每部分栽种一种、且相邻部分不能栽种同颜
色的花,则不同的栽种方法有多少种?
图5-1
1解析:先排中心的1区,有A 4种方法. 把其余5个区视为一个圆环,沿其
一个边界剪开拉直,得图5-2在5
个格子中
图5-2
放入三种异色的花,要求邻格花异色且两段花色不同,共有15种方法,然后将此图粘成圆环,为解决两端花色相同情况,设想图5-3有6个格子,要求邻格花异色且两端花色相同也有15放法,后将此图粘成圆环,且把两端两格重合在
1一起,综上共有A 4(15+15)=120种
.
图5-3
3点评:有人解此题列出算式A 4*5,你能给出合理地解释吗?本题由03年全国
高考题改编而成,变换图5-1,你能将例6重写成地图的区域涂色问题吗? 例7 用5种不同颜色给四棱锥S-ABCD 的每一个顶点涂色,要求同一条冷的两端点颜色不同,共有多少种不同的涂色方法?
A
图6
3解:先从一个侧面地剖析起步,设点S 、A 、B 异色(如图6),有A 5种涂法,B C
第二步确认点C 、D 的涂法,不妨设点S 、A 、B 涂色为红、黄、蓝,若点C 涂绿色,则点D 涂蓝、灰色,有2种涂法,若点C 涂灰色,同理点D 有2种涂法,
3累计有7种涂法,根据分布计数原理,共有涂法A 5 7=420种.
点评:以上几例,各具特色. 研讨和分析这类涂色问题的关键是细心审核和识别诸元素如位置(区域或点),颜色种类等的依存关系,或按问题中元素的互斥(异色)分类,或根据事件发生的前因后果、连续过程分布,结合排列与组合应用问题的特点,有理有据、全面妥善地敲定解题思路和方法.
11