参军入伍-鼻尖凉

排列组合问题之
涂色问题
（四个方面）

一、区域涂色问题
1、根据分步计数原理，对各个区域分步涂色，这是处理区域染色问题的基本方法。
例
1
、
用
5
种不同的颜色给图中标①、②、③、④的各部分涂色，每部分只涂 一种颜色，相
邻部分涂不同颜色，则不同的涂色方法有多少种？



①
③

④

②
解析：先给①号区 域涂色有
5
种方法；再给②号涂色有
4
种方法；接着给③号涂色方法
有
3
种方法；由于④号与①号、②号不相邻，因此④号有
4
种涂法。根据分步 计数原理，不
同的涂色方法有
5434240
种。
2、根据共用了 多少种颜色讨论，分别计算出各种情形的种数，再用分类计数原理求出不同
的涂色方法种数。
例
2
、
4
种不同的颜色涂在如图所示的
6
个区域，且相邻两 个区域不能同色。
解析：依题意只能选用
4
种颜色，要分四类：
㈠②与⑤同色、④与⑥同色，则有
A
4
4
种；
㈡③与⑤同色、④与⑥同色，则有
A
4
⑤
4
种；
㈢②与⑤同色、③与⑥同色，则有
A
4
4
种；
㈣③与⑤同色、②与④同色，则有
A
4
⑥
①
④
4
种；
②③
㈤②与④同色、③与⑥同色，则有
A
4
4
种。
根据分类计数原理得涂色方法总数为
5A
4
4
120
。
例
3
、
如图所示，一个地区分为
5
个行政区域，现给地图着色，要求 相邻区域不得使用同一
颜色。现有
4
种颜色可供选择，则不同的着色方法共有多少种？
解析：依题意至少要用
3
种颜色。
2
①若用
3
种颜色，区域
2
与
4
必须同色，
3
1 5
区域
3
与
5
必须同色，故有
A
3
4
种；
4
②若用
4
种颜色，则区域
2
与
4
同色，
区域
3
与
5
不同色，有
A
444
4
种；或 区域
3
与
5
同色，区域
2
与
4
不同色，有
A
4
种。共有
2A
4
种。
根据分类计数 原理得满足题意的着色方法共有
A
34
4
2A
4
72< br>。
3、根据某两个不相邻区域是否同色分类讨论。从某两个不相邻区域同色与不同色入手，分< br>别计算出两种情形的种数，再用分类计数原理求出不同涂色方法总数。
例
4
、
用红、黄、蓝、白、黑五种颜色涂在如图所示的四个区域内，每个区域涂一种颜色，
相邻两个区 域涂不同的颜色，五种颜色可以反复使用，共有多少种不同的涂色方法？
解析：可把问题分为三类：
①四格涂不同的颜色，有
A
3
4
种；
②有且仅有两个区域颜色相同，即只有
2 1
一组对角小方格涂相同的颜色。涂法种数有
2C
12
4
5
C
4
；
3
③两组对角小方格分别涂相同的颜色，有
A
2
5
种。
根据 分类计数原理得涂法种数共有
A
3122
4
2C
5
C4
A
5
260
种。

排列组合问题之涂色问题（共4页）

1

4、根据相间区域使用颜色分类讨论。
例
5
、
如图，
6< br>个扇形区域
A
、
B
、
C
、
D
、E
、
F
，现给这
6
个区域着色，要求同一
区域涂同一种 颜色，相邻的两个区域不得使用同一种颜色，现有
4
种不同的颜色可以反复使
用，共有 多少种不同的涂色方法?
解析：①当相间区域
A
、
C
、
E
着同一种颜

F
A
色时，有
4
种着色方法，此时
B
、
D
、
F
各有
3

B
E
种着色方法，共有
4333108
种方法。
D
C
②当相间区域
A
、
C
、
E
着两种不同
22
的颜色时，有
C
3
A
4
种着色方法，此时
B
、< br>D
、
F

22
有
322
种着色方法，共 有
C
3
A
4
322432
种方法。
③当相间区域
A
、
C
、
E
着三种不同的颜色时有
A
4
种着色方法，此时
B
、
D
、
3
22 2192
种方法。
F
各有
2
种着色方法，共有
A
4
3
总计有
108432192732
种不同的涂色方法。
5、用数列递推公式解决扇形区域涂色问题。
例
6
、
把一 个圆分成
n

