《排列组合专题之染色问题3》由会员分享，可在线阅读，更多相关《排列组合专题之染色问题3（3页珍藏版）》请在金锄头文库上搜索。
1、1排列组合专题之染色问题排列组合专题之染色问题 【引例引例】 引例 1在一个正六边形的 6 个区域栽种观赏植物，如右图，要求同一块中种 同一种植物，相邻的两块种不同的植物现有四种不同的植物可供选择，则有 _种栽种方案 引例 2某城市在中心广场建造一个花圃，花圃分为 6 个部分（如图） ，现要 栽种 4 种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花， 不同的栽种方法有_种 （以数字作答）【分析分析】首先栽种第 1 部分，有种栽种方法；1 4C然后问题就转化为用余下 3 种颜色的花，去栽种周围的 5 个部分（如右图所 示） ， 此问题和引例 1 是同一题型，因此我们有必要对这一题型
2、的解法做一深入探讨。 【剖析剖析】 为了深入探讨这一题型的解法， （1）让我们首先用 m（m3）种不同的颜色（可供选择） ，去涂 4 个扇形的情形 （要求每一个扇形着一种颜色，相邻扇形着不同颜色） ，如图所示 以 1 和 3（相间）涂色相同与否为分类标准：1 和 3 涂同一种颜色，有 m 种涂法；2 有 m-1 种涂法,4 也有 m-1 种涂 法, 共有 种涂法。(1) (1)mmm1 和 3 涂不同种颜色，有种涂法;2 有 m-2 种涂法，4 也有 m-2 种涂法， 2 mA 共有 种涂法。2(2) (2)mAmm综合和，共有+种涂法。(1) (1)mmm2(2) (2)mAmm432463
3、mmmm（）下面来分析引例 1 以 A、C、E（相间）栽种植物情况作为分类标准：A、C、E 栽种同一种植物，有 4 种栽法；B、D、F 各有 3 种栽法， 共有 4333108 种栽法。A、C、E 栽种两种植物,有种栽法（是 4 种植物中选出222 432C C A2 4C2 种，是 A、C、E3 个区域中选出 2 个区域栽种同一种植物，是2 3C2 2A选出的 2 种植物排列） ，B、D、F 共有 322 种栽法（注：若 A、C 栽种同一种植物，则 B 有 3 种栽法，D、F 各有 2 种栽法） ，222 4323 2 2432C C A 共有种栽法。A、C、E 栽种 3 种植物，有种栽法；
4、B、D、F 各有 2 种栽法，3 4A2 共有 222192 种栽法。3 4A综合、，共有 108+432+192=732 种栽法。 （）上述(1)、(2)给出了“设一个圆分成 P1，P2，Pn，共 n（n 为偶数）个扇形，用 m 种不同的颜色 对这 n 个扇形着色（m3，n3） ，每一个扇形着一种颜色，相邻扇形着不同颜色，共有多少种不同 的着色方法”这类问题的一般解题思路：即以相间扇形区域的涂色情况作为分类标准，再计算其余 相间扇形区域的涂色种数。 （4）那么， “设一个圆分成 P1，P2，Pn，共 n（n 为奇数）个扇形，用 m 种不同的颜色对这 n 个扇形 着色（m3，n3） ，每一个扇
5、形着一种颜色，相邻扇形着不同颜色，共有多少种不同的着色方法” 这类问题的解题思路又如何呢？ 【分析分析】 对扇形 P1有 m 种涂色方法， 扇形 P2有 m1 种涂色方法， 扇形 P3也有 m1 种涂色方法， 扇形 Pn也有 m1 种涂色方法于是，共有种不同的涂色方法。但是，这种涂色方法可能出现 P1与 Pn着色相同的情形，这1(1)nmm是不符合题意的，因此，答案应从中减去这些不符合题意的涂色方法。那么，这些不符合1(1)nmm题意的涂色方法，又怎样计算呢？这时，把 P1与 Pn看作一个扇形，其涂色方法相当于用 m 种颜色对 n1（n1 为偶数）个扇形涂色（这种转换思维相当巧妙） 。而用 m
6、 种颜色对偶数个扇形的涂色问题， 已在上述的（）中给出了解题思路。 下面，就让我们把这种解题思路应用于引例 2 【分析分析】首先栽种第 1 部分，有种栽种方法；1 4C然后问题就转化为用余下 3 种颜色的花，去栽种周围的 5 个部分（如右图 所示） ， 对扇形 2 有 3 种栽种方法， 扇形 3 有 2 种栽种方法， 扇形 4 也有 2 种栽种方法， 扇形 5 也有 2 种栽种方法， 扇形 6 也有 2 种栽种方法于是，共有种不同的栽种方法。但是，这种栽种方法可能出现区域 2 与 6 着色相同的情形，这是不43 2符合题意的，因此，答案应从中减去这些不符合题意的栽种方法。这时，把 2 与 6
7、看作一个扇形，43 2其涂色方法相当于用 3 种颜色的花对 4 个扇形区域栽种（这种转换思维相当巧妙） 。而用 3 种颜色的花对 4 个扇形区域的栽种问题，已在上述的（1）中解决了。综合和，共有种栽法。1412 4333 2(221 1)4(4818)430120CCA （当然此式中的18 也可以直接用（1）中的公式算出：即12 33221 1CA 3）.432463mmmm432343633 318 【拓展拓展】上面，我们分别就 n 为偶数和奇数给出了“设一个圆分成 P1，P2，Pn，共 n 个扇形，用 m 种 不同的颜色对这 n 个扇形着色（m3，n3） ，每一个扇形着一种颜色，相邻扇形着
8、不同颜色，共有多少种 不同的着色方法” 这类问题的解题思路。 那么，这类问题有没有更为一般的解法（即通法）呢？（n 为不小于 3 的整数）【分析分析】设为符合要求的对 n 个扇形的涂色方法。na对扇形 P1有 m 种涂色方法， 扇形 P2有 m1 种涂色方法， 扇形 P3也有 m1 种涂色方法， 扇形 Pn也有 m1 种涂色方法于是，共有种不同的涂色方法。但是，因为这种涂色方法可能出现 P11(1)nmmna1(1)nmm与 Pn着色相同的情形，这是不符合题意的，因此，答案应从中减去这些不符合题意的涂色1(1)nmm方法。那么，这些不符合题意的涂色方法，又怎样计算呢？这时，把 P1与 Pn看作
9、一个扇形，其涂色方法相当于用 m 种颜色对 n1 个扇形涂色（这种转换思维相当巧妙） ，不同的涂色方法有种，于是，有1na（n3） ， 显然，na1(1)nmm1na3(1)(2)am mm上述的式就是数列的递推公式，由此，我们就可以推导出的通项公式：nana (1)( 1) (1)(3)nnmmn 至此，我们就找到了“设一个圆分成 P1，P2，Pn，共 n 个扇形，用 m 种不同的颜色对这 n 个扇形着色 （m3，n3） ，每一个扇形着一种颜色，相邻扇形着不同颜色，共有多少种不同的着色方法” 这类问题的通项公式：即na (1)( 1) (1)(3)nnmmn 【注意注意】上述问题中的 m 种颜色是可供选择的，而不是全部都要用上的。【迁移练习迁移练习】1某城市在中心广场建造一个花圃，花圃分为 6 个部分（如图） ，每部分栽 种一种且相邻部分不能栽种同样颜色的花，现有 5 种不同颜色的花可供选择， 则不同的栽种方法有_种； 若要求 5 种不同颜色的花全部栽种，则不同 的栽种方法有_种 （以数字作答） 2在一个正六边形的 6 个区域栽种观赏植物，如右图，要求同一块中种同一 种植物，相邻的两块种不同的植物现有四种不同的植物可供选择，则有 _种栽种方案；若要求四种不同的植物全部栽种，则有_种栽种 方案【答案答案】11200，600； 2732，480。
