排列組合中染色問題(精華版)

1、排列組合典型例題排列組合典型例題排隊(duì)排隊(duì)”，“染色染色”問題問題典例回顧典例回顧:例例1. 4男男3女坐成一排女坐成一排, 1).共有多少種排法共有多少種排法? 2).某人必須在中間某人必須在中間,有多少種排法有多少種排法?3).某二人只能在兩端某二人只能在兩端,有多少種排法有多少種排法?4).某人不在中間和兩端某人不在中間和兩端,有多少種排法有多少種排法?5).甲乙必相鄰甲乙必相鄰,有多少種排法有多少種排法? 6)甲乙不相鄰甲乙不相鄰,有多少種排法有多少種排法?7).甲乙兩人間必相隔一人甲乙兩人間必相隔一人,有多少種排法有多少種排法?8)4男必相鄰男必相鄰,有多少種排法有多少種排法? 9)4

2、男相鄰男相鄰,3女也相鄰女也相鄰,有多少種排法有多少種排法?10)3女不相鄰女不相鄰,有多少種排法有多少種排法? 11)4男不相鄰男不相鄰,有多少種排法有多少種排法?12)4男不在兩端有多少種排法男不在兩端有多少種排法? 13)甲在乙的左邊有多少種排法甲在乙的左邊有多少種排法?14)4男不等高男不等高,按高矮順序排列按高矮順序排列,有多少種排法有多少種排法?解題回顧解題回顧:本題是處理排隊(duì)問題的經(jīng)典類型本題是處理排隊(duì)問題的經(jīng)典類型,從中體會不同的限制從中體會不同的限制條件下的求解方法條件下的求解方法.*練習(xí)練習(xí)1.(2006年江蘇卷）今有年江蘇卷）今有2個紅球、個紅球、3個黃球、個黃球、4個白

3、球，個白球，同色球不加以區(qū)分，將這同色球不加以區(qū)分，將這9個球排成一列有個球排成一列有種不同的方法種不同的方法992342341260AA A A 例例2 由由1，2，3，4，5，6六個數(shù)字可以組成多少個六個數(shù)字可以組成多少個無重復(fù)且是無重復(fù)且是6的倍數(shù)的五位數(shù)？的倍數(shù)的五位數(shù)？分析數(shù)字特征：分析數(shù)字特征：6的倍數(shù)既是的倍數(shù)既是2的倍數(shù)又是的倍數(shù)又是3的倍數(shù)。其中的倍數(shù)。其中3的倍數(shù)又滿足的倍數(shù)又滿足“各個數(shù)位上的數(shù)字之和是各個數(shù)位上的數(shù)字之和是3的倍數(shù)的倍數(shù)”的特征。的特征。把把6分成分成4組，（組，（3，3），（），（6），（），（1，5），（），（2，4），每），每組的數(shù)字和都是組的數(shù)字

4、和都是3的倍數(shù)。因此可分成兩類討論；的倍數(shù)。因此可分成兩類討論；第一類：由第一類：由1，2，4，5，6作數(shù)碼；首先從作數(shù)碼；首先從2，4，6中任選中任選一個作個位數(shù)字有一個作個位數(shù)字有 ，然后其余四個數(shù)在其他數(shù)位上全排，然后其余四個數(shù)在其他數(shù)位上全排列有列有 ，所以，所以第二類：由第二類：由1，2，3，4，5作數(shù)碼。依上法有作數(shù)碼。依上法有13A44A14341NA A14242NA A12=+=120()N N故個N【練習(xí)【練習(xí)1】由】由1，2，3，4，5，6可以組成多少個可以組成多少個(1)無重復(fù)數(shù)字的無重復(fù)數(shù)字的2的倍數(shù)的的三位數(shù)的倍數(shù)的的三位數(shù)?(2)無重復(fù)數(shù)字的無重復(fù)數(shù)字的能被能被3

5、整除的三位數(shù)整除的三位數(shù)?(3)無重復(fù)數(shù)字的無重復(fù)數(shù)字的且是且是6的倍數(shù)的三位數(shù)？的倍數(shù)的三位數(shù)？練習(xí)2:(05全國卷全國卷)在由數(shù)字0，1，2，3，4，5所組成的沒有重復(fù)數(shù)字的四位數(shù)中，不能被5整除的數(shù)共有 個.(240種種, 320種種) A簡單的著色問題簡單的著色問題例4:用n種不同顏色為下列兩塊廣告牌著色(如圖甲、乙所示），要求在a,b,c,d四個區(qū)域中相鄰（有公共邊界）的區(qū)域不用同一顏色。（1）若n=6，為甲著色時有多少種不同方法？（2）若為乙著色有120種方法，求n.abcd甲abcd乙乙（1）480 （2）n=5例5.(03年)如圖，一個地區(qū)分為5個行政區(qū)域， 現(xiàn)給地圖著色，要求

6、相鄰區(qū)域不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著色方法共有 種.（以數(shù)字作答） 72練習(xí)練習(xí)2:用紅、黃、藍(lán)、白、黑用紅、黃、藍(lán)、白、黑5種顏色涂在種顏色涂在“田田”字形的字形的4個小方格個小方格內(nèi)，每格涂一種顏色，相鄰的兩格涂不同的顏色，如果顏色可以內(nèi)，每格涂一種顏色，相鄰的兩格涂不同的顏色，如果顏色可以反復(fù)使用，共有多少種不同的涂色方法反復(fù)使用，共有多少種不同的涂色方法 圖6涂 2 色：2520A ；涂 3 色：1325120C A ； 涂 4 色：45120A ，共有20120 120260種 解后思解后思:關(guān)于涂色問題關(guān)于涂色問題,一般來說一般來說,以以”某兩個區(qū)域同色或某兩

7、個區(qū)域同色或異色分類異色分類”或或”以使用顏色的多少分類以使用顏色的多少分類”是常見的兩種是常見的兩種思考方式思考方式.例例6:用用5種顏色給圖種顏色給圖7中的中的5個車站的候車牌（個車站的候車牌（A、B、C、D、E）染色，要求相鄰兩個車站間的候車牌的顏色不同，有多少種不染色，要求相鄰兩個車站間的候車牌的顏色不同，有多少種不同的染色方案？同的染色方案？圖7涂 3 色：3560A ；涂 4 色：1425240C A ； 涂 5 色：55120A ，共有60240120420種 2、根據(jù)共用了多少種顏色討論，分別計(jì)算出各種出各種 情形的種數(shù)，再用加法原理求出不同的涂色方法種數(shù)。例7、（江蘇卷）四種

8、不同的顏色涂在如圖所示的6個區(qū)域， 且相鄰兩個區(qū)域不能同色 分析：依題意只能選用4種顏色，要分四類：（1）與同色、與同色，則有44A44A44A（2）與同色、與同色，則有（3）與同色、與同色，則有（5）與同色、與同色，則有44A （4）與同色、與同色，則有44A所以根據(jù)加法原理得涂色方法總數(shù)為例8、（全國高考題）如圖所示，一個地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著方法共有多少種？分析：依題意至少要用3種顏色 3.根據(jù)某兩個不相鄰區(qū)域是否同色分類討論，從某兩個不相鄰區(qū)域同色與不同色入手，分別計(jì)算出兩種情形的種數(shù)，再用加法原理求出不同涂色方法總數(shù)。例4.用紅、黃、藍(lán)、白、黑五種顏色涂在如圖所示的四個區(qū)域內(nèi)，每個區(qū)域涂一種顏色，相鄰兩個區(qū)域涂不同的顏色，如果顏色可以反復(fù)使用，共有多少種不同的涂色方法？4.根據(jù)相間區(qū)使用顏色的種類分類例5如圖， 6個扇形區(qū)域A、B、C、D、E、F，現(xiàn)給這6個區(qū)域著色，要求同一區(qū)域涂同一種顏色，相鄰的兩個區(qū)域不得使用同一種顏色，現(xiàn)有4種不同的顏色可有多少種方法？四、面涂色問題四、面涂色問題例9、從給定的六種不同顏色中選用若干種顏色，將一個正方體從給定的六種不同顏色中選用