例谈涂色问题的常见方法及应对策略
作者： 张海军
“涂色型”的排列组合问题，立意新颖、构思精巧、解法灵活，能较好地考查学生分析问题和解决问题的能力解决涂色问题的方法技巧性强且灵活多变，这类问题更有利于培养学生的创新思维及分析与解决问题的能力，是近几年高考及竞赛试题改革的一个新亮点解决此类问题的关键是找准突破口，进行恰当的分类讨论本文以近几年的高考及竞赛题为例总结涂色问题的常见方法及应对策略
例1（21年天津卷）如图1，用四种不同颜色给图中的A、B、C、D、E、六个点涂色，要求每个点涂一种颜色，且图中每条线段的两个端点涂不同颜色则不同的涂色方法共有种.
解法1按B、、E、D为主分类、分步进行涂色图1
（1）B用四种颜色，则有A必与颜色相同、C与E颜色相同，故有A44×1×1=24种方法.
（2）B、、E、D用三种颜色，则有B、E同色，或D、同色，或B、D同色有且仅有其一成立若B、E同色，则A有两种色可选，而C只有一种色可选，若D、同色，则A有一种色可选，而C有两种色可选，即2×A4×2×1；若B、D同色，则A、C都有两种色可选故有2×A4×2×1+A4×2×2=192种.
（）B、、E、D用二种颜色，只能B、E同色，D、同色，A、C有异于B、D两种色可选，则有A24×2×2=48故共有不同的涂色方法有24+192+48=264种.
解法2按A、B、C、D为主分类、分步进行涂色.
（1）用四种颜色涂ABCD四个点，则E有异于A、D两种颜色，有异于B、C两种颜色，即A44×2×2（2）用三种颜色涂ABCD四个点，则必有A、C或B、D同色，当A、C同色时，E、有三种涂色方法，即2×A4×（）用两种颜色涂ABCD四个点，则A、C同色，B、D同色，E、有两种涂色方法，即A24×A22故共有A44×2×2+2×A4×+A24×A22=264.
解法按总共选用颜色为主分类、分步进行涂色
第一类，三色涂完必然两两同色，即AC，BE，D或A，BD，CE，有2A4=48种；第二类，四色涂完A、D、E肯定不同色，有A4种涂法，再从B、、C中选一位置涂第四色有C1种若所选的是B，则与D同色时C有2中涂法，与D不同色时C有1中涂法，从而有A4・C1・=216种故共有48+216=264种涂法
解法4间接法1（先不考虑A，E，D和B，，C是否有同色点）
A，E，D的涂色一定不同，B，，C的涂色一定不同，先涂A，E，D有A4种方法，再涂B，，C也有A4种方法，所以至多有A4・A4种方法还要去掉A，B同色，E，同色，D，C同色的情况若只有1对同色，不妨A，B同色，若，D同色，C有2种涂法，若，D不同色，C有1种涂法若只有2对同色，不妨A，B同色，E，同色，则C有1种涂法，若，D不同色，C有1种涂法若对同色，只有一种情况故共有A4・A4-A4（C1・+C2・1+1=264种方法
解法间接法2（先不考虑E和是否同色）
先用4种颜色（可以不全用）涂ABCD若A，C同色，则B，D均有种涂法，若A，C
异色，则B，D均有2种涂法故共有C14・C1・C1+A24・C12・C12=84若不考虑E，是否异色，共有（C14・C1・C1+A24・C12・C12・（C12・C12=6还要去掉E，同色的情况，此时E，占一种颜色，同时要用种颜色（可以不全用）涂ABCD若A，C同色，则B，D均有2种涂法，若A，C异色，则B，D均有1种涂法所以E，同色共有C14（C1・C12・C12+A2=72故共有6-72=264种方法
定理1用m种不同颜色给n边形A1A2…An的n个顶点染色（其中m≥，n≥，且m为常数），每点染一种颜色，相邻的顶点染不同的颜色，不同的染色方法有多少种？
设不同的染色方法有an种，现在我们来通过合理分布，恰当分类找出递推关系：
图例（2年全国卷）如图所示，一个地区分为个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着方法共有多少种？
解法1依题意至少要用种颜色
（1当先用三种颜色时，区域2与4必须同色，
区域与必须同色，故有A4种；
（2）当用四种颜色时，若区域2与4同色，
例（1996年全国数学联赛）从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色则不同的染色方案共有种（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同）
解本题情况较为复杂，我们对用了多少种颜色进行分类讨论
（1）若只用三种颜色，从六种不同颜色中选用种颜色有C6种选法由于每两个具有公共棱的面染成不同的颜色，则正方体的相对面均为同色，由正方体的对称性知这样的染色方案只有一种因此共有C6=2种不同的染色方案
（2）若只用四种颜色，从六种不同颜色中选用4种颜色有C46种选法则仅有一个相对面不同色，共有C24种不同的涂法因此共有C46×C24=9种不同的染色方案
（）若只用五种颜色，从六种不同颜色中选用种颜色有C6种选法则仅有一个相对面同色，不妨定为上、下底面，其有C1种涂法再涂侧面，有种涂法因此共有C6×C1×=9种不同的染色方案
（4）用六种不同颜色来涂色则六个面的颜色均不相同，假想颜色已经涂好，我们可以通过适当的翻转，使上底面均为同一种颜色（例如红色），再考虑下底面，则一定有种不同的颜色对下底面是同一种颜色的（例如蓝色），再用余下的四种颜色来涂侧面，有4！=！种涂法因此共有×！=种不同的染色方案故一共有2+9+9+=2种不同的染色方案
以涂色为平台的排列组合问题，主要考查分类、分步计数原理解决此类问题的主要方法是抓住特定位置或抓住颜色总类进行突破，分步着色，解决问题的关键是依据题意，找到一个确定的标准，合理对问题进行分类或分步，但必须注意分类讨论要全面，要做到不重不漏当直接分类或分步比较复杂时也可间接入手，或寻求对立事件或寻求递推关系，灵活应对。
