排列組合問題

m!Cm=

或m!Cm=

或n11組合數(shù)的性質(zhì)1：Cm=Cn-mnn規(guī)定：排列組合問題I一、知識點(diǎn)：1?分類計數(shù)原理：做一件事情，完成它可以有n類辦法，在第一類辦法中有mi種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法+那么完成這N二m+m+—\-m件事共有 1 2十 n種不同的方法.2?分步計數(shù)原理：做一件事情，完成它需要分成n個步驟，做第一步有mi種不同的方法，做第二步有m2種不同的方法，，做第n步有"n種不同的方法，那么完成這件事有N=mxmx—xm12n種不同的方法+排列的概念：從n個不同元素中，任取m(m-n)個元素(這里的被取元素各不相同)按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列?排列數(shù)的定義：從n個不同元素中，任取m(mJn)個元素的所有排列的個數(shù)叫做從n個元素中取出m元素的排列數(shù)，用符號An表示,5.排列數(shù)公式：Am二n(n-1)(n-2)—(n-m+1)n5.排列數(shù)公式：6階乘：n!表示正整數(shù)1到"的連乘積，叫做n的階乘規(guī)定0!二1.n!7.排列數(shù)的另一個計算公式：人：=(n-m)!”(m<n丿8組合的概念：一般地，從n個不同元素中取出m -個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合+Im<n丿9.組合數(shù)的概念：從n個不同元素中取出m ~個元素的所有組合的個數(shù)，叫做從n個Cm不同元素中取出m個元素的組合數(shù).用符號n表示.Amn(n-1)(n-2)—(n-m+1)Cm=—n:10.組合數(shù)公式：n Ammn!m!(n一m)!(n,meN*,且m<n)Cm Cm Cm-1n+1—n+n二、解題思路：解排列組合問題，首先要弄清一件事是“分類”還是“分步”完成，對于元素之間的關(guān)系，還要考慮“是有序”的還是“無序的”，也就是會正確使用分類計數(shù)原理和分步計數(shù)原理、排列定義和組合定義，其次，對一些復(fù)雜的帶有附加條件的問題，需掌握以下幾種常用的解題方法：特殊優(yōu)先法*對于存在特殊元素或者特殊位置的排列組合問題，我們可以從這些特殊的東西入手，先解決特殊元素或特殊位置，再去解決其它元素或位置，這種解法叫做特殊優(yōu)先法.例如：用0、1、2、3、4這5個數(shù)字，組成沒有重復(fù)數(shù)字的三位數(shù)，其中偶數(shù)共有 個.（答案：30個）科學(xué)分類法+對于較復(fù)雜的排列組合問題，由于情況繁多，因此要對各種不同情況，進(jìn)行科學(xué)分類，以便有條不紊地進(jìn)行解答，避免重復(fù)或遺漏現(xiàn)象發(fā)生例如：從6臺原裝計算機(jī)和5臺組裝計算機(jī)中任取5臺，其中至少有原裝與組裝計算機(jī)各兩臺，則不同的選取法有 種.（答案：350）插空法?解決一些不相鄰問題時，可以先排一些元素然后插入其余元素，使問題得以解決?例如：7人站成一行，如果甲乙兩人不相鄰，則不同排法種數(shù)是 .（答案:3600）捆綁法+相鄰元素的排列，可以采用“整體到局部”的排法，即將相鄰的元素當(dāng)成“一個”元素進(jìn)行排列，然后再局部排列”例如：6名同學(xué)坐成一排，其中甲、乙必須坐在一起的不同坐法是 種.（答案：240）排除法?從總體中排除不符合條件的方法數(shù)，這是一種間接解題的方法.b、排列組合應(yīng)用題往往和代數(shù)、三角、立體幾何、平面解析幾何的某些知識聯(lián)系，從而增加了問題的綜合性，解答這類應(yīng)用題時，要注意使用相關(guān)知識對答案進(jìn)行取舍.例如：從集合｛0，1，2，3，5，7,11｝中任取3個元素分別作為直線方程Ax+By+C=O中的A、B、C,所得的經(jīng)過坐標(biāo)原點(diǎn)的直線有 條.（答案：30）三、講解范例：例1由數(shù)字1、2、3、4、5、6、7組成無重復(fù)數(shù)字的七位數(shù)（1）求三個偶數(shù)必相鄰的七位數(shù)的個數(shù)；（2）求三個偶數(shù)互不相鄰的七位數(shù)的個數(shù)+解（1）：因?yàn)槿齻€偶數(shù)2、4、6必須相鄰，所以要得到一個符合條件的七位數(shù)可以分為如下三步：第一步將1、3、5、7四個數(shù)字排好有P44種不同的排法；P3第二步將2、4、6三個數(shù)字“捆綁”在一起有3種不同的“捆綁”方法;第三步將第二步“捆綁”的這個整體“插入”到第一步所排的四個不同數(shù)字的五個“間隙”P1（包括兩端的兩個位置）中的其中一個位置上，有P5種不同的“插入”方法.P4?P3?Pl根據(jù)乘法原理共有P4P3P5=720種不同的排法所以共有720個符合條件的七位數(shù)解(2):因?yàn)槿齻€偶數(shù)2、4、6互不相鄰，所以要得到符合條件的七位數(shù)可以分為如下兩步：P4第一步將1、3、5、7四個數(shù)字排好，有P44種不同的排法；第二步將2、4、6分別“插入”到第一步排的四個數(shù)字的五個“間隙”(包括兩端的兩個P3位置)中的三個位置上，有二種“插入”方法+P4?P3根據(jù)乘法原理共有P4P5=1440種不同的排法+所以共有1440個符合條件的七位數(shù)+例2將A、E、C、D、E、F分成三組，共有多少種不同的分法？解：要將A、E、C、D、E、F分成三組，可以分為三類辦法：(1—1—4)分法、(1—2—3)分法、(2—2—2)分法■下面分別計算每一類的方法數(shù)：第一類(1—1—4)分法，這是一類整體不等分局部等分的問題，可以采用兩種解法解法一：從六個元素中取出四個不同的元素構(gòu)成一個組，余下的兩個元素各作為一個組，有C46種不同的分法?C1解法二：從六個元素中先取出一個元素作為一個組有6種選法，再從余下的五個元素中取出一個元素作為一個組有C5種選法，最后余下的四個元素自然作為一個組，由于第一步和P2第二步各選取出一個元素分別作為一個組有先后之分，產(chǎn)生了重復(fù)計算，應(yīng)除以^”Ci?Ci―6 5P2所以共有2 =15種不同的分組方法+第二類(1—2—3)分法，這是一類整體和局部均不等分的問題，首先從六個不同的C1元素中選取出一個元素作為一個組有6種不同的選法，再從余下的五個不同元素中選取出C2兩個不同的元素作為一個組有5種不同的選法，余下的最后三個元素自然作為一個組，根據(jù)乘法原理共有C6?C5=60種不同的分組方法.第三類(2—2—2)分法，這是一類整體“等分”的問題，首先從六個不同元素中選C2取出兩個不同元素作為一個組有6種不同的取法，再從余下的四個元素中取出兩個不同的C2元素作為一個組有C4種不同的取法，最后余下的兩個元素自然作為一個組由于三組等分存C2?C26 4-P3 P3在先后選取的不同的順序，所以應(yīng)除以P3，因此共有P3 =15種不同的分組方法-根據(jù)加法原理，將A、E、C、D、E、F六個元素分成三組共有：15+60+15=90種不同的方法?例3一排九個坐位有六個人坐，若每個空位兩邊都坐有人，共有多少種不同的坐法？

