一、分類計(jì)數(shù)原理

完成一件事，有n類辦法.在第1類辦法中有m1種不同的方法，在第2類方法中有m2種不同的方法，……，在第n類方法中有mn種不同的方法，則完成這件事共有

2）首先要根據(jù)具體的問題確定一個(gè)分類標(biāo)準(zhǔn)，在分類標(biāo)準(zhǔn)下進(jìn)行分類，然后對(duì)每類方法計(jì)數(shù).1）各類辦法之間相互獨(dú)立,都能獨(dú)立的完成這件事，要計(jì)算方法種數(shù),只需將各類方法數(shù)相加,因此分類計(jì)數(shù)原理又稱加法原理說明N=m1+m2+…+mn

種不同的方法第一頁，共四十六頁。二、分步計(jì)數(shù)原理

完成一件事，需要分成n個(gè)步驟。做第1步有m1種不同的方法，做第2步有m2種不同的方法，……，做第n步有mn種不同的方法，則完成這件事共有

2）首先要根據(jù)具體問題的特點(diǎn)確定一個(gè)分步的標(biāo)準(zhǔn)，然后對(duì)每步方法計(jì)數(shù).1）各個(gè)步驟相互依存,只有各個(gè)步驟都完成了,這件事才算完成,將各個(gè)步驟的方法數(shù)相乘得到完成這件事的方法總數(shù),又稱乘法原理說明N=m1×m2×…×mn種不同的方法第二頁，共四十六頁。

加法原理

乘法原理聯(lián)系區(qū)別一完成一件事情共有n類辦法，關(guān)鍵詞是“分類”完成一件事情,共分n個(gè)步驟，關(guān)鍵詞是“分步”區(qū)別二每類辦法都能獨(dú)立完成這件事情。每一步得到的只是中間結(jié)果，任何一步都不能能獨(dú)立完成這件事情，缺少任何一步也不能完成這件事情，只有每個(gè)步驟完成了，才能完成這件事情。分類計(jì)數(shù)原理和分步計(jì)數(shù)原理，回答的都是關(guān)于完成一件事情的不同方法的種數(shù)的問題。區(qū)別三各類辦法是互斥的、并列的、獨(dú)立的各步之間是相關(guān)聯(lián)的分類計(jì)數(shù)與分步計(jì)數(shù)原理的區(qū)別和聯(lián)系：第三頁，共四十六頁。如圖，從甲地到乙地有2條路，從乙地到丁地有3條路；從甲地到丙地有4條路可以走，從丙地到丁地有2條路。從甲地到丁地共有多少種不同地走法？課堂練習(xí)甲地丙地丁地乙地N1=2×3=6N2=4×2=8N=N1+N2=14第四頁，共四十六頁。例1.五名學(xué)生報(bào)名參加四項(xiàng)體育比賽，每人限報(bào)一項(xiàng)，報(bào)名方法的種數(shù)為多少？又他們爭(zhēng)奪這四項(xiàng)比賽的冠軍，獲得冠軍的可能性有多少種？

