初三作文网-百年孤寂歌词

排列组合染色问题的探究
上饶县二中 徐 凯
在任教高 二数学教学时，有许多同学被排列组合题的灵活性所困惑，甚至有
学生向我询问有没有公式之类的解决途 径，每道题都去分析似乎很累。其实就某
些特殊的排列组合问题是可以抽象出数学模型来加以研究的，比 如说下面我们所
要提到的染色问题。
一、一个结论。
若把一个圆（除中间同心圆外的圆环部分）分成n份( n > 1) , 每部分染一
种颜色且相邻部分不能染同种颜色, 现有m (m > 1) 种不同颜色可供使用, 那么
nn
(m1)(1)(m1)
种染色方法。 共有S
例：在一 个圆形花坛种颜色花卉，现有4种颜色可供选择，要求相邻两个区
域不同色，则共有多少种方法？ 解：从图中可以发现除同心圆部分外的圆环部分被分成了
n=5份，因为有4种颜色可供选择，我们 先给同心圆①染色有4
种方法，那么圆环部分有3种颜色可供选择，即m=3,所以圆环部
分共 有S=

31

(1)
5
(31)3223 0
种染色方法，从而整
5
个圆形花坛共有
430120
种染色方 法。
用常规方法同学们是否也能做到那么快和准确呢？
二、结论的证明。
把圆(除中间同心圆部分)分成n份( n > 1) , 每部分染
一种颜色且相邻。部分不能染同种颜色, 现有m (m > 1) 种
不同颜色可供使用, 求不同的染色方法总数。
(1) 当m = 2时, n为偶数时有2种栽种法,n为奇数时无
解。
(2) 当m > 2时
设把圆分成的n 部分为
T
1
、T
2
、T
3
、...T
n1
、T
n
1-1

。开始
2-1

时,
T
1
有m 种不同的染色法;
T
1
染好后,
T
2
有m - 1 种 染色
法;
T
1
、T
2
染好后,
T
3
也有m - 1种染色法; 这样依次下去, 染色的方法总数为
TT
m(m1)
n1
。但是在这些染色方法中, 包括
n1
与
n
染同种颜色的情况,若某种染
色法使
T
n1
与
T
n
同色, 拆去
T
n1
与
T
n
的边界后, 就是分圆为n-1部分, 相邻部分
a
n
染不同颜色的方法。因此, 把圆分成n部分时, 设染色方法的总数为
2
am(m1)mm

2
当n = 2时,
,
当n = 3、4、5、⋯时, 有
a
n
a
n 1
m(m1)
n1
此时问题可转化为:

1

在数列{
a
n
}中，已知
a
n< br>a
n1
m(m1)
n1
得：

a3
m(m1)
2
a
2
2
m(m1)m (m1)

2
m[(m1)(m1)]

a
4
m(m1)
3
a
3

32
m[(m1)(m1)(m1)]

a
5< br>m[(m1)
4
(m1)
3
(m1)
2
(m1)]

……
a
n
m[(m1)
n1(m1)
n2
(m1)
n3
...(m1)(1)
n
]

(m1)
n1
[1(
a
n
m
1(
1
n1
)]
m1
1
)< br>m1

1
n1
(m1)
n
[1()]
m1

nn1
(m1)(1)(m1)

nn
(m1)(1)(m1)
（m>2）
三、练习。在平时做习题时，我们肯定还见过下面这些图形：
3-1 3-2

2

3-3

提示：挖掘共同点
我们可以把上面的图形通过变形转化为下列图形。



这样一来 就很容易的转变成为刚开始我们所说的那种题型了，同学们不妨自己设
已知条件并尝试一下，是不是觉得 排列组合是不是并不那么可怕了呢？


3