解：九個坐位六個人坐，空了三個坐位，每個空位兩邊都有人，等價于三個空位互不相鄰，可以看做將六個人先依次坐好有6種不同的坐法，再將三個空坐位“插入”到坐好的六個C3人之間的五個“間隙”（不包括兩端）之中的三個不同的位置上有C5種不同的“插入”方法?根據(jù)乘法原理共有P66C5=7200種不同的坐法?排列組合問題II一、相臨問題——整體捆綁法例1．7名學(xué)生站成一排，甲、乙必須站在一起有多少不同排法？解：兩個元素排在一起的問題可用“捆綁”法解決，先將甲乙二人看作一個元素與其他五人進(jìn)行排列，并考慮甲乙二人的順序，所以共有 種。捆綁法:要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素，再與其它元素一起作排列，同時要注意合并元素內(nèi)部也可以作排列.一般地："個人站成一排，其中某欣個人相鄰，可用“捆綁”法解決，共有 種排法。練習(xí)：5個男生3個女生排成一排,3個女生要排在一起,有多少種不同的排法?分析此題涉及到的是排隊(duì)問題,對于女生有特殊的限制,因此,女生是特殊元素,并且要求她們要相鄰,因此可以將她們看成是一個元素來解決問題.解 因?yàn)榕旁谝黄?所以可以將3個女生看成是一個人,與5個男生作全排列,有6種排法,其中女生內(nèi)部也有3二、不相臨問題——選空插入法種排法,根據(jù)乘法原理,共有6種排法,其中女生內(nèi)部也有3二、不相臨問題——選空插入法種排法,根據(jù)乘法原理,共有P6P363種不同的排法.例2．7名學(xué)生站成一排，甲乙互不相鄰有多少不同排法？解：甲、乙二人不相鄰的排法一般應(yīng)用“插空”法，所以甲、乙二人不相鄰的排法總數(shù)應(yīng)為： 種?插入法:對于某兩個元素或者幾個元素要求不相鄰的問題,可以用插入法.即先排好沒有限制條件的元素，然后將有限制條件的元素按要求插入排好元素的空檔之中即可.若"個人站成一排，其中険個人不相鄰，可用“插空”法解決，共有 種排法。練習(xí)：學(xué)校組織老師學(xué)生一起看電影，同一排電影票12張。8個學(xué)生，4個老師，要求老師在學(xué)生中間，且老師互不相鄰，共有多少種不同的坐法？分析此題涉及到的是不相鄰問題，并且是對老師有特殊的要求，因此老師是特殊元素，在解決時就要特殊對待.所涉及問題是排列問題.解先排學(xué)生共有P8種排法，然后把老師插入學(xué)生之間的空檔，共有7個空檔可插,選其中8P4 P8P4的4個空檔，共有7種選法.根據(jù)乘法原理，共有的不同坐法為 87種.三、復(fù)雜問題——總體排除法或排異法有些問題直接法考慮比較難比較復(fù)雜，或分類不清或多種時，而它的反面往往比較簡捷，可考慮用“排除法”，先求出它的反面，再從整體中排除.解決幾何問題必須注意幾何圖形本身對其構(gòu)成元素的限制。例3.（1996年全國高考題）正六邊形的中心和頂點(diǎn)共7個點(diǎn)，以其中3個點(diǎn)為頂點(diǎn)的三角形共有 個.解：從7個點(diǎn)中取3個點(diǎn)的取法有U；種，但其中正六邊形的對角線所含的中心和頂點(diǎn)三點(diǎn)共線不能組成三角形，有3條，所以滿足條件的三角形共有^-3=32個.練習(xí)：我們班里有43位同學(xué),從中任抽5人,正、副班長、團(tuán)支部書記至少有一人在內(nèi)的抽法有多少種?分析此題若是直接去考慮的話,就要將問題分成好幾種情況,這樣解題的話,容易造成各種情況遺漏或者重復(fù)的情況.而如果從此問題相反的方面去考慮的話,不但容易理解,而且在計算中也是非常的簡便.這樣就可以簡化計算過程.解43人中任抽5人的方法有43種,正副班長,團(tuán)支部書記都不在內(nèi)的抽法有40種,所以正副班長,團(tuán)支部書記至少有1人在內(nèi)的抽法有 4340種.四、特殊元素——優(yōu)先考慮法對于含有限定條件的排列組合應(yīng)用題，可以考慮優(yōu)先安排特殊位置，然后再考慮其他位置的安排。例4．（1995年上海高考題）1名老師和4名獲獎學(xué)生排成一排照像留念，若老師不排在兩端，則共有不同的排法 種.解：先考慮特殊元素（老師）的排法，因老師不排在兩端，故可在中間三個位置上任選一個位置，有衛(wèi)；種，而其余學(xué)生的排法有禹種，所以共有貝；式=72種不同的排法.例5.（2000年全國高考題）乒乓球隊(duì)的10名隊(duì)員中有3名主力隊(duì)員，派5名隊(duì)員參加比賽，3名主力隊(duì)員要安排在第一、三、五位置，其余7名隊(duì)員選2名安排在第二、四位置，那么不同的出場安排共有 種.解：由于第一、三、五位置特殊，只能安排主力隊(duì)員，有禹種排法，而其余7名隊(duì)員選出2名安排在第二、四位置，有摻種排法，所以不同的出場安排共有翅摻=252種.五、多元問題——分類討論法對于元素多，選取情況多，可按要求進(jìn)行分類討論，最后總計。例6.（2003年北京春招）某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目.如果將這兩個節(jié)目插入原節(jié)目單中，那么不同插法的種數(shù)為（A）A.42 B.30 C.20 D.12解：增加的兩個新節(jié)目，可分為相臨與不相臨兩種情況：1?不相臨：共有A2種；2?相臨： .6共有A2A1種。故不同插法的種數(shù)為：A2+A2A1=42，故選Ao例7.（22003年全國高考試題）如圖，一個2地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求WESTWOOD行政職業(yè)能力測驗(yàn)版WESTWOOD

