高中數(shù)學(xué)《排列組合染色問(wèn)題》典例講解復(fù)習(xí)過(guò)程

1、精品文檔排列組合染色問(wèn)題的探究上饒縣二中徐凱在任教高二數(shù)學(xué)教學(xué)時(shí)， 有許多同學(xué)被排列組合題的靈活性所困惑， 甚至有學(xué)生向我詢問(wèn)有沒(méi)有公式之類的解決途徑， 每道題都去分析似乎很累。 其實(shí)就某些特殊的排列組合問(wèn)題是可以抽象出數(shù)學(xué)模型來(lái)加以研究的， 比如說(shuō)下面我們所要提到的染色問(wèn)題。一、一個(gè)結(jié)論。若把一個(gè)圓（除中間同心圓外的圓環(huán)部分）分成n份( n 1) ,每部分染一種顏色且相鄰部分不能染同種顏色 , 現(xiàn)有 m (m 1)種不同顏色可供使用 , 那么共有 S (m 1)n( 1) n (m 1) 種染色方法。例：在一個(gè)圓形花壇種顏色花卉，現(xiàn)有 4種顏色可供選擇，要求相鄰兩個(gè)區(qū)域不同色，則共有多少種方

2、法？解：從圖中可以發(fā)現(xiàn)除同心圓部分外的圓環(huán)部分被分成了n=5份，因?yàn)橛?4種顏色可供選擇，我們先給同心圓染色有 4 種方法，那么圓環(huán)部分有 3種顏色可供選擇， 即m=3,所以圓環(huán)部分共有S=3 15(1) 5(3 1)32230 種染色方法，從而整個(gè)圓形花壇共有 430 120 種染色方法。用常規(guī)方法同學(xué)們是否也能做到那么快和準(zhǔn)確呢？二、結(jié)論的證明。1-1把圓 ( 除中間同心圓部分 ) 分成 n份 ( n 1) ,每部分染一種顏色且相鄰。部分不能染同種顏色, 現(xiàn)有 m (m 1) 種不同顏色可供使用 ,求不同的染色方法總數(shù)。(1)當(dāng) m = 2 時(shí), n 為偶數(shù)時(shí)有 2種栽種法 ,n 為奇數(shù)時(shí)

3、無(wú)解。(2)當(dāng) m 2 時(shí)設(shè)把圓分成的 n 部分為 T1、 T2、 T3、.Tn 1、 Tn 。開始時(shí) , T1 有m 種不同的染色法 ; T1染好后 ,T2 有m - 1種染色2-1法 ; T1、 T2 染好后 , T3 也有 m - 1種染色法 ;這樣依次下去 , 染色的方法總數(shù)為m( m 1) n1Tn 1與Tn染同種顏色的情況 , 若某種染。但是在這些染色方法中 , 包括色法使 Tn1 與 Tn 同色 , 拆去 Tn 1 與 Tn 的邊界后 ,就是分圓為 n-1 部分 ,相鄰部分染不同顏色的方法。因此 , 把圓分成 n部分時(shí) ,設(shè)染色方法的總數(shù)為 an ,當(dāng)n = 2 時(shí) , a2m(

4、 m 1) m2m當(dāng)n = 3 、 4、 5、 ?時(shí) , 有 anan 1m( m1) n 1此時(shí)問(wèn)題可轉(zhuǎn)化為 :精品文檔精品文檔在數(shù)列 an 中，已知 anan1m( m1) n 1 得：a3m( m1) 2a2m(m1) 2m(m1)m( m1)2(m1)am(m1)3a34m( m1)3(m1)2(m1)a5m( m1) 4( m1) 3(m1) 2(m1)anm( m1)n1(m1) n 2(m1) n 3. (m 1)( 1) n (m 1) n 1 1 (1) n 1 anmm111(m)11 ) n 1 (m1)n 1(m1(m1)n(1) n1 (m1)(m1)n(1) n (m1)（ m2）三、練習(xí)。 在平時(shí)做習(xí)題時(shí)，我們肯定還見過(guò)下面這些圖形：3-13-2精品文檔精品文檔3-3提示：挖掘共同點(diǎn)我們可以把上面的圖形通過(guò)變形轉(zhuǎn)化為下列圖形。這樣一來(lái)