环状涂色问题经验很好的总结

1、（克山一中）（克山一中）中国行政地图中国行政地图 给山东，河南，安徽，江苏四个地区涂色，相邻区域涂不同给山东，河南，安徽，江苏四个地区涂色，相邻区域涂不同颜色，现有四种不同颜色可供使用，共有颜色，现有四种不同颜色可供使用，共有 种不同涂法。种不同涂法。问题问题84圆被分成圆被分成了了2。 3、4、5、6个扇形区域的图形个扇形区域的图形, 如下：如下： （图（图B）（图（图C)（图（图D） （图（图E） 图图A，按要求显然有，按要求显然有4 3 =12种涂色方案。种涂色方案。图图C，用间接法求解，假设，用间接法求解，假设4区域涂法依次为区域涂法依次为4、3、3、3种种， 则需减去首尾两区域涂相同

2、颜色的情形（相当于图则需减去首尾两区域涂相同颜色的情形（相当于图A的情形）的情形） 故有故有 种涂色方案。种涂色方案。 34 32484以上图形各区以上图形各区域可选四域可选四种不同颜色涂色，要求相邻涂不同颜色种不同颜色涂色，要求相邻涂不同颜色1.观察分析观察分析(图图A)图图B, 显然有显然有4 3 2= 4 3 2- 12=24种涂色方种涂色方案。案。 对图对图D，类似于图，类似于图C的解法，假设的解法，假设5个区域涂法依次为个区域涂法依次为4、3、3、3、3种，则需减去首尾两区域涂相同颜色的情形（相当于种，则需减去首尾两区域涂相同颜色的情形（相当于图图C的情形）。的情形）。 故有故有44

3、 384240 种涂色方案。种涂色方案。 对图对图E，类似于图，类似于图D的解法，假设的解法，假设6区域涂法依次为区域涂法依次为4、3、3、3、3、3种，则需减去首尾两区域涂相同颜色的情形（相当于种，则需减去首尾两区域涂相同颜色的情形（相当于图图D的情形）。的情形）。 种涂色方案。种涂色方案。 故有故有 732240345（图（图B）（图（图C）（图（图D） （图（图E） (图图A)如果如果n个区域有个区域有四四种颜色可供选用，那么有多少种不同的涂法种颜色可供选用，那么有多少种不同的涂法?) 3( n113) 13(nna1133nnna1134nnnaa2.猜想递推公式猜想递推公式a2=33

4、243 （3+1）3a3=) 33 (33223333a4=33433a) 33 (33334334a5=a6=) 33 (33445335) 33 (3355633622333a3.猜猜想归纳通项想归纳通项annnna33) 1( (n2)所以所以如果如果n个不同区域有个不同区域有m种颜色可供选用，那么有多少种不同的涂法种颜色可供选用，那么有多少种不同的涂法?由由1134nnnaa1133nnna(n3)记为记为?图2?M?n?M?6?M?5?M?4?M?3?M?2?M?1P4.归纳结论：归纳结论： 相连构成相连构成n个三角形，个三角形， 2MnM1M、，现取现取种颜色对这种颜色对这n个三角

5、形涂色，每相邻的两个三角形的涂色不同，个三角形涂色，每相邻的两个三角形的涂色不同，试求涂色的方案有多少种？试求涂色的方案有多少种？ 如图如图2，已知，已知p是是n(n3)边形内的一点，它与边形内的一点，它与n个顶点个顶点m（m4）故得递推公式为故得递推公式为:11) 1(nnnamma) 3( nnnnmma) 1() 1() 1(n2，m4)通项通项： 在一个正六边形的在一个正六边形的六六个区域栽种观赏植个区域栽种观赏植物（如图）要求同一区域中种同一种植物，相邻的两物（如图）要求同一区域中种同一种植物，相邻的两块种不同的植物。现有块种不同的植物。现有5种不同的植物可供选择，则种不同的植物可供

6、选择，则栽种方案有栽种方案有 _ 种。种。 ABCDEFP4100结论应用结论应用：1解解:因为因为 n=6, m=5 由公式得由公式得nnnmma) 1() 1() 1(66) 15() 15() 1(644=4100应用应用2.（2008年全国）年全国）如图，一环形花坛分成如图，一环形花坛分成A、B、C、D四四块，现有块，现有 4种不同的花供选种，要在每块花坛里种一种种不同的花供选种，要在每块花坛里种一种花，且相邻的两块花，且相邻的两块 种不同的花，则不同的种法总数为种不同的花，则不同的种法总数为（ ） A、96 B、84 C、60 D、48ADBCB如图，一个地区分为如图，一个地区分为5

7、个行政区域，现给地图着色，个行政区域，现给地图着色，要求相邻区域不得使用同一种颜色，现有要求相邻区域不得使用同一种颜色，现有四四种颜色可种颜色可供选择，则不同的着色方法有供选择，则不同的着色方法有_种。种。 12345变式应用变式应用：12543172 (2003年高考题年高考题)解解:首先涂首先涂1区域有区域有4种种,再涂再涂2,3,4,5区域区域还有还有3种颜色涂种颜色涂,可抽象如图可抽象如图.所以涂色总数所以涂色总数:72)422(4) 13() 13() 1(4442.?(2003年全国高考新课程卷理工第15题)某城市在中心广场建造一个花圃，花圃分为6个部分（如图），现要栽种4种不同颜

8、色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_种（以数字作答）120引申练习引申练习：1（2005年潍坊模拟）将一个年潍坊模拟）将一个四四棱锥的每一个棱锥的每一个顶点染一种颜色，并使一条棱的两个端点异色，如果有顶点染一种颜色，并使一条棱的两个端点异色，如果有5种不种不同的颜色可选用，问有多少种不同的染色方法同的颜色可选用，问有多少种不同的染色方法_种。种。PADBC420练练习习2：将将5种颜色染种颜色染n棱锥棱锥 的顶点，每个顶点染上一种颜色，的顶点，每个顶点染上一种颜色，并使同一条棱的两端点异色。如并使同一条棱的两端点异色。如果过果过有有五五种颜色可供种颜色可供使

9、用，那么不同的染色方法总数是使用，那么不同的染色方法总数是_an=53n+(-1)n33. 将将m(m4)种颜色染种颜色染n(n3)棱锥的每个顶点染上一种颜棱锥的每个顶点染上一种颜色，并使同一条棱的两端点异色。如果只有色，并使同一条棱的两端点异色。如果只有n种颜色可供使种颜色可供使用，那么不同的染色方法总数是用，那么不同的染色方法总数是an=_m (m-2)n+(-1)n(m-2) 4. 将一个将一个四四棱锥的每一个面染一种颜色，并使相邻两面涂棱锥的每一个面染一种颜色，并使相邻两面涂异色，如果有异色，如果有5种不同的颜色可选用，问有种不同的颜色可选用，问有_种不同的种不同的染色方法。染色方法。420知识总结：知识总结：(n2，m3)nnnmma) 1() 1() 1(1.环状涂色问题涂法总数公式环状涂色问题涂法总数公式:(其中 n为不同区域数,m为不同颜色数)2()2() 1(nnnmmma(n3，m4)2.用用m不同颜色涂不同颜色涂n棱锥的顶点涂法总数公式棱锥的顶点涂法总数公式:课后作业课后作业: : （2003年全国高考题）年全国高考题） 如图，一个地区分为如图，一个地区分为5个行政区域，现给地图着色，个行政区域，现给地图着色，要求相邻区域不得使用同一种颜色，现有要求相邻区域不得使用同一种颜色，现有6 6种颜色可种颜色