当前位置:首页 >> 数学 >> 排列组合着色问题2

排列组合着色问题2


排列组合专题之染色问题 【引例】 引例 1.在一个正六边形的 6 个区域栽种观赏植物,如右图,要求同一块中种 同一种植物,相邻的两块种不同的植物.现有四种不同的植物可供选择,则有 ________种栽种方案. 引例 2.某城市在中心广场建造一个花圃,花圃分为 6 个部分(如图) ,现要栽 种 4 种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不 同的栽种方法有_

____种. (以数字作答)
1 【分析】首先栽种第 1 部分,有 C4 种栽种方法;

然后问题就转化为用余下 3 种颜色的花,去栽种周围的 5 个部分(如右图所 示) , 此问题和引例 1 是同一题型,因此我们有必要对这一题型的解法做一深入探讨。 【剖析】 为了深入探讨这一题型的解法, (1)让我们首先用 m(m≥3)种不同的颜色(可供选择) ,去涂 4 个扇形的情形 (要求每一个扇形着一种颜色,相邻扇形着不同颜色) ,如图所示 以 1 和 3(相间)涂色相同与否为分类标准: ①1 和 3 涂同一种颜色,有 m 种涂法;2 有 m-1 种涂法,4 也有 m-1 种涂法, ∴ 共有 m ? (m ? 1) ? (m ? 1) 种涂法。
2 ②1 和 3 涂不同种颜色, 有 Am 种涂法;2 有 m-2 种涂法, 4 也有 m-2 种涂法, 2 ∴ 共有 Am ? (m ? 2) ? (m ? 2) 种涂法。 2 综合①和②,共有 m ? ( m ? 1) ? (m ? 1) + Am ? (m ? 2) ? (m ? 2) ? m4 ? 4m3 ? 6m2 ? 3m

种涂法。 (2)下面来分析引例 1 以 A、C、E(相间)栽种植物情况作为分类标准: ①A、C、E 栽种同一种植物,有 4 种栽法;B、D、F 各有 3 种栽法, ∴ 共有 4× 3× 3× 3=108 种栽法。
2 2 2 2 ②A、C、E 栽种两种植物,有 C4 是 4 种植物中选出 2 C3 A2 种栽法( C4 2 2 种, C3 是 A、C、E3 个区域中选出 2 个区域栽种同一种植物, A2 是

选出的 2 种植物排列) ,B、D、F 共有 3× 2× 2 种栽法(注:若 A、C 栽种同一种植 物,则 B 有 3 种栽法,D、F 各有 2 种栽法) ,
2 2 2 ?共有C4 C3 A2 ? 3? 2 ? 2 ? 432种栽法。 3 ③A、C、E 栽种 3 种植物,有 A4 种栽法;B、D、F 各有 2 种栽法, 3 ∴ 共有 A4 × 2× 2× 2=192 种栽法。

综合①、②、③,共有 108+432+192=732 种栽法。 (3)上述(1)、(2)给出了“设一个圆分成 P1,P2,…,Pn,共 n(n 为偶数)个扇形,用 m 种不同的颜色对这 n 个扇形着色(m≥3,n≥3) ,每一个扇形着一种颜色,相邻扇形着 不同颜色,共有多少种不同的着色方法”这类问题的一般解题思路:即以相间扇形区 域的涂色情况作为分类标准,再计算其余相间扇形区域的涂色种数。 (4)那么,“设一个圆分成 P1,P2,…,Pn,共 n(n 为奇数)个扇形,用 m 种不同的颜色 对这 n 个扇形着色(m≥3,n≥3) ,每一个扇形着一种颜色,相邻扇形着不同颜色,共 有多少种不同的着色方法” 这类问题的解题思路又如何呢? 【分析】 对扇形 P1 有 m 种涂色方法, 扇形 P2 有 m-1 种涂色方法, 扇形 P3 也有 m-1 种涂色方法, ………… 扇形 Pn 也有 m-1 种涂色方法. 于是,共有 m ? (m ? 1)
n ?1

种不同的涂色方法。但是,这种涂色方法可能出现 P1 与 Pn 着色相
n ?1

同的情形,这是不符合题意的,因此,答案应从 m ? (m ? 1)