解：（1）5名學(xué)生中任一名均可報(bào)其中的任一項(xiàng)，因此每個(gè)學(xué)生都有4種報(bào)名方法，5名學(xué)生都報(bào)了項(xiàng)目才能算完成這一事件故報(bào)名方法種數(shù)為4×4×4×4×4=種.（2）每個(gè)項(xiàng)目只有一個(gè)冠軍，每一名學(xué)生都可能獲得其中的一項(xiàng)獲軍，因此每個(gè)項(xiàng)目獲冠軍的可能性有5種故有n=5×５×５×５=種.第五頁，共四十六頁。例3.核糖核酸（RNA）分子是在生物細(xì)胞中發(fā)現(xiàn)的化學(xué)成分，一個(gè)RNA分子是一個(gè)有著數(shù)百個(gè)甚至數(shù)千個(gè)位置的長(zhǎng)鏈，長(zhǎng)鏈中每一個(gè)位置上都由一種稱為堿基的化學(xué)成分所占據(jù)，總共有４個(gè)不同的堿基，分別用A，C，G，U表示，在一個(gè)RNA分子中，各種堿基能夠以任意次序出現(xiàn)，所以在任意一個(gè)位置上的堿基與其他位置上的堿基無關(guān)。假設(shè)有一類RNA分子由100個(gè)堿基組成，那么能有多少種不同的RNA分子？UUUAAACCCGGG分析:用100個(gè)位置表示由100個(gè)堿基組成的長(zhǎng)鏈，每個(gè)位置都可以從A、C、G、U中任選一個(gè)來占據(jù)。第1位第2位第3位第100位4種4種4種4種……解：100個(gè)堿基組成的長(zhǎng)鏈共有100個(gè)位置，在每個(gè)位置中，從A、C、G、U中任選一個(gè)來填入，每個(gè)位置有4種填充方法。根據(jù)分步計(jì)數(shù)原理，共有種不同的RNA分子.第六頁，共四十六頁。例4.電子元件很容易實(shí)現(xiàn)電路的通與斷、電位的高與底等兩種狀態(tài)，而這也是最容易控制的兩種狀態(tài)。因此計(jì)算機(jī)內(nèi)部就采用了每一位只有0或1兩種數(shù)字的計(jì)數(shù)法，即二進(jìn)制，為了使計(jì)算機(jī)能夠識(shí)別字符，需要對(duì)字符進(jìn)行編碼，每個(gè)字符可以用一個(gè)或多個(gè)字節(jié)來表示，其中字節(jié)是計(jì)算機(jī)中數(shù)據(jù)存儲(chǔ)的最小計(jì)量單位，每個(gè)字節(jié)由８?jìng)€(gè)二進(jìn)制位構(gòu)成，問（1）一個(gè)字節(jié)（8位）最多可以表示多少個(gè)不同的字符？（2）計(jì)算機(jī)漢字國(guó)標(biāo)碼（GB碼）包含了6763個(gè)漢字，一個(gè)漢字為一個(gè)字符，要對(duì)這些漢字進(jìn)行編碼，每個(gè)漢字至少要用多少個(gè)字節(jié)表示？第1位第2位第3位第8位2種2種2種2種……如00000000，10000000，第七頁，共四十六頁。開始子模塊118條執(zhí)行路徑子模塊328條執(zhí)行路徑子模塊245條執(zhí)行路徑子模塊543條執(zhí)行路徑子模塊438條執(zhí)行路徑結(jié)束A例5.計(jì)算機(jī)編程人員在編寫好程序以后要對(duì)程序進(jìn)行測(cè)試。程序員需要知道到底有多少條執(zhí)行路（即程序從開始到結(jié)束的線），以便知道需要提供多少個(gè)測(cè)試數(shù)據(jù)。一般的，一個(gè)程序模塊又許多子模塊組成，它的一個(gè)具有許多執(zhí)行路徑的程序模塊。問：這個(gè)程序模塊有多少條執(zhí)行路徑？另外為了減少測(cè)試時(shí)間，程序員需要設(shè)法減少測(cè)試次數(shù)，你能幫助程序員設(shè)計(jì)一個(gè)測(cè)試方式，以減少測(cè)試次數(shù)嗎？第八頁，共四十六頁。課堂練習(xí)1、乘積展開后共有幾項(xiàng)？2、某商場(chǎng)有6個(gè)門，如果某人從其中的任意一個(gè)門進(jìn)入商場(chǎng)，并且要求從其他的門出去，共有多少種不同的進(jìn)出商場(chǎng)的方式？第九頁，共四十六頁?；靖拍?、排列：一般地，從n個(gè)不同中取出m(mn)個(gè)元素，按照一定的順序排成一列，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列。說明：1、元素不能重復(fù)。n個(gè)中不能重復(fù)，m個(gè)中也不能重復(fù)。2、“按一定順序”就是與位置有關(guān)，這是判斷一個(gè)問題是否是排列問題的關(guān)鍵。3、兩個(gè)排列相同，當(dāng)且僅當(dāng)這兩個(gè)排列中的元素完全相同，而且元素的排列順序也完全相同。4、m＜n時(shí)的排列叫選排列，m＝n時(shí)的排列叫全排列。5、為了使寫出的所有排列情況既不重復(fù)也不遺漏，最好采用“樹形圖”。第十頁，共四十六頁。2、排列數(shù)：

