排列組合問(wèn)題

1、WESTWOOD排列組合問(wèn)題 WESTWOOD排列組合問(wèn)題I一、知識(shí)點(diǎn)：1分類(lèi)計(jì)數(shù)原理：做一件事情，完成它可以有n類(lèi)辦法，在第一類(lèi)辦法中有種不同的方法，在第二類(lèi)辦法中有種不同的方法，在第n類(lèi)辦法中有種不同的方法那么完成這件事共有 種不同的方法2.分步計(jì)數(shù)原理：做一件事情，完成它需要分成n個(gè)步驟，做第一步有種不同的方法，做第二步有種不同的方法，做第n步有種不同的方法，那么完成這件事有 種不同的方法 3排列的概念：從個(gè)不同元素中，任?。ǎ﹤€(gè)元素（這里的被取元素各不相同）按照一定的順序排成一列，叫做從個(gè)不同元素中取出個(gè)元素的一個(gè)排列4排列數(shù)的定義：從個(gè)不同元素中，任?。ǎ﹤€(gè)元素的所有排列的個(gè)數(shù)叫做從

2、個(gè)元素中取出元素的排列數(shù)，用符號(hào)表示5排列數(shù)公式：（）6 階乘：表示正整數(shù)1到的連乘積，叫做的階乘規(guī)定7排列數(shù)的另一個(gè)計(jì)算公式：= 8 組合的概念：一般地，從個(gè)不同元素中取出個(gè)元素并成一組，叫做從個(gè)不同元素中取出個(gè)元素的一個(gè)組合9組合數(shù)的概念：從個(gè)不同元素中取出個(gè)元素的所有組合的個(gè)數(shù)，叫做從 個(gè)不同元素中取出個(gè)元素的組合數(shù)用符號(hào)表示10組合數(shù)公式：或11 組合數(shù)的性質(zhì)1：規(guī)定：； 2：+ 二、解題思路：解排列組合問(wèn)題，首先要弄清一件事是“分類(lèi)”還是“分步”完成，對(duì)于元素之間的關(guān)系，還要考慮“是有序”的還是“無(wú)序的”，也就是會(huì)正確使用分類(lèi)計(jì)數(shù)原理和分步計(jì)數(shù)原理、排列定義和組合定義，其次，對(duì)一些復(fù)

3、雜的帶有附加條件的問(wèn)題，需掌握以下幾種常用的解題方法：特殊優(yōu)先法 對(duì)于存在特殊元素或者特殊位置的排列組合問(wèn)題，我們可以從這些特殊的東西入手，先解決特殊元素或特殊位置，再去解決其它元素或位置，這種解法叫做特殊優(yōu)先法.例如：用0、1、2、3、4這5個(gè)數(shù)字，組成沒(méi)有重復(fù)數(shù)字的三位數(shù)，其中偶數(shù)共有_個(gè).（答案：30個(gè)）科學(xué)分類(lèi)法 對(duì)于較復(fù)雜的排列組合問(wèn)題，由于情況繁多，因此要對(duì)各種不同情況，進(jìn)行科學(xué)分類(lèi)，以便有條不紊地進(jìn)行解答，避免重復(fù)或遺漏現(xiàn)象發(fā)生例如：從6臺(tái)原裝計(jì)算機(jī)和5臺(tái)組裝計(jì)算機(jī)中任取5臺(tái)，其中至少有原裝與組裝計(jì)算機(jī)各兩臺(tái)，則不同的選取法有_種.（答案：350）插空法 解決一些不相鄰問(wèn)題時(shí)，可

4、以先排一些元素然后插入其余元素，使問(wèn)題得以解決例如：7人站成一行，如果甲乙兩人不相鄰，則不同排法種數(shù)是_.(答案:3600)捆綁法相鄰元素的排列，可以采用“整體到局部”的排法，即將相鄰的元素當(dāng)成“一個(gè)”元素進(jìn)行排列，然后再局部排列例如：6名同學(xué)坐成一排，其中甲、乙必須坐在一起的不同坐法是_種.（答案：240）排除法 從總體中排除不符合條件的方法數(shù)，這是一種間接解題的方法.b、排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解析幾何的某些知識(shí)聯(lián)系，從而增加了問(wèn)題的綜合性，解答這類(lèi)應(yīng)用題時(shí)，要注意使用相關(guān)知識(shí)對(duì)答案進(jìn)行取舍.例如：從集合0，1，2，3，5，7，11中任取3個(gè)元素分別作為直線(xiàn)方程Ax+

