排列组合中的染色问题

林维祥

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

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

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

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

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

所以，不同的着色方法共有 + =72（种）。

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

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

种方法。

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

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

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

第一种情况： 与 颜色一样的涂法为 ，区域 有2种涂色方法；

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

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

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

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

则有

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

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

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