從n個(gè)不同的元素中取出m(m≤n)個(gè)元素的所有排列的個(gè)數(shù)，叫做從n個(gè)不同的元素中取出m個(gè)元素的排列數(shù)。用符號(hào)表示。“排列”和“排列數(shù)”有什么區(qū)別和聯(lián)系？排列數(shù)，而不表示具體的排列。所有排列的個(gè)數(shù)，是一個(gè)數(shù)；“排列數(shù)”是指從個(gè)不同元素中，任取個(gè)元素的所以符號(hào)只表示“一個(gè)排列”是指：從個(gè)不同元素中，任取按照一定的順序排成一列，不是數(shù)；個(gè)元素第十一頁，共四十六頁。(1)排列數(shù)公式（1）：當(dāng)m＝n時(shí)，正整數(shù)1到n的連乘積，叫做n的階乘，用表示。n個(gè)不同元素的全排列公式：(2)排列數(shù)公式（2）：說明：1、排列數(shù)公式的第一個(gè)常用來計(jì)算，第二個(gè)常用來證明。為了使當(dāng)m＝n時(shí)上面的公式也成立，規(guī)定：2、對(duì)于這個(gè)條件要留意，往往是解方程時(shí)的隱含條件。第十二頁，共四十六頁。例3：某信號(hào)兵用紅，黃，藍(lán)3面旗從上到下掛在豎直的旗桿上表示信號(hào)，每次可以任掛1面、2面或3面，并且不同的順序表示不同的信號(hào)，一共可以表示多少種不同的信號(hào)？例4：用0到9這10個(gè)數(shù)字，可以組成多少個(gè)沒有重復(fù)數(shù)字的三位數(shù)？百位十位個(gè)位解法一：對(duì)排列方法分步思考。從位置出發(fā)第十三頁，共四十六頁。解法二：對(duì)排列方法分類思考。符合條件的三位數(shù)可分為兩類：根據(jù)加法原理從元素出發(fā)分析解法三：間接法.從0到9這十個(gè)數(shù)字中任取三個(gè)數(shù)字的排列數(shù)為，

所求的三位數(shù)的個(gè)數(shù)是其中以0為排頭的排列數(shù)為.逆向思維法百位十位個(gè)位第十四頁，共四十六頁。百位十位個(gè)位千位萬位例5：由數(shù)字1、2、3、4、5組成沒有重復(fù)數(shù)字的五位數(shù)，其中小于50000的偶數(shù)共有多少個(gè)？有約束條件的排列問題第十五頁，共四十六頁。百位十位個(gè)位千位萬位例5：由數(shù)字1、2、3、4、5組成沒有重復(fù)數(shù)字的五位數(shù)，其中小于50000的偶數(shù)共有多少個(gè)？有約束條件的排列問題第十六頁，共四十六頁。

例

4男3女在一起排隊(duì)，滿足下列站法有多少種（1）3女站前排，4男站后排（2）前排站3人，后排站4人（3）4男必須站一塊（4）4男全部相鄰，且3女全部相鄰（5）甲和乙中間有且僅有2人（6）3女互不相鄰（7）4男互不相鄰（8）3女互不相鄰，且4男互不相鄰（9)甲乙必須相鄰，丙丁不相鄰（10）甲不站左，乙不站右（11）甲必須在乙的右邊（12）甲乙丙必須從左到右排列第十七頁，共四十六頁。小結(jié)：常見解題策略：⑴特殊元素，優(yōu)先安排⑵特殊位置，優(yōu)先安排；⑶正難則反，等價(jià)轉(zhuǎn)換;(4)相鄰問題，捆綁處理(5)不相鄰問題，插空法（6）定序問題，除法處理（7）分排問題，直排處理；第十八頁，共四十六頁。組合定義:

一般地，從n個(gè)不同元素中取出m（m≤n）個(gè)元素并成一組，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)組合．概念講解第十九頁，共四十六頁。