解：區(qū)域1與其他四個區(qū)域相鄰，而其他每個區(qū)域都與三個區(qū)域相鄰，因此，可以涂三種或四種顏色.用三種顏色著色有C；=24種方法，用四種顏色著色有=48種方法,從而共有24+48=72種方法,應(yīng)填72.混合問題——先選后排法對于排列組合的混合應(yīng)用題，可采取先選取元素，后進(jìn)行排列的策略.例8.（2002年北京高考）12名同學(xué)分別到三個不同的路口進(jìn)行車流量的調(diào)查，若每個路口4人，則不同的分配方案共有（ ）A.C：W種B.3咒第時種C.*戊罵種D.讐:種解：本試題屬于均分組問題。則12名同學(xué)均分成3組共有字尹種方法,分配到三個不同的路口的不同的分配方案共有：種，故選A。例9. （2003年北京高考試題）從黃瓜、白菜、油菜、扁豆4種蔬菜品種中選出3種，分別種在不同土質(zhì)的三塊土地上，其中黃瓜必須種植，不同的種植方法共有（）A.24種 B.18種 C.12種 D.6種解:先選后排，分步實(shí)施.由題意，不同的選法有：C32種,不同的排法有：A1?a2,故不同的種植方法共有A1?C2?A2=12，故應(yīng)選C.相同元素分配——檔板分隔法例10.把10本相同的書發(fā)給編號為1、2、3的三個學(xué)生閱覽室，每個閱覽室分得的書的本數(shù)不小于其編號數(shù)，試求不同分法的種數(shù)。請用盡可能多的方法求解，并思考這些方法是否適合更一般的情況？本題考查組合問題。解：先讓2、3號閱覽室依次分得1本書、2本書；再對余下的7本書進(jìn)行分配，保證每個閱覽室至少得一本書，這相當(dāng)于在7本相同書之間的6個“空檔”內(nèi)插入兩個相同“I”（一般可視為“隔板”）共有邙種插法，即有15種分法。轉(zhuǎn)化法:對于某些較復(fù)雜的、或較抽象的排列組合問題，可以利用轉(zhuǎn)化思想,將其化歸為簡單的、具體的問題來求解.例11高二年級8個班,組織一個12個人的年級學(xué)生分會,每班要求至少1人,名額分配方案有多少種?分析此題若直接去考慮的話,就會比較復(fù)雜.但如果我們將其轉(zhuǎn)換為等價的其他問題,就會顯得比較清楚,方法簡單,結(jié)果容易理解.解：此題可以轉(zhuǎn)化為:將12個相同的白球分成8份,有多少種不同的分法問題,因此須把這12個白球排成一排,在11個空檔中放上7個相同的黑球,每個空檔最多放一個,即可將白球分C7 C7成8份,顯然有C171種不同的放法,所以名額分配方案有C171種.第6頁共8頁WESTWOOD行政職業(yè)能力測驗(yàn)版WESTWOOD行政職業(yè)能力測驗(yàn)版WESTWOOD九．剩余法:在組合問題中,有多少取法,就有多少種剩法,他們是一一對應(yīng)的,因此,當(dāng)求取法困難時,可轉(zhuǎn)化為求剩法.例12袋中有5分硬幣23個,1角硬幣10個,如果從袋中取出2元錢,有多少種取法?分析此題是一個組合問題,若是直接考慮取錢的問題的話,情況比較多,也顯得比較凌亂,難以理出頭緒來.但是如果根據(jù)組合數(shù)性質(zhì)考慮剩余問題的話,就會很容易解決問題.解 把所有的硬幣全部取出來,將得到0.05X23+0.10X10=2.15元,所以比2元多0.15元所以剩下0.15元即剩下3個5分或1個5分與1個1角,所以共有 23 23 10種取法.十．對等法:在有些題目中,它的限制條件的肯定與否定是對等的,各占全體的二分之一.在求解中只要求出全體,就可以得到所求.例13 期中安排考試科目9門,語文要在數(shù)學(xué)之前考,有多少種不同的安排順序?分析對于任何一個排列問題,就其中的兩個元素來講的話,他們的排列順序只有兩種情況,并且在整個排列中,他們出現(xiàn)的機(jī)會是均等的,因此要求其中的某一種情況,能夠得到全體,那么問題就可以解決了.并且也避免了問題的復(fù)雜性.解不加任何限制條件，整個排法有P9 種，“語文安排在數(shù)學(xué)之前考”，與“數(shù)學(xué)安排在91P9語文之前考”的排法是相等的,所以語文安排在數(shù)學(xué)之前考的排法共有29種.十．平均分組問題:例14．6本不同