記數(shù)的基本原理與排列組合

基本原理組合排列排列數(shù)公式組合數(shù)公式應(yīng)用問題知識結(jié)構(gòu)

分類計數(shù)原理，分步計數(shù)原理分類計數(shù)原理分步計數(shù)原理原理

完成一件事可以有n類辦法，在第一類中有m1種不同的方法，在第二類中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法，那么完成這件事共N=m1+m2+……+mn種不同的方法。

完成一件事需要分成n個步驟，第一步有m1種不同的方法，第二步有m2種不同的方法，……，第n步有mn種不同的方法，那么完成這件事共N=m1×m2×……×mn種不同的方法。區(qū)別分類計數(shù)原理針對的是“分類”問題，其中各種方法相互獨立，用其中任何一種方法都可完成這件事。分步計數(shù)原理針對的是“分步”問題，各步方法相互依存，只有各步都完成才能完成這件事。

例、書架上第1層放有4本不同的計算機書,第2層放有3本不同的文藝書,第3層放有2本不同的體育雜志.(2)從書架的第1、2、3層各取1本書,有多少種不同取法?N＝4＋3+2＝9N＝4×3×2＝24(1)從書架上任取1本書,有多少種不同的取法?例由數(shù)字0,1,2,3,4可以組成多少個三位數(shù)？（各位上的數(shù)字可以重復(fù)）解：第一步：選百位上的數(shù)字，有4種；第二步：選十位上的數(shù)字，有5種；第三步：選個位上的數(shù)字，有5種；所以共有4×5×5=100個。練習(xí)：有8名考生，報考5所院校，每人限報一所，不同的報法有58填空題1．由數(shù)字2，3，4，5可組成________個三位數(shù)，_________個四位數(shù)，________個五位數(shù)．２．用1，2，3…，9九個數(shù)字，可組成__________個四位數(shù)，_________個六位數(shù)．３．商店里有15種上衣，18種褲子，某人要買一件上衣或一條褲子，共有___種不同的選法．要買上衣、褲子各一件，共有_________種不同的選法．33；270①什么叫做從n個不同元素中取出m個元素的一個排列？從n個不同元素中取出m（m≤n）個元素，按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列.從n個不同的元素中取出m（m≤n)個元素的所有排列的個數(shù)，叫做從n個不同元素中取出m個元素的排列數(shù).用符號表示②什么叫做從n個不同元素中取出m個元素的排列數(shù)？③排列數(shù)的兩個公式是什么？（n，m∈N*，m≤n）125組合定義：一般地說，從n個不同元素中，任取m(m≤n)個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合。組合數(shù)公式：組合數(shù)的兩個性質(zhì):（1）（2）(1)x=7或x=9(2)n=8排列組合定義從n個不同元素中，任取m(m≤n)個不同元素按照一定順序排成一列，叫做從n個不同元素中取出m個不同元素的一個排列。從n個不同的元素中，任取m（m≤n）個不同的元素并成一組，叫做從n個不同的元素中取出m個不同的元素的一個組合。區(qū)別與順序有關(guān)與順序無關(guān)判定