從n個(gè)不同元素中取出m（m≤n）個(gè)元素的所有組合的個(gè)數(shù)，叫做從n個(gè)不同元素中取出m個(gè)元素的組合數(shù)，用符號(hào)表示.如:從a,b,c三個(gè)不同的元素中取出兩個(gè)元素的所有組合個(gè)數(shù)是:如:已知4個(gè)元素a、b、c、d,寫出每次取出兩個(gè)元素的所有組合個(gè)數(shù)是：概念講解組合數(shù):注意：是一個(gè)數(shù)，應(yīng)該把它與“組合”區(qū)別開來．

第二十頁，共四十六頁。組合數(shù)公式

排列與組合是有區(qū)別的，但它們又有聯(lián)系．根據(jù)分步計(jì)數(shù)原理，得到：因此：

一般地，求從個(gè)不同元素中取出個(gè)元素的排列數(shù)，可以分為以下2步：

第1步，先求出從這個(gè)不同元素中取出個(gè)元素的組合數(shù)．

第2步，求每一個(gè)組合中個(gè)元素的全排列數(shù)．

這里，且，這個(gè)公式叫做組合數(shù)公式．

概念講解第二十一頁，共四十六頁。組合數(shù)公式:

從n個(gè)不同元中取出m個(gè)元素的排列數(shù)概念講解第二十二頁，共四十六頁。（2）一個(gè)口袋內(nèi)裝有大小相同的7個(gè)白球和1個(gè)黑球．⑴從口袋內(nèi)取出3個(gè)球，共有多少種取法？⑵從口袋內(nèi)取出3個(gè)球，使其中含有1個(gè)黑球，有多少種取法？⑶從口袋內(nèi)取出3個(gè)球，使其中不含黑球，有多少種取法？

⑵

⑶

解：（1）

（1）第二十三頁，共四十六頁。性質(zhì)2第二十四頁，共四十六頁。例１計(jì)算：第二十五頁，共四十六頁。一、等分組與不等分組問題例3、6本不同的書，按下列條件，各有多少種不同的分法；（1）分給甲、乙、丙三人，每人兩本；（2）分成三份，每份兩本；（3）分成三份，一份1本，一份2本，一份3本；（4）分給甲、乙、丙3人，一人1本，一人2本，一人3本；（5）分給甲、乙、丙3人，每人至少一本；（6）分給5個(gè)人，每人至少一本；（7）6本相同的書，分給甲乙丙三人，每人至少一本。第二十六頁，共四十六頁。練習(xí)：(1)今有10件不同獎(jiǎng)品,從中選6件分成三份,二份各1件,另一份4件,有多少種分法?(2)今有10件不同獎(jiǎng)品,從中選6件分給甲乙丙三人,每人二件有多少種分法?解:(1)(2)第二十七頁，共四十六頁。例4、某城新建的一條道路上有12只路燈，為了節(jié)省用電而不影響正常的照明，可以熄滅其中三盞燈，但兩端的燈不能熄滅，也不能熄滅相鄰的兩盞燈，可以熄滅的方法共有（）（A）種（B）種（C）種（D）種二、不相鄰問題插空法第二十八頁，共四十六頁。三、混合問題，先“組”后“排”例5對(duì)某種產(chǎn)品的6件不同的正品和4件不同的次品,一一進(jìn)行測(cè)試，至區(qū)分出所有次品為止，若所有次品恰好在第5次測(cè)試時(shí)全部發(fā)現(xiàn),則這樣的測(cè)試方法有幾種可能？解：由題意知前5次測(cè)試恰有4次測(cè)到次品，且第5次測(cè)試是次品。故有：種可能。第二十九頁，共四十六頁。練習(xí)：1、某學(xué)習(xí)小組有5個(gè)男生3個(gè)女生，從中選3名男生和1名女生參加三項(xiàng)競(jìng)賽活動(dòng)，每項(xiàng)活動(dòng)至少有1人參加，則有不同參賽方法______種.解：采用先組后排方法:2、3名醫(yī)生和6名護(hù)士被分配到3所學(xué)校為學(xué)生體檢,每校分配1名醫(yī)生和2名護(hù)