中减去这些不符合题意的涂色

方法。 那么, 这些不符合题意的涂色方法, 又怎样计算呢?这时, 把 P1 与 Pn 看作一个扇形, 其涂色方法相当于用 m 种颜色对 n-1 (n-1 为偶数) 个扇形涂色 (这种转换思维相当巧妙) 。 而用 m 种颜色对偶数个扇形的涂色问题,已在上述的(3)中给出了解题思路。 下面,就让我们把这种解题思路应用于 引例 2. 【分析】
1 ①首先栽种第 1 部分,有 C4 种栽种方法;

②然后问题就转化为用余下 3 种颜色的花,去栽种周围的 5 个部分 (如右图 所示) , 对扇形 2 有 3 种栽种方法, 扇形 3 有 2 种栽种方法, 扇形 4 也有 2 种栽种方法, 扇形 5 也有 2 种栽种方法, 扇形 6 也有 2 种栽种方法. 于是,共有 3 ? 2 4 种不同的栽种方法。但是,这种栽种方法可能出现区域 2 与 6 着色相同的 情形, 这是不符合题意的, 因此, 答案应从 3 ? 2 4 中减去这些不符合题意的栽种方法。 这时, 把 2 与 6 看作一个扇形, 其涂色方法相当于用 3 种颜色的花对 4 个扇形区域栽种 (这种转换 思维相当巧妙) 。 而用 3 种颜色的花对 4 个扇形区域的栽种问题, 已在上述的 (1) 中解决了。
1 1 2 综合①和②,共有 C4 ? [3 ? 24 ? (C3 ? 2 ? 2 ? A3 ?1?1)] ? 4 ? (48 ? 18) ? 4 ? 30 ? 120 种栽

法。
1 2 (当然此式中的 C3 ? 2 ? 2 ? A3 ?1 ?1 ? 18 也可以直接用(1)中的公式算出:即

m4 ? 4m3 ? 6m2 ? 3m ? 34 ? 4 ? 33 ? 6 ? 32 ? 3 ? 3 ? 18 ).

【拓展】上面,我们分别就 n 为偶数和奇数给出了“设一个圆分成 P1,P2,…,Pn,共 n 个 扇形,用 m 种不同的颜色对这 n 个扇形着色(m≥3,n≥3) ,每一个扇形着一种颜色,相邻 扇形着不同颜色,共有多少种不同的着色方法” 这类问题的解题思路。 那么,这类问题有没有更为一般的解法(即通法)呢?(n 为不小于 3 的整数) 【分析】设 an 为符合要求的对 n 个扇形的涂色方法。 对扇形 P1 有 m 种涂色方法, 扇形 P2 有 m-1 种涂色方法, 扇形 P3 也有 m-1 种涂色方法, ………… 扇形 Pn 也有 m-1 种涂色方法. 于是,共有 m ? (m ? 1)
n ?1

种不同的涂色方法。但是, an

? m ? (m ? 1)n?1 ,因为这种涂色方
n ?1

法可能出现 P1 与 Pn 着色相同的情形,这是不符合题意的,因此,答案应从 m ? (m ? 1)



减去这些不符合题意的涂色方法。 那么, 这些不符合题意的涂色方法, 又怎样计算呢?这时, 把 P1 与 Pn 看作一个扇形,其涂色方法相当于用 m 种颜色对 n-1 个扇形涂色(这种转换思 维相当巧妙) ,不同的涂色方法有 an ?1 种,于是,有 ,①. an ? m ? (m ? 1)n?1 - an ?1 (n≥3) 显然, a3 ? m(m ? 1)(m ? 2) .

上述的式①就是数列的递推公式,由此,我们就可以推导出 an 的通项公式:

an ? (m ?1)n ? (?1)n (m ?1)(n ? 3) .
至此,我们就找到了“设一个圆分成 P1,P2,…,Pn,共 n 个扇形,用 m 种不同的颜色对这 n 个扇形着色(m≥3,n≥3) ,每一个扇形着一种颜色,相邻扇形着不同颜色,共有多少种不 同的着色方法” 这类问题的通项公式:即 an ? (m ?1) ? (?1) (m ?1)(n ? 3) .
n n