n2

个扇形，每个扇形用红、白、蓝、黑四色之一 染色，要求相
邻扇形不同色，有多少种不同的染色方法？
解析：设
n
个扇形分别为
A
1
、
A
2
、

、
A
n
，分成
n
个扇形时的染色方法有
a
n
种，则

2
①当
n2
时
A
1
、
A
2
有
A
4
12
种染色方法，即
a
2
12
。

②当分成
n
个扇形时，
A
1< br>与不同色，
A
2
与
A
3
不同色，

，
A
n1
与
A
n
不同色，共有
43
n1
种染色方法。由于
A
n
与
A
1
相邻，应排除
A
n
与
A
1
同色的情形。
A
n
与
A
1
同色时，可把
A
n
、
A
1
看成一个扇形，与前
n2
个扇形加在一起为
n1< br>个扇
形，此时有
a
n1
种染色法。故有如下递推关系：

a
n
43
n1
a
n1

a< br>n
a
n1
43
n1


a
n2
43
n2

43
n1


a
n2
43


4

3
n2
43
n1
an3
43
n3
43
n2
43
n1

n
3
n2




1< br>
3



n


31


3
n1
3
n2



1

3




nn
n1n2n1n2

3

33



1

3

1< br>
33



1

3
< br>

nnn
nn1n22n1n22



333



1

3



33



1

3

1

3



n
n



1

33

n1

二、点涂色问题
方法：㈠根据共用了多少种颜色分类讨论；
㈡根据相对顶点是否同色分类讨论；
㈢将空间问题平面化，转化为区域涂色问题。 例
7
、
将一个四棱锥
SABCD
的每个顶点染上一种颜色，并 使
同一条棱的两端点异色，如果只有
5
种颜色可供使用，那么不同的
染色方法的总数是多少？
解法一：满足题设条件的染色至少要用
3
种颜色。
A
①若恰用
3
种颜色，可先从
5
种颜色中任选一种染
排列组合问题之涂色问题（共4页）

S
D
C
B
2

顶点
S
，再从余下的
4
种颜色中任选2
种染
A
、
B
、
C
、
D
四 点，此时只能
A
与
C
、
B
与
D
分别同色， 故
12
有
C
5
A
4
60
种方法。
②若恰用
4
种颜色，可以先从
5
种颜色中任选一种
染顶点
S
，再从余下的
4
种颜色中任选
2
种染
A
与
B
，
2
由于
A
、
B
颜色可以交换，故 有
A
4
种染法；再从余下的
2
种颜色中任选
1
种染
D
或
C
，而
1211
A
4
C
2< br>C
2
240
种方法。
D
与
C
中的另一个 只需染与其相对顶点同色即可，故有
C
5
5
③若恰用
5
种颜色，有
A
5
120
种方法。
综上，满足题意的染色方法数为
60240120420
种。
解法二：设想染 色按
SABCD
的顺序进行，对
S
、
A
、有
54360
B
染色，
种染色方法。由于
C
点的颜色可能与< br>A
同色或不同色，这影响到
D
点颜色的选取方法数，
故分类讨论：①< br>C
与
A
同色时（此时
C
对颜色的选取方法唯一），
、
S
不同色，有
3
种选择；②
C
与
A
不同 色时，
D
应与
A
（
C
）
D
A
C
有
2
种选择的颜色，
D
也有
2
种颜色可选择， 从而对
C
、
D

染色有
13227
种染色方法。由分步计数乘法原理得，总
S
的染色方法数为
607420
种。
C
B
解法三：这个问题可转化成相邻区域不同色问题。如图，对这
五个区域用
5
种颜色涂色，有多少种不同的涂色方法？