5、By+C=0中的A、B、C，所得的經(jīng)過(guò)坐標(biāo)原點(diǎn)的直線(xiàn)有_條.（答案：30）三、講解范例：例1 由數(shù)字、組成無(wú)重復(fù)數(shù)字的七位數(shù)(1）求三個(gè)偶數(shù)必相鄰的七位數(shù)的個(gè)數(shù)；（2）求三個(gè)偶數(shù)互不相鄰的七位數(shù)的個(gè)數(shù)解 (1)：因?yàn)槿齻€(gè)偶數(shù)、必須相鄰，所以要得到一個(gè)符合條件的七位數(shù)可以分為如下三步：第一步將、四個(gè)數(shù)字排好有種不同的排法；第二步將、三個(gè)數(shù)字“捆綁”在一起有 種不同的“捆綁”方法; 第三步將第二步“捆綁”的這個(gè)整體“插入”到第一步所排的四個(gè)不同數(shù)字的五個(gè)“間隙”(包括兩端的兩個(gè)位置)中的其中一個(gè)位置上,有種不同的“插入”方法根據(jù)乘法原理共有720種不同的排法所以共有720個(gè)符合條件的七位數(shù)解（2）

6、：因?yàn)槿齻€(gè)偶數(shù)、 互不相鄰，所以要得到符合條件的七位數(shù)可以分為如下兩步：第一步將、四個(gè)數(shù)字排好，有 種不同的排法；第二步將、分別“插入”到第一步排的四個(gè)數(shù)字的五個(gè)“間隙”（包括兩端的兩個(gè)位置）中的三個(gè)位置上，有 種“插入”方法根據(jù)乘法原理共有1440種不同的排法所以共有1440個(gè)符合條件的七位數(shù)例 將、分成三組，共有多少種不同的分法？解：要將、分成三組，可以分為三類(lèi)辦法：（）分法、（）分法、（）分法下面分別計(jì)算每一類(lèi)的方法數(shù)：第一類(lèi)（）分法，這是一類(lèi)整體不等分局部等分的問(wèn)題，可以采用兩種解法解法一：從六個(gè)元素中取出四個(gè)不同的元素構(gòu)成一個(gè)組，余下的兩個(gè)元素各作為一個(gè)組，有種不同的分法解法二：從六

7、個(gè)元素中先取出一個(gè)元素作為一個(gè)組有 種選法，再?gòu)挠嘞碌奈鍌€(gè)元素中取出一個(gè)元素作為一個(gè)組有 種選法，最后余下的四個(gè)元素自然作為一個(gè)組，由于第一步和第二步各選取出一個(gè)元素分別作為一個(gè)組有先后之分，產(chǎn)生了重復(fù)計(jì)算，應(yīng)除以所以共有 15種不同的分組方法 第二類(lèi)（）分法，這是一類(lèi)整體和局部均不等分的問(wèn)題，首先從六個(gè)不同的元素中選取出一個(gè)元素作為一個(gè)組有 種不同的選法，再?gòu)挠嘞碌奈鍌€(gè)不同元素中選取出兩個(gè)不同的元素作為一個(gè)組有 種不同的選法，余下的最后三個(gè)元素自然作為一個(gè)組，根據(jù)乘法原理共有60種不同的分組方法 第三類(lèi)（）分法，這是一類(lèi)整體“等分”的問(wèn)題，首先從六個(gè)不同元素中選取出兩個(gè)不同元素作為一個(gè)組有

