高中数学：涂色问题，排列组合的一类特殊应用问题

涂色是排列组合的一类特殊应用问题，计数时易重易漏，下面介绍两种避免重漏的分类计数法：

1、区域分类

以涂色区域为对象，选取一对不相邻的区域，按照它们所涂的颜色相同和不同分类计算。

2、色数分类

以颜色种数为对象，按照所选取的不同颜色数分类。

例1、如图1所示，一座圆形花坛被两条直线分成A、B、C、D四块，现要种5种不同颜色的花，要求共边的两块花色不同，每块只种一色花，共有多少种法？

图1

解法一：区域分类

（1）A、C同色

先种A、C，有种方法，然后种B、D，有种方法，共有（种）方法；

（2）A、C异色

先种A、C，有种方法，然后种B、D，有种方法，共有

（种）方法

所以，总种法有260种。

解法二：色数分类

（1）5种花选4种，有种方法；

（2）5种花选3种，则A与C、B与D有一组花色相同，有种方法；

（3）5种花只选2种，则A与C及B与D花色分别相同，有种方法。

所以，总种法有（种）

例2、如图2所示，将一个四棱锥的每个顶点染上一种颜色，并使同一条棱上的两个端点颜色不同，如果只有5种颜色可供使用，求不同的染色方法总数。

图2

解法一：区域分类

（1）若B、D同色，有种染法，再染A，有种方法，然后染C、E，有种方法，此时共有种方法；

（2）若B、D不同色，有种染法，再染A、C、E，有种方法，共有种方法。

综上，染色方法总数为：

（种）

解法二：色数分类

（1）5种颜色都用，有种染法；

（2）5种颜色选4种，则B与D、C与E必有一组同色，有种染法；

（3）5种颜色选3种，则B与D、C与E分别同色，有种染法。

综上，总的染法有（种）

例3、如图3所示，一个地区划分为5个行政区域，现给地图着色，要求相邻区域不得使用同一种颜色，有4种颜色可供选择，不同的着色方法有多少？

图3

解法一：区域分类

（1）先给B、D着相同颜色，有种方法，再依次给A、C、E着色，有种方法，共有种方法；

（2）先给B、D着不同颜色，有种方法，再依次给A、C、E着色，有种方法，共有种方法。

所以，不同着色方法共有

（种）

解法二：色数分类

（1）4种颜色都用，则B与D、C与E必有一组同色，有种方法；

（2）4种颜色选3种，则B与D、C与E分别同色，有种方法。

所以，不同着色方法共有

（种）