与染色有关的计数问题.doc

与染色有关的计数问题一、对区域染色问题对区域的染色问题常见方法：（1）直接根据两个基本原理求解；（2）根据所用颜色的种数分类；（3）根据某两个区域同色或不同色分类；（4）根据相间区域使用的种类分类。西藏四川青海云南例1用四种颜色给四川、青海、西藏、云南四省（区）的地图染色，每一省（区）一种颜色，要求相邻的省（区）不同色，则不同的染色方法有多少种？分析：给四川染色有4种方法，给青海染色有3种方法，给西藏染色有2种方法，给云南染色有2种方法，根据分步计数原理共有种方法。点评：本例是直接利用两个基本原理来解决。21534例2（2003全国16）如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有 _种。（以数字作答） 解法一：合并单元格法分析：颜色相同的区域可能是24，35。下面分情况讨论：（1）24同色且35不同色时，将24合并成一个单元格，此时不同的着色方法相当于四个元素24、1、3、5的全排列数。（2）当24颜色不同且35颜色相同时种着色方法。（3）当24与35分别同色时，分别将及合并，这样仅有三个单元格，即24、35、1，从4种颜色中选3种来着色这三个单元格，即有种方法。由分类计数原理知，不同的着色方法共有（种）。解法二：由题意可知至少要选三种颜色，依着色的种数分类：（1）当选用三种颜色时，区域与必须同色，且区域与必须同色，故有种。（2）当用四种颜色时，若区域仅与同色有种，若区域仅与同色有种，故用四种颜色时共有种。由分类计数原理知，不同的着色方法共有（种）。解法三：依某两个不相邻的区域同色与不同色分类：（1）当区域与同色时，区域有4种着色方法，区域有3种着色方法，区域有2种着色方法，区域有1种着色方法，区域有2种着色方法，故有种。（2）当区域与不同色时，区域有4种着色方法，区域有3种着色方法，区域有2种着色方法，区域有1种着色方法，区域有1种着色方法，故有种。综上可知，满足题意的着色方法共有种。点评：解法一：合并单元格法；解法二：依使用颜色的种数进行分类；解法三：是根据某两个不相邻的区域是否同色进行讨论的。12345例3（2003新课程文）将3种作物种植在如图的5块试验田里，每块种植一种作物且相邻的试验田不能种植同一作物，不同的种植方法共有_种。（以数字作答）分析：种植同种作物的试验田可能是：，。注意到：5=2+2+1或5=3+1+1，所以必有两对区域的颜色分别相同或有且仅有三个区域同色。不同搭配方式有：、；、；、；、；、；、；、。所以不同的种植方法共有（种）523416点评：本例是先合并单元格，然后再重新组合涂色。例4（2003新课程）某城市在中心广场建造一个花圃，花圃分为6个部分（如图）。现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有_种。（以数字作答）分析：颜色相同的部分可能有：、。要栽种四种不同颜色的花且不可能出现三个区域同色的情形，注意到6=2+2+1+1，所以必有两对区域同色，不同的搭配情形有：、；、；、；、；、。共有种栽种方法。点评：本例也是先合并单元格，然后再重新组合涂色。2134例5用红、黄、蓝、白、黑5种颜色涂在“田”字形的4个小方格内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种涂色方法？解析：如图，把问题分成三类：（1）四格涂不同的颜色，方法有种；（2）有且仅有两格涂相同的颜色，即一组对角小方格涂相同的颜色，有种；（3）两组对角小方格分别涂相同的颜色，涂法种数为。因此，所求得涂法种数为：。点评：本例是根据某两个不相邻的区域是否同色进行讨论的。例6如图一个正六边形的6个区域，现给这六个区域着色，要求同一区域染同一种颜色，相邻的两个区域不得使用同一种颜色，现有4种颜色可供选择，则有多少种不同的着色方法？解：（1）当相间区域着同一颜色时，有4种着色方法，此时各有三种着色方法，故有种方法。（2）当相间区域着两种不同的颜色时，有种着色方法，此时，有种着色方法，故有种方法。（3）当相间区域着三种颜色时，有种着色方法，此时的各有2种着色方法，故有种方法。综上共有种方法。点评：本题是根据相间区域使用的颜色的种类来讨论的。二、对点染色的问题对点染色问题，要注意对各点依次染色。主要方法有：（1）根据共用了多少种颜色的分类讨论法；（2）根据相对顶点是否同色分类讨论法。ADBCS例7将一个四棱锥SABCD的每个顶点染上一种颜色，并使同一条棱上的两个端点不同色，如果只有5种颜色可供使用，那么不同的染色方法的总数是多少？解法一：至少要用3种颜色。（1）若恰用三种颜色，为S染色有5种方法，为AC染色有4种方法，为BD染色有3种方法，共有60种方法。（2）若恰用四种颜色染色，可以先从5种颜色中任选一种染顶点S，再从余下的四种颜色中任选2种染A与B，由于A、B颜色可以交换，故有种染色方法；再从余下的2种颜色中任选1种染D或C，而D与C中另一个只需染与其相对顶点同色即可，故有种方法。（3）若恰用5种颜色染色，有种方法。综上所知，满足题意的染色方法数为种。解法二：设想染色按SABCD的顺序进行，对S、A、B染色，有种染色方法。由于C点的颜色可能与A点同色或不同色，这影响到D点的颜色的选取方法数，故分类讨论：C与A同色时（此时C对颜色的选取方法唯一），D应与A（C）、S不同色，有3种选择；C与A不同色时，C有2种选择的颜色，D也有2种颜色可供选择，从而对C、D染色有种染色方法。三、对线段的染色问题对线段的染色问题，要注意对各条线段依次染色，主要方法有：（1）根据共用了多少种颜色的分类讨论；（2）根据相对的线段是否同色分类讨论。例8用红、黄、蓝、白4种颜色染矩形ABCD的四条边，每一条边只染一种颜色，且使相邻两边染不同的颜色。如果颜色可以反复使用，共有多少种不同的染色方法。解法一：（）使用四种颜色有种；（）使用三种颜色染色，则必须将一组对边染成同色，故有种；（）使用两种颜色时，则必须两组对边分别同色，故有种。因此所求的染色方法数为：种。解法二：设想染色按ABBCCDDA的顺序进行，对AB、BC染色有种方法。由于CD的颜色可能与AB相同，这影响着DA的颜色的选取方法，故分类讨论：当CD与AB同色时，这时CD对颜色的选取方法唯一，则DA有3种颜色可供选择；当CD与AB不同色时，CD有2种可供选择的颜色，DA也有2种可供选择的颜色，从而对CD、DA的染色有种染色方法。由分步计数原理，总的染色方法种数为种。例9用6种颜色给正四面体ABCD的每条棱染色，要求每条棱只染一种颜色且共顶点的棱染不同的颜色，问有多少种不同的染色方法。分析：正四面体有三组对棱AB与CD，AC与BD，AD与BC。满足条件的染色至少要用3种颜色。解：（）若恰用3种