三、线段涂色问题
方法：㈠根据共用了多少颜色分类讨论。
㈡根据相对线段是否同色分类讨论。
解决线段涂色问题，要特别注意对各条线段依次涂色。
例
8
、
用红、黃、蓝、白四种颜色涂矩形
ABCD
的四条边 ，每条边只涂一种颜色，且使相
邻两边涂不同的颜色，如果颜色可以反复使用，共有多少种不同的涂色方 法？
解法一：（1）①使用四种颜色，有
A
4
种；
②使用三种颜色，则必须将一组对边染成同色，故有
C
4
C
2
A3
种；
③使用二种颜色，则两组对边必须分别同色，有
A
4
种；
因此，染 色方法共有
A
4
C
4
C
2
A
3
A
4
84
种。
解法二：涂色按
ABBCCDD A
的顺序进行，对
AB
、
BC
涂色有
4312
种。
由于
CD
的颜色可能与
AB
同色或不同色， 这影响到
DA
颜色的选取，故分类讨论：
①当
CD
与
AB
同色时，这时
CD
对颜色的选取唯一，则
DA< br>有3种颜色可选；
②当
CD
与
AB
不同色时，
CD
有两种颜色可选，
DA
也有两种颜色可选.
对
CD
、
DA
有
13227
种涂色方法。
由分步计数乘法原理，总的涂色方法数为
12784
种。 例
9
、
用六种颜色给正四面体
ABCD
的每条棱染色，要求每 条棱只染一种颜色且共顶点
的棱涂不同的颜色，问有多少种不同的涂色方法？
解析：①若恰用三种颜色，则每组对棱涂同色，组与组之间不同色，有
A
6
种方法。
②若恰用四种颜色，则三组对棱中有二组对棱涂同色，有
C
3
A6
种方法。
③若恰用五种颜色，则三组对棱中有一组对棱涂同色，有
C
3
A
6
种。
④若恰用六种颜色，则有
A
6
种。
324156
综上，总 的染色方法数为
A
6
C
3
A
6
C
3< br>A
6
A
6
4080
种。
6
3
2
4
112
41122
24
15

四、面涂色问题
排列组合问题之涂色问题（共4页）

3

例
9
、
从给定的六种不同颜色中选用 若干种颜色，将一个正方体的
6
个面涂色，每两个具
有公共棱的面涂成不同的颜色，则 不同的涂色方案共有多少种？
解析：至少需要三种颜色，根据用了多少种颜色分类讨论。
①用了六种颜色。确定某种颜色所涂面为下底面，则上底面颜色有
5
种选择， 在上、下
底面已涂好后，再确定其余
4
种颜色中的某一种所涂面为左侧面，则其余3
个面有
3!
种涂色
方案。
n
1
53! 30
种。
5
②用了五种颜色。选定五种颜色有
C
6
，确定 为上、
6
种，必有两面同色（必为相对面）
下底面，其颜色可有
5
种选择，再确定一种颜色为左侧面，此时的方案数取决于右侧面的颜
5
色，有
3
种选择（前后面可通过翻转交换）。
n
2
C
6
5390< br>种。
42
③用了四种颜色。仿上分析可得
n
3
C
6
C
4
90
种。
3
④用了三种颜色。仿上分析可得n
4
C
6
20
种。
综上，总的涂色方案数为n
1
n
2
n
3
n
4
309 09020230
种。
例
10
、
四棱锥
PABC D
，用
4
种不同的颜色涂在四棱锥的各个面上，要求相邻不同色，
有多少种涂 法？

P



1

2

5
D


3
C
4


A

B



解析：可转化为区域涂色问题。如右图，区域
1
、2
、
3
、
4
相当于四个侧面，区域
5
相
当于底面。根据共用颜色多少分类：最少要用
3
种颜色，即
1
与
3
同色、
2
与
4
同色，有
A
4
314
总数为
A
4
C
2
A
4
72
种。 < br>3
14
种；当用
4
种颜色时，
1
与
3
、
2
与
4
两组中只能有一组同色，此时有
C
2
A
4
种。故涂色方法
例
11
、
用三种不同的颜色填涂右图33
方格中的
9
个区域，
要求每行、每列的三个区域都不同色，则不同的填涂方法种
数共有 （
D
）

A
、
48

B
、
24

C
、
12

D
、
6

解析：第一行（或列）
3
种；第二行（或列）
2
种；第三
行（或列）
1
种。共有
3216
种。












排列组合问题之涂色问题（共4页）

4