恰用m种颜色着色的一类计数问题的算法
作者：李金兴 翁利帅
来源：《数学教学通讯(教师阅读)》2012年第12期

        摘 要：用m种不同的颜色对圆内n个扇形染色（相邻扇形不同色）的方法数可用公式表示，其中包含恰用2种、恰用3种、…、恰用m种颜色染色的方法.如果要计算恰用m种不同的颜色对圆内n个扇形染色（相邻扇形不同色）的方法数难度更大.本文用猜想证明和算法程序解决了该问题.

        关键词：恰用m种颜色；计数问题算法

        两道高考题“牵”出的计数问题

        2003年高考数学全国卷理科15题如下：如图1，一个地区分为5个行政区域，现给地图着色，要求相邻地区不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有多少种？

        无独有偶，2008年高考数学全国卷理科12题如下：如图2，一环形花坛分成A，B，C，D四块，现有4种不同的花供选种，要求在每块里种1种花，且相邻的2块种不同的花，则不同的种法有多少种？

        上述两道考题源于同一问题背景.因为前一题中，先选择一种颜色涂1号区域后，再用余下3种颜色涂2、3、4、5号四块区域（相邻区域不同色），此时，与后一题的问题情景完全一致. 一般地，有下述问题：如图3，把圆分成S1，S2，…，Sn共n个扇形（n≥2）. 现对这n个扇形着色，若有m种不同的颜色可供选择，每个扇形一种颜色，相邻扇形不同色，那么共有多少种不同的着色方法？利用递推关系，可求得着色方法共有f（n，m）=（m-1）n+（-1）n·（m-1）种，因此，两道高考题的答案分别为4f（4，3）=72和f（4，4）=84.

        不同分类视角提出一类新的计数问题

        在一次数学兴趣小组辅导课上，笔者以上述问题背景给出一道练习题：

        在图4所示的六边形区域内栽种植物， 要求相邻两块种不同的植物， 如果有4种植物可供选择， 那么有多少种栽种方法？