看取出的兩個元素互換位置是否為同一種方法，若不是，則是排列問題；若是，則是組合。公式排列與組合例1：（1）7位同學(xué)站成一排，共有多少種不同的排法？分析：問題可以看作7個元素的全排列.(2)7位同學(xué)站成兩排(前3后4)，共有多少種不同的排法？分析:根據(jù)分步計數(shù)原理(3)7位同學(xué)站成一排，其中甲站在中間的位置,共有多少種不同的排法？分析:可看作甲固定,其余全排列(4)7位同學(xué)站成一排，甲、乙只能站在兩端的排法共有多少種？解:將問題分步第一步:甲乙站兩端有種第二步:其余5名同學(xué)全排列有種答：共有2400種不同的排列方法。(5)7位同學(xué)站成一排，甲、乙不能站在排頭和排尾的排法共有多少種？解法一:(特殊位置法)第一步:從其余5位同學(xué)中找2人站排頭和排尾,有種;第二步:剩下的全排列,有種;答：共有2400種不同的排列方法。解法二:(排除法)先全排列有種,其中甲或乙站排頭有種,甲或乙站排尾的有種,甲乙分別站在排頭和排尾的有種.答：共有2400種不同的排列方法。(5)7位同學(xué)站成一排，甲、乙不能站在排頭和排尾的排法共有多少種？了解！練習(xí)：由0,1,2,3,4,5組成無重復(fù)數(shù)字的數(shù)：（1）四位數(shù)有多少個？（2）四位奇數(shù)有多少個？（3）四位偶數(shù)有多少個？（4）能被5整除的四位數(shù)有多少個？（5）比2400大的四位數(shù)有多少個？練習(xí)：從8名男生，2名女生中，任選三名開會（1）共有多少種不同的選法；（2）恰有1名女生的選法多少種；（3）至少有1名女生的選法多少種；（4）最多有1名女生的選法多少種？捆綁法:對于相鄰問題,常常先將要相鄰的元素捆綁在一起,視作為一個元素,與其余元素全排列,再松綁后它們之間進行全排列.這種方法就是捆綁法.例3：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。若三個女孩要站在一起，有多少種不同的排法？解：將三個女孩看作一人與四個男孩排隊，有

種排法，而三個女孩之間有種排法，所以不同的排法共有：（種）。捆綁法若三個女孩要站在一起，四個男孩也要站在一起，有多少種不同的排法？不同的排法有：（種）說一說捆綁法一般適用于問題的處理。相鄰例4：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。插空法:對于不相鄰問題,先將其余元素全排列,再將這些不相鄰的元素插入空擋中,這種方法就是插空法.若三個女孩互不相鄰，有多少種不同的排法？解：先把四個男孩排成一排有種排法，在每一排列中有五個空檔（包括兩端），再把三個女孩插入空檔中有種方法，所以共有：（種）排法。插空法例5：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。男生、女生相間排列，有多少種不同的排法？解：先把四個男孩排成一排有種排法，在每一排列中有五個空檔（包括兩端），再把三個女孩插入空檔中有種方法，所以共有：（種）排法。插空法例6：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。甲、乙兩人的兩邊必須有其他人，有多少種不同的排法？解：先把其余五人排成一排有種排法，在每一排列中有四個空檔（不包括兩端），再把甲、乙插入空檔中有種方法，所以共有：（種）排法。插空法例7：七個家庭一起外出旅游，若其中四家是一個男孩，三家是一個女孩，現(xiàn)將這七個小孩站成一排照相留念。例1

學(xué)校組織老師學(xué)生一起看電影，同一排電影票12張。8個學(xué)生，4個老師，要求老師在學(xué)生之間，且老師互不相鄰，共有多少種不同的坐法？解

先排學(xué)生共有種排法,然后把老師插入學(xué)生之間的空檔，共有7個空檔可插,選其中的4個空檔,共有種選法.根據(jù)乘法原理,共有的不同坐法為種.結(jié)論1

插空法:對于某兩個元素或者幾個元素要求不相鄰的問題,可以用插入法.即先排好沒有限制條件的元素,然后將有限制條件的元素按要求插入排好元素的空檔之中即可.分析此題涉及到的是不相鄰問題,并且是對老師有特殊的要求,因此老師是特殊元素,在解決時就要特殊對待.所涉及問題是排列問題.例2

5個男生3個女生排成一排,3個女生要排在一起,有多少種不同的排法?

解

因為女生要排在一起,所以可以將3個女生看成是一個人,與5個男生作全排列,有種排法,其中女生內(nèi)部也有種排法,根據(jù)乘法原理,共有種不同的排法.結(jié)論2

捆綁法:要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素,再與其它元素一起作排列,同時要注意合并元素內(nèi)部也可以作排列.分析此題涉及到的是排隊問題,對于女生有特殊的限制,因此,女生是特殊元素,并且要求她們要相鄰,因此可以將她們看成是一個元素來解決問題.例3