【注意】上述问题中的 m 种颜色是可供选择的,而不是全部都要用上的。 【迁移练习】 1.某城市在中心广场建造一个花圃,花圃分为 6 个部分(如图) ,每部分栽 种一种且相邻部分不能栽种同样颜色的花, 现有 5 种不同颜色的花可供选择, 则不同的栽种方法有_____种; 若要求 5 种不同颜色的花全部栽种,则不同 的栽种方法有_____种. (以数字作答) 2.在一个正六边形的 6 个区域栽种观赏植物,如右图,要求同一块中种同一种 植物, 相邻的两块种不同的植物. 现有四种不同的植物可供选择, 则有________ 种栽种方案;若要求四种不同的植物全部栽种,则有________种栽种方案. 【答案】1.1200,600; 2.732,480。

例解排列组合中涂色问题
于涂色问题有关的试题新颖有趣,其中包含着丰富的数学思想。解决涂色问题方法技巧 性强且灵活多变, 故这类问题的利于培养学生的创新思维能力、 分析问题与观察问题的能力, 有利于开发学生的智力。本文拟总结涂色问题的常见类型及求解方法。 一、区域涂色问题 1、 根据分步计数原理,对各个区域分步涂色,这是处理染色问题的基本方法。 例1、 用 5 种不同的颜色给图中标①、②、③、④的各部分涂色,每部分只涂一种颜 色,相邻部分涂不同颜色,则不同的涂色方法有多少种? ① ② 分析:先给①号区域涂色有 5 种方法,再给②号涂色有 4 种方法,接着给③号涂色方法 有 3 种,由于④号与①、②不相邻,因此④号有 4 种涂法,根据分步计数原理,不同的涂色 方法有 5 ? 4 ? 3 ? 4 ? 240 2、 根据共用了多少种颜色讨论,分别计算出各种出各种情形的种数,再用加法原理求 出不同的涂色方法种数。 例 2、 (2003 江苏卷)四种不同的颜色涂在如图所示的 6 个区域,且相邻两个区域不能 同色。 分析:依题意只能选用 4 种颜色,要分四类:
4 (1)②与⑤同色、④与⑥同色,则有 A4 ; 4 (2)③与⑤同色、④与⑥同色,则有 A4 ;
4 (3)②与⑤同色、③与⑥同色,则有 A4 ;





⑤ ⑥ ② ① ③ ④

4 4 (4)③与⑤同色、② 与④同色,则有 A4 ; (5)②与④同色、③与⑥同色,则有 ; A4 2 4 所以根据加法原理得涂色方法总数为 5 A4 =120

例 3、 (2003 年全国高考题)如图所示,一个地区分为 5 个行政区域,现给地图着色,要求 相邻区域不得使用同一颜色,现有 4 种颜色可供选择,则不同的着方法共有多少种? 分析:依题意至少要用 3 种颜色 1) 当先用三种颜色时,区域 2 与 4 必须同色, 2 2) 3) 4)
3 区域 3 与 5 必须同色,故有 A4 种;

3

1 4

5

当用四种颜色时,若区域 2 与 4 同色,

4 则区域 3 与 5 不同色,有 A4 种;若区域 3 与 5 同色,则区域 2 与 4 不同色, 4 4 有 A4 种, 故用四种颜色时共有 2 A4 种。 由加法原理可知满足题意的着色方法

3 4 共有 A4 +2 A4 =24+2 ? 24=72

3、 根据某两个不相邻区域是否同色分类讨论, 从某两个不相邻区域同色与不同色入手, 分别计算出两种情形的种数,再用加法原理求出不同涂色方法总数。 例 4 用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内,每个区域涂一种 颜色,相邻两个区域涂不同的颜色,如果颜色可以反复使用,共有多少种不同的涂 色方法? 分析:可把问题分为三类: 2 1 4 (1) 四格涂不同的颜色,方法种数为 A5 ; (2) 有且仅两个区域相同的颜色,即只 有一组对角小方格涂相同的颜色,涂法种数为
1 2 2C5 A4 ;

3

4

5)