8、種不同的取法，再?gòu)挠嘞碌乃膫€(gè)元素中取出兩個(gè)不同的元素作為一個(gè)組有種不同的取法，最后余下的兩個(gè)元素自然作為一個(gè)組由于三組等分存在先后選取的不同的順序，所以應(yīng)除以 ，因此共有 15種不同的分組方法 根據(jù)加法原理，將、六個(gè)元素分成三組共有：15601590種不同的方法例 一排九個(gè)坐位有六個(gè)人坐，若每個(gè)空位兩邊都坐有人，共有多少種不同的坐法？解：九個(gè)坐位六個(gè)人坐，空了三個(gè)坐位，每個(gè)空位兩邊都有人，等價(jià)于三個(gè)空位互不相鄰，可以看做將六個(gè)人先依次坐好有種不同的坐法，再將三個(gè)空坐位“插入”到坐好的六個(gè)人之間的五個(gè)“間隙”（不包括兩端）之中的三個(gè)不同的位置上有種不同的“插入”方法 根據(jù)乘法原理共有 7200種

9、不同的坐法排列組合問(wèn)題II一、相臨問(wèn)題整體捆綁法 例17名學(xué)生站成一排，甲、乙必須站在一起有多少不同排法？解：兩個(gè)元素排在一起的問(wèn)題可用“捆綁”法解決，先將甲乙二人看作一個(gè)元素與其他五人進(jìn)行排列，并考慮甲乙二人的順序，所以共有 種。捆綁法:要求某幾個(gè)元素必須排在一起的問(wèn)題,可以用捆綁法來(lái)解決問(wèn)題.即將需要相鄰的元素合并為一個(gè)元素,再與其它元素一起作排列,同時(shí)要注意合并元素內(nèi)部也可以作排列.一般地: 個(gè)人站成一排,其中某 個(gè)人相鄰,可用“捆綁”法解決，共有 種排法。練習(xí)：5個(gè)男生3個(gè)女生排成一排,3個(gè)女生要排在一起,有多少種不同的排法? 分析 此題涉及到的是排隊(duì)問(wèn)題,對(duì)于女生有特殊的限制,因此,

10、女生是特殊元素,并且要求她們要相鄰,因此可以將她們看成是一個(gè)元素來(lái)解決問(wèn)題.解 因?yàn)榕旁谝黄?所以可以將3個(gè)女生看成是一個(gè)人,與5個(gè)男生作全排列,有 種排法,其中女生內(nèi)部也有 種排法,根據(jù)乘法原理,共有 種不同的排法.二、不相臨問(wèn)題選空插入法 例2 7名學(xué)生站成一排，甲乙互不相鄰有多少不同排法？解：甲、乙二人不相鄰的排法一般應(yīng)用“插空”法，所以甲、乙二人不相鄰的排法總數(shù)應(yīng)為： 種 . 插入法:對(duì)于某兩個(gè)元素或者幾個(gè)元素要求不相鄰的問(wèn)題,可以用插入法.即先排好沒(méi)有限制條件的元素,然后將有限制條件的元素按要求插入排好元素的空檔之中即可.若 個(gè)人站成一排，其中 個(gè)人不相鄰，可用“插空”法解決，

11、共有 種排法。練習(xí)： 學(xué)校組織老師學(xué)生一起看電影，同一排電影票12張。8個(gè)學(xué)生，4個(gè)老師，要求老師在學(xué)生中間，且老師互不相鄰，共有多少種不同的坐法？分析 此題涉及到的是不相鄰問(wèn)題,并且是對(duì)老師有特殊的要求,因此老師是特殊元素,在解決時(shí)就要特殊對(duì)待.所涉及問(wèn)題是排列問(wèn)題.解 先排學(xué)生共有 種排法,然后把老師插入學(xué)生之間的空檔，共有7個(gè)空檔可插,選其中的4個(gè)空檔,共有 種選法.根據(jù)乘法原理,共有的不同坐法為 種.三、復(fù)雜問(wèn)題總體排除法或排異法有些問(wèn)題直接法考慮比較難比較復(fù)雜，或分類(lèi)不清或多種時(shí)，而它的反面往往比較簡(jiǎn)捷，可考慮用“排除法”，先求出它的反面,再?gòu)恼w中排除.解決幾何問(wèn)題必須注意幾何圖形

