數學問題整理之排列組合問題

1、排列組合問題I一、知識點：1分類計數原理：做一件事情，完成它可以有n類辦法，在第一類辦法中有種不同的方法，在第二類辦法中有種不同的方法，在第n類辦法中有種不同的方法那么完成這件事共有 種不同的方法2.分步計數原理：做一件事情，完成它需要分成n個步驟，做第一步有種不同的方法，做第二步有種不同的方法，做第n步有種不同的方法，那么完成這件事有種不同的方法 3排列的概念：從個不同元素中，任?。ǎ﹤€元素（這里的被取元素各不相同）按照一定的順序排成一列，叫做從個不同元素中取出個元素的一個排列4排列數的定義：從個不同元素中，任?。ǎ﹤€元素的所有排列的個數叫做從個元素中取出元素的排列數，用符號表示5排列數公式

2、：（）6階乘：表示正整數1到的連乘積，叫做的階乘規(guī)定7排列數的另一個計算公式：=8組合的概念：一般地，從個不同元素中取出個元素并成一組，叫做從個不同元素中取出個元素的一個組合9組合數的概念：從個不同元素中取出個元素的所有組合的個數，叫做從個不同元素中取出個元素的組合數用符號表示10組合數公式：或11組合數的性質1：規(guī)定：； 2：+ 二、解題思路：解排列組合問題，首先要弄清一件事是“分類”還是“分步”完成，對于元素之間的關系，還要考慮“是有序”的還是“無序的”，也就是會正確使用分類計數原理和分步計數原理、排列定義和組合定義，其次，對一些復雜的帶有附加條件的問題，需掌握以下幾種常用的解題方法：特殊

3、優(yōu)先法對于存在特殊元素或者特殊位置的排列組合問題，我們可以從這些特殊的東西入手，先解決特殊元素或特殊位置，再去解決其它元素或位置，這種解法叫做特殊優(yōu)先法.例如：用0、1、2、3、4這5個數字，組成沒有重復數字的三位數，其中偶數共有_個.（答案：30個）科學分類法對于較復雜的排列組合問題，由于情況繁多，因此要對各種不同情況，進行科學分類，以便有條不紊地進行解答，避免重復或遺漏現象發(fā)生例如：從6臺原裝計算機和5臺組裝計算機中任取5臺，其中至少有原裝與組裝計算機各兩臺，則不同的選取法有_種.（答案：350）插空法解決一些不相鄰問題時，可以先排一些元素然后插入其余元素，使問題得以解決例如：7人站成一行

4、，如果甲乙兩人不相鄰，則不同排法種數是_.(答案:3600)捆綁法相鄰元素的排列，可以采用“整體到局部”的排法，即將相鄰的元素當成“一個”元素進行排列，然后再局部排列例如：6名同學坐成一排，其中甲、乙必須坐在一起的不同坐法是_種.（答案：240）排除法從總體中排除不符合條件的方法數，這是一種間接解題的方法.b、排列組合應用題往往和代數、三角、立體幾何、平面解析幾何的某些知識聯(lián)系，從而增加了問題的綜合性，解答這類應用題時，要注意使用相關知識對答案進行取舍.例如：從集合0，1，2，3，5，7，11中任取3個元素分別作為直線方程Ax+By+C=0中的A、B、C，所得的經過坐標原點的直線有_條.（答案