2 两组对角小方格分别涂相同的颜色,涂法种数为 A5 , 2 1 2 2 因此,所求的涂法种数为 A5 ? 2C5 A4 ? A5 ? 260

4、 根据相间区使用颜色的种类分类 例 5 如图, 6 个扇形区域 A、B、C、D、E、F,现给这 6 个区域着色,要求同一 区域涂同一种颜色,相邻的两个区域不得使用同一种颜色,现有 4 种不同的颜色可

A1 解(1)当相间区域 A、C、E 着同一种颜色时,
有 4 种着色方法,此时,B、D、F 各有 3 种着色方法, 此时,B、D、F 各有 3 种着色方法故有 4 ? 3 ? 3 ? 3 ? 108 种方法。 D E

C

B A F

2 2 (2)当相间区域 A、C、E 着色两不同的颜色时,有 C3 A4 种着色方法,此时 B、 2 2 D、F 有 3 ? 2 ? 2 种着色方法,故共有 C3 A4 ? 3? 2 ? 2 ? 432 种着色方法。 3 (3)当相间区域 A、C、E 着三种不同的颜色时有 A4 种着色方法,此时 B、D、 3 F 各有 2 种着色方法。此时共有 A4 ? 2 ? 2 ? 2 ? 192 种方法。

故总计有 108+432+192=732 种方法。 说明:关于扇形区域区域涂色问题还可以用数列中的递推公来解决。 如:如图,把一个圆分成 n(n ? 2) 个扇形,每个扇形用红、白、蓝、黑四色 之一染色,要求相邻扇形不同色,有多少种染色方法? 解:设分成 n 个扇形时染色方法为 an 种
2 (1) 当 n=2 时 A 1 、 A2 有 A4 =12 种,即 a2 =12

A1 A2
An
⑤ ⑤

⑤ ⑤ ⑤ ⑤ (2) 当分成 n 个扇形, 如图,A ,An?1 1 与 A2 不同色,A2 与 A 3 不同色,

A3 A3

A4

与 An 不同色, 共有 4 ? 3n ?1 种染色方法, 但由于 An 与 A 1 邻,所以应排除 An 与 A 1

n ? 2 个扇形加在一起为 同色的情形; An 与 A 1 同色时,可把 An 、 A 1 看成一个扇形,与前 n ? 1 个扇形,此时有 an ?1 种染色法,故有如下递推关系:

an ? 4 ? 3n?1 ? an?1

?an ? ?an?1 ? 4 ? 3n?1 ? ?(?an?2 ? 4 ? 3n?2 ) ? 4 ? 3n?1
2 ? an?2 ? 4 ? 3n?2 ? 4 ? 3n? 1 ? ?an?3 ? 4 ? 3n? 3 ? 4 ? 3n? ? 4 ? 3n? 1

?

? 4 ? [3n?1 ? 3n?2 ?

? (?1)n ? 3]

? (?1)n ? 3 ? 3n
二、点的涂色问题 方法有: (1)可根据共用了多少种颜色分类讨论, (2)根据相对顶点是否同色分类讨 论, (3)将空间问题平面化,转化成区域涂色问题。 例 6、 将一个四棱锥 S ? ABCD 的每个顶点染上一种颜色, 并使同一条棱的两端点异色, 如果只有 5 种颜色可供使用,那么不同的染色方法的总数是多少? 解法一:满足题设条件的染色至少要用三种颜色。 (1) 若恰用三种颜色,可先从五种颜色中任选一种染顶点 S,再从余下的四 种颜色中任选两种涂 A、B、C、D 四点,此时只能 A 与 C、B 与 D 分
1 2 别同色,故有 C5 A4 ? 60 种方法。

(2) 若恰用四种颜色染色,可以先从五种颜色中任选一种颜色染顶点 S,再 从余下的四种颜色中任选两种染 A 与 B,由于 A、B 颜色可以交换,
2 故有 A4 种染法; 再从余下的两种颜色中任选一种染 D 或 C, 而 D 与 C,

而 D 与 C 中另一个只需染与其相对顶点同色即可,故有
1 2 1 1 C5 A4 C2C2 ? 240 种方法。 5 (3) 若恰用五种颜色染色,有 A5 ? 120 种染色法