12、本身對(duì)其構(gòu)成元素的限制。例3.(1996年全國(guó)高考題)正六邊形的中心和頂點(diǎn)共7個(gè)點(diǎn)，以其中3個(gè)點(diǎn)為頂點(diǎn)的三角形共有個(gè).解：從7個(gè)點(diǎn)中取3個(gè)點(diǎn)的取法有 種，但其中正六邊形的對(duì)角線(xiàn)所含的中心和頂點(diǎn)三點(diǎn)共線(xiàn)不能組成三角形，有3條，所以滿(mǎn)足條件的三角形共有 332個(gè).練習(xí)： 我們班里有43位同學(xué),從中任抽5人,正、副班長(zhǎng)、團(tuán)支部書(shū)記至少有一人在內(nèi)的抽法有多少種?分析 此題若是直接去考慮的話(huà),就要將問(wèn)題分成好幾種情況,這樣解題的話(huà),容易造成各種情況遺漏或者重復(fù)的情況.而如果從此問(wèn)題相反的方面去考慮的話(huà),不但容易理解,而且在計(jì)算中也是非常的簡(jiǎn)便.這樣就可以簡(jiǎn)化計(jì)算過(guò)程.解 43人中任抽5人的方法有 種,正

13、副班長(zhǎng),團(tuán)支部書(shū)記都不在內(nèi)的抽法有 種,所以正副班長(zhǎng),團(tuán)支部書(shū)記至少有1人在內(nèi)的抽法有 種.四、特殊元素優(yōu)先考慮法 對(duì)于含有限定條件的排列組合應(yīng)用題，可以考慮優(yōu)先安排特殊位置，然后再考慮其他位置的安排。 例4 (1995年上海高考題) 1名老師和4名獲獎(jiǎng)學(xué)生排成一排照像留念，若老師不排在兩端，則共有不同的排法種解：先考慮特殊元素（老師）的排法，因老師不排在兩端，故可在中間三個(gè)位置上任選一個(gè)位置，有 種，而其余學(xué)生的排法有 種，所以共有 72種不同的排法.例5（2000年全國(guó)高考題）乒乓球隊(duì)的10名隊(duì)員中有3名主力隊(duì)員，派5名隊(duì)員參加比賽，3名主力隊(duì)員要安排在第一、三、五位置，其余7名隊(duì)員選2名

14、安排在第二、四位置，那么不同的出場(chǎng)安排共有種.解：由于第一、三、五位置特殊，只能安排主力隊(duì)員，有 種排法，而其余7名隊(duì)員選出2名安排在第二、四位置，有 種排法，所以不同的出場(chǎng)安排共有 252種.五、多元問(wèn)題分類(lèi)討論法 對(duì)于元素多，選取情況多，可按要求進(jìn)行分類(lèi)討論，最后總計(jì)。例6（2003年北京春招）某班新年聯(lián)歡會(huì)原定的5個(gè)節(jié)目已排成節(jié)目單，開(kāi)演前又增加了兩個(gè)新節(jié)目.如果將這兩個(gè)節(jié)目插入原節(jié)目單中，那么不同插法的種數(shù)為（A ）A42B30C20D12解：增加的兩個(gè)新節(jié)目，可分為相臨與不相臨兩種情況：1.不相臨：共有A62種；2.相臨：共有A22A61種。故不同插法的種數(shù)為：A62 +A22A61

15、=42 ，故選A。例7（2003年全國(guó)高考試題）如圖，一個(gè)地區(qū)分為5個(gè)行政區(qū)域，現(xiàn)給地圖著色，要求相鄰地區(qū)不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著色方法共有 種.（以數(shù)字作答） 解：區(qū)域與其他四個(gè)區(qū)域相鄰，而其他每個(gè)區(qū)域都與三個(gè)區(qū)域相鄰，因此，可以涂三種或四種顏色 用三種顏色著色有 =24種方法, 用四種顏色著色有 =48種方法,從而共有24+48=72種方法,應(yīng)填72. 六、混合問(wèn)題先選后排法 對(duì)于排列組合的混合應(yīng)用題，可采取先選取元素，后進(jìn)行排列的策略 例8（2002年北京高考）12名同學(xué)分別到三個(gè)不同的路口進(jìn)行車(chē)流量的調(diào)查，若每個(gè)路口4人，則不同的分配方案共有（ ）A 種B 種

