排列组合中的染色问题

福建省霞浦县松港中心小学 林维祥

引言 组合计数问题是组合数学的重要内容，也是竞赛数学不可或缺的重要组成部分，而染色问题是数学竞赛中常见的一类问题，也是与实际生活联系最为直接的内容. 若能顺利解决此类问题则其他排列组合问题也就迎刃而解了.

解决组合计数问题的主要方法有枚举法、利用计数原理及基本公式、递推方法、容斥原理等，其中蕴含着分类讨论、转化和化归、函数与方程等数学思想。在平时遇到的某些计数问题(如染色问题)看似排列组合类应用题， 但又复杂万分，若从元素递增的角度考虑，建立递推数列就能迎刃而解.

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

图1

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

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

所以，不同的着色方法共有

例题中的图形我们可以将其抽象为图2，即把图形分成如图的五块，则改变图形至图3，即将图形分成n+1块，有

命题1 如图3所示的一个图形被分成n+1块小块，现将其染色，要求相邻的小块不得使用同一种颜色，有四种颜色可供选择，则有种方法。

分析：如图3中第O块与每个小块都相邻，则其所涂的颜色必与剩余的任何一个小块的颜色不同；因此，当O块涂了四种颜色中的一种后，就只剩下三种颜色可供剩余的小块涂色，根据此分析，我们有如下证明：

证明： 第O小块可以从四种颜色中任意选一种有种，设n个小块区域D1、D2、Dn…的涂法总数为an，整个图形的涂法总数为bn。不难算出

现寻找an的递推关系：当D1、D2、Dn…区域涂色完毕后，区域Dn+1的涂色有两种情况：

第一种情况：D1与Dn颜色一样的涂法为an-1，区域Dn+1有2种涂色方法；

第二种情况：D1与Dn颜色不一样的涂法为an，区域Dn+1只有一种涂色方法。

由分类计数原理知：

经检验n=2时，也适合上式。

若将命题1中的颜色从4种增加到m种，则有

命题2 如图3所示的一个图形被分成n+1块小块，现将其染色，要求相邻的小块不得使用同一种颜色，有m种颜色可供选择，则有种方法。

证明： 设n个小块区域D1、D2、Dn…的涂法总数为an，整个图形的涂法总数为bn。

证明与命题2的证明相同。

推论：若将图3的图形再复杂化成如图4所示的图形，现对其进行染色，要求相邻的小块颜色不同，有m种颜色可供选择，则有种 方法。

图4

分析：图4中的图形相对图3增加了n个外面的半圆，而外面的半圆的染色数目只与相邻的小块颜色有关（如B1的颜色只与B有关，即B1与B颜色不相同）。当里面的小块已经染色完毕后，A1还有m-1种颜色可供选择，同理B1,C1均有m-1种颜色可供选择。所以根据乘法原理共有种方法。

从上可知，常规的方法不仅繁杂而且容易遗漏；但是若能熟练运用式（*）或（**），则问题就变得简单易解，而且在解题过程中不会出现重复或遗漏的情况。