综上所知,满足题意的染色方法数为 60+240+120=420 种。 解法二: 设想染色按 S—A—B—C—D 的顺序进行, 对 S、 A、 B 染色, 有 5 ? 4 ? 3 ? 60 种染色方法。 由于 C 点的颜色可能与 A 同色或不同色, 这影响到 D 点颜色的选取方法数, 故分类讨论: C 与 A 同色时(此时 C 对颜色的选取方法唯一) ,D 应与 A(C) 、S 不同色,有 3 种 选择;C 与 A 不同色时,C 有 2 种选择的颜色,D 也有 2 种颜色可供选择,从而对 C、D 染 色有 1? 3 ? 2 ? 2 ? 7 种染色方法。 由乘法原理,总的染色方法是 60 ? 7 ? 420 解法三:可把这个问题转化成相邻区域不同色问题:如图, A S B C D

对这五个区域用 5 种颜色涂色,有多少种不同的涂色方法? 解答略。 三、线段涂色问题 对线段涂色问题,要注意对各条线段依次涂色,主要方法有: 1) 根据共用了多少颜色分类讨论 2) 根据相对线段是否同色分类讨论。 例 7、 用红、 黃、 蓝、 白四种颜色涂矩形 ABCD 的四条边, 每条边只涂一种颜色 , 且使相邻两边涂不同的颜色,如果颜色可以反复使用,共有多少种不同的涂色方 法?
4 解法一: (1)使用四颜色共有 A4 种 1 1 2 (2) 使用三种颜色涂色, 则必须将一组对边染成同色, 故有 C4 C2 A3 种, 2 (3)使用二种颜色时,则两组对边必须分别同色,有 A4 种
4 1 1 2 2 因此,所求的染色方法数为 A4 ? C4 C2 A3 ? A4 ? 84 种

解法二:涂色按 AB-BC-CD-DA 的顺序进行,对 AB、BC 涂色有 4 ? 3 ? 12 种 涂色方法。 由于 CD 的颜色可能与 AB 同色或不同色, 这影响到 DA 颜色的选取方法数, 故分 类讨论: 当 CD 与 AB 同色时,这时 CD 对颜色的选取方法唯一,则 DA 有 3 种颜 色可供选择 CD 与 AB 不同色时,CD 有两种可供选择的颜色,DA 也有两种可供 选择的颜色,从而对 CD、DA 涂色有 1? 3 ? 2 ? 2 ? 7 种涂色方法。 由乘法原理,总的涂色方法数为 12 ? 7 ? 84 种 例 8、用六种颜色给正四面体 A ? BCD 的每条棱染色,要求每条棱只染一种颜色 且共顶点的棱涂不同的颜色,问有多少种不同的涂色方法? 解: (1) 若恰用三种颜色涂色, 则每组对棱必须涂同一颜色, 而这三组间的颜色不同,
3 故有 A6 种方法。

(2)若恰用四种颜色涂色,则三组对棱中有二组对棱的组内对棱涂同色,但组与
3 4 组之间不同色,故有 C6 A6 种方法。 1 5 (3)若恰用五种颜色涂色,则三组对棱中有一组对棱涂同一种颜色,故有 C3 A6 种

方法。
6 (4)若恰用六种颜色涂色,则有 A6 种不同的方法。

3 2 4 1 5 6 综上,满足题意的总的染色方法数为 A6 ? C3 A6 ? C3 A6 ? A6 ? 4080种。

四、面涂色问题 例 9、从给定的六种不同颜色中选用若干种颜色,将一个正方体的 6 个面涂色,每两个 具有公共棱的面涂成不同的颜色,则不同的涂色方案共有多少种? 分析:显然,至少需要 3 三种颜色,由于有多种不同情况,仍应考虑利用加法原 理分

类、乘法原理分步进行讨论 解:根据共用多少种不同的颜色分类讨论 (1) 用了六种颜色, 确定某种颜色所涂面为下底面, 则上底颜色可有 5 种选择, 在上、 下底已涂好后,再确定其余 4 种颜色中的某一种所涂面为左侧面,则其余 3 个面有 3! 种涂色方案,根据乘法原理 n1 ? 5 ? 3!? 30
5 (2)共用五种颜色,选定五种颜色有 C6 , ? 6 种方法,必有两面同色(必为相对面)