16、C 種D 種解：本試題屬于均分組問(wèn)題。 則12名同學(xué)均分成3組共有 種方法,分配到三個(gè)不同的路口的不同的分配方案共有： 種，故選A。 例9（2003年北京高考試題）從黃瓜、白菜、油菜、扁豆4種蔬菜品種中選出3種，分別種在不同土質(zhì)的三塊土地上，其中黃瓜必須種植，不同的種植方法共有（ ）    A24種          B18種          C12種   

17、;            D6種    解:先選后排,分步實(shí)施. 由題意，不同的選法有: C32種,不同的排法有: A31·A22,故不同的種植方法共有A31·C32·A22=12，故應(yīng)選C. 七相同元素分配檔板分隔法 例10把10本相同的書(shū)發(fā)給編號(hào)為1、2、3的三個(gè)學(xué)生閱覽室，每個(gè)閱覽室分得的書(shū)的本數(shù)不小于其編號(hào)數(shù)，試求不同分法的種數(shù)。請(qǐng)用盡可能多的方法求解，并思考這些方法是否適合更一般的情況？本題考查組合問(wèn)題。解：先讓2、

18、3號(hào)閱覽室依次分得1本書(shū)、2本書(shū)；再對(duì)余下的7本書(shū)進(jìn)行分配，保證每個(gè)閱覽室至少得一本書(shū)，這相當(dāng)于在7本相同書(shū)之間的6個(gè)“空檔”內(nèi)插入兩個(gè)相同“I”（一般可視為“隔板”）共有 種插法，即有15種分法。八轉(zhuǎn)化法:對(duì)于某些較復(fù)雜的、或較抽象的排列組合問(wèn)題，可以利用轉(zhuǎn)化思想,將其化歸為簡(jiǎn)單的、具體的問(wèn)題來(lái)求解.例11 高二年級(jí)8個(gè)班,組織一個(gè)12個(gè)人的年級(jí)學(xué)生分會(huì),每班要求至少1人,名額分配方案有多少種?分析 此題若直接去考慮的話(huà),就會(huì)比較復(fù)雜.但如果我們將其轉(zhuǎn)換為等價(jià)的其他問(wèn)題,就會(huì)顯得比較清楚,方法簡(jiǎn)單,結(jié)果容易理解.解： 此題可以轉(zhuǎn)化為:將12個(gè)相同的白球分成8份,有多少種不同的分法問(wèn)題,因此須

19、把這12個(gè)白球排成一排,在11個(gè)空檔中放上7個(gè)相同的黑球,每個(gè)空檔最多放一個(gè),即可將白球分成8份,顯然有 種不同的放法,所以名額分配方案有 種.九剩余法:在組合問(wèn)題中,有多少取法,就有多少種剩法,他們是一一對(duì)應(yīng)的,因此,當(dāng)求取法困難時(shí),可轉(zhuǎn)化為求剩法.例12 袋中有5分硬幣23個(gè),1角硬幣10個(gè),如果從袋中取出2元錢(qián),有多少種取法?分析 此題是一個(gè)組合問(wèn)題,若是直接考慮取錢(qián)的問(wèn)題的話(huà),情況比較多,也顯得比較凌亂,難以理出頭緒來(lái).但是如果根據(jù)組合數(shù)性質(zhì)考慮剩余問(wèn)題的話(huà),就會(huì)很容易解決問(wèn)題.解 把所有的硬幣全部取出來(lái),將得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3個(gè)5分或1個(gè)5分與1個(gè)1角,所以共有 種取法.十對(duì)等法:在有些題目中,它的限制條件的肯定與否定是對(duì)等的,各占全體的二分之一.在求解中只要求出全體,就可以得到所求.例13 期中安排考試科目9門(mén),語(yǔ)文要在數(shù)學(xué)之前考,有多少種不同的安排順序?分析 對(duì)于任何一個(gè)排列問(wèn)題,就其中的兩個(gè)元素來(lái)講的話(huà),他們的排列順序只有兩種情況,并且在整個(gè)排列中,他們出現(xiàn)的機(jī)會(huì)是均等的,因此要求其中的某一種情況,能夠得到全體,那么問(wèn)題就可以解決了.并且也避免了問(wèn)題的復(fù)雜性.解 不加任何限制條件,整個(gè)排法有 種,“語(yǔ)文安排在