排列组合专题之染色问题3.docx

PAGE PAGE 1 排列组合专题之染色问题 【引例】 引例 1．在一个正六边形的 6 个区域栽种观赏植物，如右图，要求同一块中种同一种植物，相邻的两块种不同的植物．现有四种不同的植物可供选择，则有 种栽种方案． 引例 2．某城市在中心广场建造一个花圃，花圃分为6 个部分（如图），现要栽种 4 种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有 种．（以数字作答） 【分析】首先栽种第 1 部分，有C 1 种栽种方法； 4 然后问题就转化为用余下 3 种颜色的花，去栽种周围的 5 个部分（如右图所示）， 此问题和引例 1 是同一题型，因此我们有必要对这一题型的解法做一深入探讨。 【剖析】 为了深入探讨这一题型的解法， （1）让我们首先用m（m≥3）种不同的颜色（可供选择），去涂 4 个扇形的情形 （要求每一个扇形着一种颜色，相邻扇形着不同颜色），如图所示以 1 和 3（相间）涂色相同与否为分类标准： ①1 和 3 涂同一种颜色，有 m 种涂法；2 有 m-1 种涂法,4 也有m-1 种涂法, ∴ 共有 m ? (m ?1)?(m ?1) 种涂法。 ②1 和 3 涂不同种颜色，有 A2 种涂法;2 有 m-2 种涂法，4 也有 m-2 种涂法， m ∴ 共有 A2 ? (m ? 2) ? (m ? 2) 种涂法。 m 综合①和②，共有m ? (m ?1)?(m ?1)+ A2 ? (m ? 2) ? (m ? 2) ? m4 ? 4m3 ? 6m2 ? 3m 种涂法。 m （２）下面来分析引例 1 以 A、C、E（相间）栽种植物情况作为分类标准： ①A、C、E 栽种同一种植物，有 4 种栽法；B、D、F 各有 3 种栽法， ∴ 共有 4×3×3×3＝108 种栽法。 ②A、C、E 栽种两种植物,有C2C2 A2 种栽法（C2 是 4 种植物中选出 2 4 3 2 4 种， C2 是 A、C、E3 个区域中选出 2 个区域栽种同一种植物， A2 是 3 2 选出的 2 种植物排列），B、D、F 共有 3×2×2 种栽法（注：若A、C 栽种同一种植物，则B 有 3 种栽法，D、F 各有 2 种栽法）， ?共有C2C2 A2 ? 3? 2? 2 ? 432种栽法。 4 3 2 ③A、C、E 栽种 3 种植物，有 A3 种栽法；B、D、F 各有 2 种栽法， 4 ∴ 共有 A3 ×2×2×2＝192 种栽法。 4 综合①、②、③，共有 108+432+192=732 种栽法。 “ …（３）上述(1)、(2)给出了 设一个圆分成 P ，P ， ，Pn，共 n（n 为偶数）个扇形，用 m “ … 1 2 对这 n 个扇形着色（m≥3，n≥3），每一个扇形着一种颜色，相邻扇形着不同颜色，共有多少种不同 的着色方法”这类问题的一般解题思路：即以相间扇形区域的涂色情况作为分类标准，再计算其余相间扇形区域的涂色种数。 “ …（4）那么， 设一个圆分成P ，P ， ，Pn，共 n（n 为奇数）个扇形，用m 种不同的颜色对这n “ … 1 2 着色（m≥3，n≥3），每一个扇形着一种颜色，相邻扇形着不同颜色，共有多少种不同的着色方法” 这 类问题的解题思路又如何呢？ 【分析】 对扇形P 有 m 种涂色方法， 1 扇形P 有 m－1 种涂色方法， 2 扇形P 3 也有m－1 种涂色方法， ………… 扇形P 也有m－1 种涂色方法． n 于是，共有m ? (m ? 1)n?1 种不同的涂色方法。但是，这种涂色方法可能出现 P 与 P 着色相同的情形，这 1 n 是不符合题意的，因此，答案应从m ? (m ? 1)n?1 中减去这些不符合题意的涂色方法。那么，这些不符合题意的涂色方法，又怎样计算呢？这时，把 P 与P 看作一个扇形，其涂色方法相当于用 m 种颜色对n－1（n 1 n －1 为偶数）个扇形涂色（这种转换思维相当巧妙）。而用 m 种颜色对偶数个扇形的涂色问题，已在上述 的（３）中给出了解题思路。 下面，就让我们把这种解题思路应用于引例2． 【分析】 ①首先栽种第 1 部分，有C 1 种栽种方法； 4 ②然后问题就转化为用余下 3 种颜色的花，去栽种周围的 5 个部分（如右图所示）， 对扇形 2 有 3 种栽种方法， 扇形 3 有 2 种栽种方法， 扇形 4 也有 2 种栽种方法， 扇形 5 也有 2 种栽种方法， 扇形 6 也有 2 种栽种方法． 于是，共有3 ? 24 种不同的栽种方法。但是，这种栽种方法可能出现区域2 与 6 着色相同的情形，这是不 符合题意的，因此，答案应从3 ? 24 中减去这些不符合题意的栽种方法。这时，把2 与 6 看作一个扇形， 其涂色方法相当于用