高中数学《排列组合染色问题》典例讲解教学内容.pdfVIP

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