确定为上、下底面,其颜色可有 5 种选择,再确定一种颜色为左侧面,此时的方法数 取决于右侧面的颜色,有 3 种选择(前后面可通过翻转交换)
5 n2 ? C6 ? 5 ? 3 ? 90

(3)共用四种颜色,仿上分析可得
4 2 n3 ? C6 C4 ? 90
3 (4)共用三种颜色, n4 ? C6 ? 20

例 10、四棱锥 P ? ABCD ,用 4 种不同的颜色涂在四棱锥的各个面上,要求相邻不同 色,有多少种涂法? P 1

2 5 3

D C A

?
4

B 解:这种面的涂色问题可转化为区域涂色问题,如右图,区域 1、2、3、4 相当于四个侧 面,区域 5 相当于底面;根据共用颜色多少分类:
3 (1) 最少要用 3 种颜色,即 1 与 3 同色、2 与 4 同色,此时有 A4 种; 1 4 (2) 当用 4 种颜色时, 1 与 3 同色、 2 与 4 两组中只能有一组同色, 此时有 C2 A4 ; 3 1 4 故满足题意总的涂色方法总方法交总数为 A4 ? C2 A4 ? 72


更多相关文档:

例谈排列组合中的染色问题

例谈排列组合中的染色问题 例谈排列组合中的染色问题 排列组合中的,去涂 4 ...但是,这种栽种方法可能出现区域 2 与 6 着色相同的情形,这是不符合题意的,...

排列组合中涂色问题的常见方法及策略

高三专题讲座 排列组合中涂色问题的常见方法及策略与涂色问题有关的试题新颖有趣...由加法原理可知满足题意的着色方 法共有 A4 +2 A4 =24+2 × 24=72 3 ...

2015年高考排列组合专题之染色问题

2015年高考排列组合专题之染色问题_高考_高中教育_教育专区。2015年高考排列组合...现有四种不同的植物可供选择,则有 ___种栽种方案. 引例 2.某城市在中心广场...

排列组合中的染色问题(教师版)

排列组合中的染色问题(教师版)_数学_高中教育_教育专区。排列,组合,染色问题排列...480 种,解法二:与第 4 题类似,A3 3 + 1 = 480种 6 6.用 n 种不同...

排列组合中的染色问题(教师用)

排列组合中的染色问题辅导教师:朱屿 电话:15044088809 辅导教师: 电话: 染色问题...2.如图所示的花圃分成六个区域, 现要栽四种不同的花, 每一部分栽一种花色且...

排列组合涂色问题

排列组合涂色问题_数学_高中教育_教育专区。用三种颜色给 6 个格子涂色,若每种...和第二格的颜色确定下来,其他格 就定下来 方法数=3*2种情况:首尾格...

解排列组合中涂色问题

排列组合中涂色问题_育儿理论经验_幼儿教育_教育专区...对各个区域分步涂色,这是处理染色问题的基本方法。 ...①②③ ④ 例 2、四种不同的颜色涂在如图所示的...

排列组合中涂色问题的常见方法及策略

排列组合中涂色问题的常见方法及策略_数学_高中教育_教育专区。排列组合中涂色问题...2 2 2 2 (3)当相间区域 A、 C、E 着三种不同的颜色时有 A4 种着色...

解决排列组合中涂色问题的常见方法

解决排列组合中涂色问题的常见方法及策略江苏省阜宁中学 刘佐 与涂色问题有关的...由加法原理可知满足题意的着色方 法共有 A4 +2 A4 =24+2 × 24=72 3 ...

排列组合中涂色问题

排列组合中涂色问题_数学_高中教育_教育专区。解决排列组合中涂色问题的常见方法及...C D E F B A 2 2 (2)当相间区域 A、C、E 着色两不同的颜色时,有 ...
更多相关标签:
组合数学地图着色问题 | 排列组合问题 | 隔板法解排列组合问题 | 小学奥数排列组合问题 | 排列组合涂色问题 | 排列组合染色问题 | 排列组合平均分组问题 | 排列组合分组问题 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com