秒杀高考中的圆周染色问题

递推类四色圆周染色问题：如图，把一个圆分成(2)n n ≥个扇形，每个扇形用红白蓝黑四色之一染色，要求相邻扇形不同色，有多少种方法？ 思路：设分成n 个扇形时染色方法为n a 种

（1）当2n =时；1A ，2A ，有2

412A =种，即212a =；（2）当分成n 个扇形，如

图，1A 与2A 不同色，2A 与3A 不同色， ，1n A -与n A 不同色，共有143n -?种染色方法，但由于n A 与1A 相邻，所以应排除n A 与1A 同色的情形；n A 与1A 同色时，可把n A ，1A 看成一个扇形，与前2n -个扇形加在一起为1n -个扇形，此时有1n a -种染色法，故有如下递推关系：

1122112433(3)3(3)(1)33(1)n n n n n n n n n n n n n a a a a a a a -----=?-?-=--?-=-?-?=+?-所以有：33(1)n n n a =+?-。

递推类k 种颜色圆周染色问题：如图，把一个圆分成(2)n n ≥个扇形，每个扇形用k 种颜色之一染色，要求相邻扇形不同色，有多少种方法？ 思路：设分成n 个扇形时染色方法为n a 种

（2）当2n =时；1A ，2A ，有2(1)k A k k =-种，即2(1)a k k =-；（2）当分成n 个扇形，如图，1A 与2A 不同色，2A 与3A 不同色， ，1n A -与n A 不同色，共有

1(1)n k k -?-种染色方法，但由于n A 与1A 相邻，所以应排除n A 与1A 同色的情形；n A 与1A 同色时，可把n A ，1A 看成一个扇形，与前2n -个扇形加在一起为1n -个扇形，此时有1n a -种染色法，故有如下递推关系：11(1)n n n a k k a --=?--。

12212(1)[(1)](1)[(1)](1)n n n n n n n a k a k a k a k -----=---?--=--?-， 所以有：(1)(1)(1)n n n a k k =-+-?-

正常着色定理：，如图，用k （k 为正整数）种颜色给圈n C 的n 个顶点着色， 则正常着色的方法为：2),1()1()1(,≥--+-=n k k F n n k n 。k F k =,1。

注： （1）正常着色是指相邻的两个顶点颜色不同；

（2）k 种颜色只是供选择的，并不要求全部用上。

（2008全国卷1）

12．如图，一环形花坛分成A B C D ，，，四块，现有4种不同的花供选种，要求在每块里种1种花，且相邻的2块种不同的花，则不同的种法总数为（ ） A ．96 B ．84 C ．60 D ．48

解：44433(1)84a =+?-=

（2003全国卷）

15．如图，一个地区分为5个行政区域，现给地

图着色，要求相邻地区不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有 种（以数字作答）

解：4444[22(1)]72a =?+?-=

（2003江苏）15．某城市在中心广场建造一个花圃，花圃分为6个部分（如图）现要

栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有___________________种

解： 55

54[22(1)]120a =?+?-

=