高中数学《排列组合染色问题》典例讲解

1、排列组合染色问题的探究上饶县二中徐凯在任教高二数学教学时， 有许多同学被排列组合题的灵活性所困惑， 甚至有学生向我询问有没有公式之类的解决途径， 每道题都去分析似乎很累。 其实就某些特殊的排列组合问题是可以抽象出数学模型来加以研究的， 比如说下面我们所要提到的染色问题。一、一个结论。若把一个圆（除中间同心圆外的圆环部分）分成n份( n 1) ,每部分染一种颜色且相邻部分不能染同种颜色 , 现有 m (m 1)种不同颜色可供使用 , 那么共有 S (m 1)n( 1) n (m 1) 种染色方法。例：在一个圆形花坛种颜色花卉，现有 4种颜色可供选择，要求相邻两个区域不同色，则共有多少种方法？解：

2、从图中可以发现除同心圆部分外的圆环部分被分成了n=5份，因为有 4种颜色可供选择，我们先给同心圆染色有 4 种方法，那么圆环部分有 3种颜色可供选择， 即m=3,所以圆环部分共有 S= 3 1 5(1) 5 (3 1)32230 种染色方法，从而整个圆形花坛共有 430 120 种染色方法。用常规方法同学们是否也能做到那么快和准确呢？二、结论的证明。1-1把圆 ( 除中间同心圆部分 ) 分成 n份 ( n 1) ,每部分染一种颜色且相邻。部分不能染同种颜色, 现有 m (m 1) 种不同颜色可供使用 ,求不同的染色方法总数。(1)当 m = 2 时, n 为偶数时有 2种栽种法 ,n 为奇数时

3、无解。(2)当 m 2 时设把圆分成的 n 部分为 T1、 T2、 T3、.Tn 1、 Tn 。开始时 , T1 有m 种不同的染色法 ; T1染好后 ,T2 有m - 1种染色2-1法 ; T1、 T2 染好后 , T3 也有 m - 1种染色法 ;这样依次下去 , 染色的方法总数为m( m 1) n1Tn 1与Tn染同种颜色的情况 , 若某种染。但是在这些染色方法中 , 包括色法使 Tn1 与 Tn 同色 , 拆去 Tn 1 与 Tn 的边界后 ,就是分圆为 n-1 部分 ,相邻部分染不同颜色的方法。因此 , 把圆分成 n部分时 ,设染色方法的总数为 an ,当n = 2 时 , a2m(

4、 m 1) m2m当n = 3 、 4、 5、 ?时 , 有 anan 1m( m1) n 1此时问题可转化为 :1在数列 an 中，已知 anan 1m( m1) n 1 得：a3m(m1)2a2m(m1) 2m(m1)m( m1)2(m1)a4m(m1) 3a3m( m1)3(m1)2(m 1)a5m( m 1) 4(m1)3(m1)2( m1)anm( m1) n 1(m1) n 2(m1)n 3. (m 1)( 1) n (m 1) n 11 (1) n 1 anmm111(m)11 ) n 1 (m1)n 1(m1(m1)n(1) n1 (m1)(m1)n(1) n (m1)（ m2）三、练习。 在平时做习题时，我们肯定还见过下面这些图形：3-13-223-3提示：挖掘共同点我们可以把上面的图形通过变形转化为下列图形。这样