5、：30）三、講解范例：例1 由數字、組成無重復數字的七位數(1）求三個偶數必相鄰的七位數的個數；（2）求三個偶數互不相鄰的七位數的個數解 (1)：因為三個偶數、必須相鄰，所以要得到一個符合條件的七位數可以分為如下三步：第一步將、四個數字排好有種不同的排法；第二步將、三個數字“捆綁”在一起有種不同的“捆綁”方法; 第三步將第二步“捆綁”的這個整體“插入”到第一步所排的四個不同數字的五個“間隙”(包括兩端的兩個位置)中的其中一個位置上,有種不同的“插入”方法根據乘法原理共有720種不同的排法所以共有720個符合條件的七位數解（2）：因為三個偶數、互不相鄰，所以要得到符合條件的七位數可以分為如下兩步

6、：第一步將、四個數字排好，有種不同的排法；第二步將、分別“插入”到第一步排的四個數字的五個“間隙”（包括兩端的兩個位置）中的三個位置上，有種“插入”方法根據乘法原理共有1440種不同的排法所以共有1440個符合條件的七位數例 將、分成三組，共有多少種不同的分法？解：要將、分成三組，可以分為三類辦法：（）分法、（）分法、（）分法下面分別計算每一類的方法數：第一類（）分法，這是一類整體不等分局部等分的問題，可以采用兩種解法解法一：從六個元素中取出四個不同的元素構成一個組，余下的兩個元素各作為一個組，有種不同的分法解法二：從六個元素中先取出一個元素作為一個組有種選法，再從余下的五個元素中取出一個元素

7、作為一個組有種選法，最后余下的四個元素自然作為一個組，由于第一步和第二步各選取出一個元素分別作為一個組有先后之分，產生了重復計算，應除以所以共有15種不同的分組方法 第二類（）分法，這是一類整體和局部均不等分的問題，首先從六個不同的元素中選取出一個元素作為一個組有種不同的選法，再從余下的五個不同元素中選取出兩個不同的元素作為一個組有種不同的選法，余下的最后三個元素自然作為一個組，根據乘法原理共有60種不同的分組方法 第三類（）分法，這是一類整體“等分”的問題，首先從六個不同元素中選取出兩個不同元素作為一個組有種不同的取法，再從余下的四個元素中取出兩個不同的元素作為一個組有種不同的取法，最后余下

8、的兩個元素自然作為一個組由于三組等分存在先后選取的不同的順序，所以應除以，因此共有15種不同的分組方法 根據加法原理，將、六個元素分成三組共有：15601590種不同的方法例 一排九個坐位有六個人坐，若每個空位兩邊都坐有人，共有多少種不同的坐法？解：九個坐位六個人坐，空了三個坐位，每個空位兩邊都有人，等價于三個空位互不相鄰，可以看做將六個人先依次坐好有種不同的坐法，再將三個空坐位“插入”到坐好的六個人之間的五個“間隙”（不包括兩端）之中的三個不同的位置上有種不同的“插入”方法根據乘法原理共有7200種不同的坐法排列組合問題II一、相臨問題整體捆綁法 例17名學生站成一排，甲、乙必須站在一起有多

9、少不同排法？解：兩個元素排在一起的問題可用“捆綁”法解決，先將甲乙二人看作一個元素與其他五人進行排列，并考慮甲乙二人的順序，所以共有 種。捆綁法:要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素,再與其它元素一起作排列,同時要注意合并元素內部也可以作排列.一般地: 個人站成一排,其中某 個人相鄰,可用“捆綁”法解決，共有 種排法。練習：5個男生3個女生排成一排,3個女生要排在一起,有多少種不同的排法? 分析 此題涉及到的是排隊問題,對于女生有特殊的限制,因此,女生是特殊元素,并且要求她們要相鄰,因此可以將她們看成是一個元素來解決問題.解 因為女生要排在

10、一起,所以可以將3個女生看成是一個人,與5個男生作全排列,有 種排法,其中女生內部也有 種排法,根據乘法原理,共有 種不同的排法.二、不相臨問題選空插入法 例2 7名學生站成一排，甲乙互不相鄰有多少不同排法？解：甲、乙二人不相鄰的排法一般應用“插空”法，所以甲、乙二人不相鄰的排法總數應為： 種 . 插入法:對于某兩個元素或者幾個元素要求不相鄰的問題,可以用插入法.即先排好沒有限制條件的元素,然后將有限制條件的元素按要求插入排好元素的空檔之中即可.若 個人站成一排，其中 個人不相鄰，可用“插空”法解決，共有 種排法。練習： 學校組織老師學生一起看電影，同一排電影票12張。8個學生，4個老師，要求

11、老師在學生中間，且老師互不相鄰，共有多少種不同的坐法？分析 此題涉及到的是不相鄰問題,并且是對老師有特殊的要求,因此老師是特殊元素,在解決時就要特殊對待.所涉及問題是排列問題.解 先排學生共有種排法,然后把老師插入學生之間的空檔，共有7個空檔可插,選其中的4個空檔,共有 種選法.根據乘法原理,共有的不同坐法為 種.三、復雜問題總體排除法或排異法有些問題直接法考慮比較難比較復雜，或分類不清或多種時，而它的反面往往比較簡捷，可考慮用“排除法”，先求出它的反面,再從整體中排除.解決幾何問題必須注意幾何圖形本身對其構成元素的限制。例3.(1996年全國高考題)正六邊形的中心和頂點共7個點，以其中3個點

12、為頂點的三角形共有個.解：從7個點中取3個點的取法有 種，但其中正六邊形的對角線所含的中心和頂點三點共線不能組成三角形，有3條，所以滿足條件的三角形共有 332個.練習： 我們班里有43位同學,從中任抽5人,正、副班長、團支部書記至少有一人在內的抽法有多少種?分析 此題若是直接去考慮的話,就要將問題分成好幾種情況,這樣解題的話,容易造成各種情況遺漏或者重復的情況.而如果從此問題相反的方面去考慮的話,不但容易理解,而且在計算中也是非常的簡便.這樣就可以簡化計算過程.解 43人中任抽5人的方法有 種,正副班長,團支部書記都不在內的抽法有 種,所以正副班長,團支部書記至少有1人在內的抽法有 種.四、

13、特殊元素優(yōu)先考慮法 對于含有限定條件的排列組合應用題，可以考慮優(yōu)先安排特殊位置，然后再考慮其他位置的安排。 例4 (1995年上海高考題) 1名老師和4名獲獎學生排成一排照像留念，若老師不排在兩端，則共有不同的排法種解：先考慮特殊元素（老師）的排法，因老師不排在兩端，故可在中間三個位置上任選一個位置，有 種，而其余學生的排法有 種，所以共有 72種不同的排法.例5（2000年全國高考題）乒乓球隊的10名隊員中有3名主力隊員，派5名隊員參加比賽，3名主力隊員要安排在第一、三、五位置，其余7名隊員選2名安排在第二、四位置，那么不同的出場安排共有種.解：由于第一、三、五位置特殊，只能安排主力隊員，有

14、 種排法，而其余7名隊員選出2名安排在第二、四位置，有 種排法，所以不同的出場安排共有 252種.五、多元問題分類討論法 對于元素多，選取情況多，可按要求進行分類討論，最后總計。例6（2003年北京春招）某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目.如果將這兩個節(jié)目插入原節(jié)目單中，那么不同插法的種數為（A ）A42B30C20D12解：增加的兩個新節(jié)目，可分為相臨與不相臨兩種情況：1.不相臨：共有A62種；2.相臨：共有A22A61種。故不同插法的種數為：A62 +A22A61=42 ，故選A。例7（2003年全國高考試題）如圖，一個地區(qū)分為5個行政區(qū)域，現給地圖著色，要

15、求相鄰地區(qū)不得使用同一顏色，現有4種顏色可供選擇，則不同的著色方法共有 種.（以數字作答） 解：區(qū)域與其他四個區(qū)域相鄰，而其他每個區(qū)域都與三個區(qū)域相鄰，因此，可以涂三種或四種顏色 用三種顏色著色有 =24種方法, 用四種顏色著色有 =48種方法,從而共有24+48=72種方法,應填72. 六、混合問題先選后排法 對于排列組合的混合應用題，可采取先選取元素，后進行排列的策略 例8（2002年北京高考）12名同學分別到三個不同的路口進行車流量的調查，若每個路口4人，則不同的分配方案共有（ ）A 種B 種C 種D 種解：本試題屬于均分組問題。則12名同學均分成3組共有 種方法,分配到三個不同的路口的

16、不同的分配方案共有： 種，故選A。 例9（2003年北京高考試題）從黃瓜、白菜、油菜、扁豆4種蔬菜品種中選出3種，分別種在不同土質的三塊土地上，其中黃瓜必須種植，不同的種植方法共有（）    A24種          B18種          C12種           &

17、#160;   D6種    解:先選后排,分步實施. 由題意，不同的選法有: C32種,不同的排法有: A31·A22,故不同的種植方法共有A31·C32·A22=12，故應選C. 七相同元素分配檔板分隔法 例10把10本相同的書發(fā)給編號為1、2、3的三個學生閱覽室，每個閱覽室分得的書的本數不小于其編號數，試求不同分法的種數。請用盡可能多的方法求解，并思考這些方法是否適合更一般的情況？本題考查組合問題。解：先讓2、3號閱覽室依次分得1本書、2本書；再對余下的7本書進行分配，保證每個閱覽室至少得一本書，這相當于在7

18、本相同書之間的6個“空檔”內插入兩個相同“I”（一般可視為“隔板”）共有 種插法，即有15種分法。八轉化法:對于某些較復雜的、或較抽象的排列組合問題，可以利用轉化思想,將其化歸為簡單的、具體的問題來求解.例11 高二年級8個班,組織一個12個人的年級學生分會,每班要求至少1人,名額分配方案有多少種?分析 此題若直接去考慮的話,就會比較復雜.但如果我們將其轉換為等價的其他問題,就會顯得比較清楚,方法簡單,結果容易理解.解： 此題可以轉化為:將12個相同的白球分成8份,有多少種不同的分法問題,因此須把這12個白球排成一排,在11個空檔中放上7個相同的黑球,每個空檔最多放一個,即可將白球分成8份,顯

19、然有 種不同的放法,所以名額分配方案有 種.九剩余法:在組合問題中,有多少取法,就有多少種剩法,他們是一一對應的,因此,當求取法困難時,可轉化為求剩法.例12 袋中有5分硬幣23個,1角硬幣10個,如果從袋中取出2元錢,有多少種取法?分析 此題是一個組合問題,若是直接考慮取錢的問題的話,情況比較多,也顯得比較凌亂,難以理出頭緒來.但是如果根據組合數性質考慮剩余問題的話,就會很容易解決問題.解 把所有的硬幣全部取出來,將得到0.05×23+0.10×10=2.15元,所以比2元多0.15元,所以剩下0.15元即剩下3個5分或1個5分與1個1角,所以共有 種取法.十對等法:在有些題目中,它的限制條件的肯定與否定是對等的,各占全體的二分之一.在求解中只要求出全體,就可以得到所求.例13 期中安排考試科目9門,語文要在數學之前考,有多少種不同的安排順序?分析 對于任何一個排列問題,就其中的兩個元素來講的話,他們的排列順序只有兩種情況,并且在整個排列中,他們出現的機會是均等的,因此要求其中的某一種情況,能夠得到全體,那么問題就可以解決了.并且也避免了問題的復雜