某班里有43位同學(xué),從中任抽5人,正、副班長、團支部書記至少有一人在內(nèi)的抽法有多少種?解

43人中任抽5人的方法有種,正副班長,團支部書記都不在內(nèi)的抽法有種,所以正副班長,團支部書記至少有1人在內(nèi)的抽法有種.結(jié)論6

排除法:有些問題,正面直接考慮比較復(fù)雜,而它的反面往往比較簡捷,可以先求出它的反面,再從整體中排除.分析此題若是直接去考慮的話,就要將問題分成好幾種情況,這樣解題的話,容易造成各種情況遺漏或者重復(fù)的情況.而如果從此問題相反的方面去考慮的話,不但容易理解,而且在計算中也是非常的簡便.這樣就可以簡化計算過程.練習(xí)：用0，1，2，3，4這五個數(shù)，組成沒重復(fù)數(shù)字的三位數(shù)，其中1不在個位的數(shù)共有_______種。

分析：五個數(shù)組成三位數(shù)的全排列有個，0排在首位的有個，1排在末尾的有，減掉這兩種不合條件的排法數(shù)，再加回百位為0同時個位為1的排列數(shù)（為什么？）故共有種。例題2：4個男同學(xué)，3個女同學(xué)站成一排．(1)3個女同學(xué)必須排在一起，有多少種不同的排法？解答：(1)3個女同學(xué)是特殊元素，我們先把她們排好，共有種排法；由于3個女同學(xué)必須排在一起，我們可視排好的女同學(xué)為一整體，再與男同學(xué)排隊，這時是5個元素的全排列，應(yīng)有種排法，由分步計數(shù)的原理,有＝720種不同排法．例題2：4個男同學(xué)，3個女同學(xué)站成一排(2)任何兩個女同學(xué)彼此不相鄰，有多少種不同的排法？解答：(2)先將男生排好，共有種排法，再在這4個男生的中間及兩頭的5個空檔中插入3個女生有種方案，故符合條件的排法共有＝1440種不同排法．例題3：4個男同學(xué)，3個女同學(xué)站成一排(3)其中甲、乙兩同學(xué)之間必須恰有3人，有多少種不同的排法？解答：(3)甲、乙2人先排好，有種排法，再從余下5人中選3人排在甲、乙2人中間，有種排法，這時把已排好的5人視為一整體，與最后剩下的2人再排，又有種排法，這樣總共有＝720種不同排法．例題4：4個男同學(xué)，3個女同學(xué)站成一排(4)甲、乙兩人相鄰，但都不與丙相鄰，有多少種不同的排法？

．解答：(4)先排甲、乙和丙3人以外的其他4人，有種排法；由于甲、乙要相鄰，故再把甲、乙排好，有種排法；最后把甲、乙排好的這個整體與丙分別插入原先排好的4人的空檔中有種排法．這樣，總共有＝960種不同排法．例題5：4個男同學(xué)，3個女同學(xué)站成一排(5)女同學(xué)從左到右按高矮順序排，有多少種不同的排法？(3個女生身高互不相等)．解答：(5)從7個位置中選出4個位置把男生排好，則有種排法．然后再在余下的3個空位置中排女生，由于女生要按身體高矮排列，故僅有一種排法．這樣總共有＝840種不同排法.住店法解決“允許重復(fù)排列問題”要注意區(qū)分兩類元素：

一類元素可以重復(fù)，另一類不能重復(fù)，把不能重復(fù)的元素看作“客”，能重復(fù)的元素看作“店”，再利用乘法原理直接求解。例6

七名學(xué)生爭奪五項冠軍，每項冠軍只能由一人獲得，獲得冠軍的可能的種數(shù)有（）A.B.CD.分析：因同一學(xué)生可以同時奪得n項冠軍，故學(xué)生可重復(fù)排列，將七名學(xué)生看作7家“店”，五項冠軍看作5名“客