分類加法計數(shù)原理與分步乘法計數(shù)原理（3）課件高二下學(xué)期數(shù)學(xué)人教A版選擇性

6.1分類加法計數(shù)原理與分步乘法計數(shù)原理

(3)例1：

計算機(jī)編程人員在編寫好程序以后需要對程序進(jìn)行測試.程序員需要知道到底有多少條執(zhí)行路徑(程序從開始到結(jié)束的路線)，以便知道需要提供多少個測試數(shù)據(jù).一般地，一個程序模塊由許多子模塊組成.下圖是一個具有許多執(zhí)行路徑的程序模塊，它有多少條執(zhí)行路徑?另外，為了減少測試時間，程序員需要設(shè)法減少測試次數(shù).你能幫助程序員設(shè)計一個測試方法，以減少測試次數(shù)嗎?例題課本P8分析：整個模塊的任意一條執(zhí)行路徑都分兩步完成：第1步是從開始執(zhí)行到A點(diǎn)；第2是從A點(diǎn)執(zhí)行到結(jié)束.而第1步可由子模塊1、子模塊2、子模塊3中任何一個來完成；第2步可由子模塊4、子模塊5中任何一個來完成.因此，分析一條指令在整個的模塊執(zhí)行路徑需要用到兩個計數(shù)原理.解：由分類加法計數(shù)原理，子模塊1、子模塊2、子模塊3中的子路徑條數(shù)共為

18+45+28=91；子模塊4、子模塊5中的子路徑條數(shù)共

38+43=81.又由分步乘法計數(shù)原理，整個模塊的執(zhí)行路徑條數(shù)共為

91×81=7371.再測試各個模塊之間的信息交流是否正常，只需要測試程序第1步中的各個子模塊和第2步中的各個子模塊之間的信息交流是否正常，需要的測試次數(shù)為3×2=6.如果每個子模塊都工作正常，并且各個子模塊之間的信息交流也正常，那么整個程序模塊就工作正常，這樣，測試整個模塊的次數(shù)就變?yōu)?72+6=178.顯然，178與7371的差距是非常大的.在實(shí)際測試中，程序員總是把每一個子模塊看成一個黑箱，即通過只考察是否執(zhí)行了正確的子模塊的方式來測試整個模塊，這樣，他可以先分別單獨(dú)測試5個模塊，以考察每個子模塊的工作是否正常，總共需要的測試次數(shù)為18+45+28+38+43=172.你看出了程序員是如何實(shí)現(xiàn)減少測試次數(shù)的嗎？？解：根據(jù)多項式乘法法則，要得到展開式的項數(shù)，可以分3步完成：第1步，從第一個因式中任取一項，有3種方法；第2步，從第2個因式中任取一項，有3種方法；第3步，從第3個因式中任取一項，有5種方法．根據(jù)分步乘法計數(shù)原理，展開后共有的項數(shù)為N＝3×3×5＝45.1.乘積(a1+a2+a3)(b1+b2+b3)(c1+c2+c3+c4+c5)展開后共有多少項?課本P11練習(xí)2.某商場有6個門，如果某人從其中的任意一個門進(jìn)人商場，并且要求從其他的門出去，那么共有多少種不同的進(jìn)出商場的方式?解：要完成這件事，可以分2步完成：先從6個門中選一個進(jìn)入，再從其余5個門中選一個出去，故共有6×5＝30種不同的進(jìn)出商場的方式．課本P11例2：通常，我國民用汽車號牌的編號由兩部分組成:第一部分為用漢字表示的省、自治區(qū)、直轄市簡稱和用英文字母表示的發(fā)牌機(jī)關(guān)代號，第二部分為由阿拉伯?dāng)?shù)字和英文字母組成的序號，如圖所示.其中，序號的編碼規(guī)則為:(1)由10個阿拉伯?dāng)?shù)字和除O，I之外的24個英文字母組成；(2)最多只能有2個英文字母.如果某地級市發(fā)牌機(jī)關(guān)采用5位序號編碼，那么這個發(fā)牌機(jī)關(guān)最多能發(fā)放多少張汽車號牌?例題0冀AJR005省、自治區(qū)、直轄市簡稱發(fā)牌機(jī)關(guān)代號序號課本P9分析：由號牌編號的組成可知:序號的個數(shù)決定了發(fā)牌機(jī)所能發(fā)放的最多號牌數(shù).按序號編碼規(guī)則可知，每個序號中的數(shù)字、字母都是可重復(fù)的，并且可將序號分為三類：沒有字母，有1個字母，有2個字母.以字母所在位置為分類標(biāo)準(zhǔn)，可將有1個字母的序號分為五個子類，將有2個字母的序號分為十個子類.0冀AJR005省、自治區(qū)、直轄市簡稱發(fā)牌機(jī)關(guān)代號序號解:由號牌編號的組成可知，這個發(fā)牌機(jī)關(guān)所能發(fā)放的最多號牌數(shù)就是序號的個數(shù).根據(jù)序號編碼規(guī)則，5位序號可以分為三類：沒有字母，有1個字母，有2個字母.(1)當(dāng)沒有字母時，序號的每一位都是數(shù)字，確定一個序號可以分5個步驟，每一步都可以從10個數(shù)字中選1個，各有10種選法，根據(jù)分步乘法計數(shù)原理，這類號牌張數(shù)為10×10×10×10×10=100000.(2)當(dāng)有1個字母時，這個字母可以分別在序號的第1位、第2位、第3位、第4位或第5位，這類序號可以分為五個子類.當(dāng)?shù)?位是字母時,分5個步驟確定一個序號中的字母和數(shù)字:第1步,從24個字母中選1個放在第1位,有24種選法;第2～5步都是從10個數(shù)字中選1個放在相應(yīng)的位置,各有10種選法,根據(jù)分步乘法計數(shù)原理,號牌張數(shù)為24×10×10×10×10=240000.同樣，其余四個子類號牌也各有240000張.根據(jù)分類加法計數(shù)原理，這類號牌張數(shù)一共為

240000+240000+240000+240000+240000=1200000.(3)當(dāng)有2個字母時，根據(jù)這2個字母在序號中的位置，可以將這類序號分為十個子類：第1位和第2位，第1位和第3位，第1位和第4位，第1位和第5位，第2位和第3位，第2位和第4位，第2位和第5位，第3位和第4位，第3位和第5位，第4位和第5位.當(dāng)?shù)?位和第2位是字母時，分5個步驟確定一個序號中的字母和數(shù)字：第1,2步都是從24個字母中選1個分別放在第1位、第2位，各有24種選法；第3~5步都是從10個數(shù)字中選1個放在相應(yīng)的位置，各有10種選法，根據(jù)分步乘法計數(shù)原理，號牌張數(shù)為

24×24×10×10×10=576000.同樣，其余九個子類號牌也各有576000張.于是，這類號牌張數(shù)一共為

576000×10=5760000.綜合(1)(2)(3),根據(jù)分類加法計數(shù)原理，這個發(fā)牌機(jī)關(guān)最多能發(fā)放的汽車號牌張數(shù)為

100000+1200000+5760000=7060000.思考：乘法運(yùn)算是特定條件下加法運(yùn)算的簡化，分步乘法計數(shù)原理和分類加法計數(shù)原理也有這種類似的關(guān)系嗎？(1)有些計數(shù)問題既需要進(jìn)行“分類”，又需要進(jìn)行“分步”，此時就要注意綜合運(yùn)用兩個計數(shù)原理來解決問題.解決這類問題時，首先要明確是先“分類”后“分步”，還是先“分步”后“分類”；其次，在“分類”和“分步”的過程中，均要有明確的分類標(biāo)準(zhǔn)和分步程序．(2)在既需要分類又需要分步的題目中，可以先根據(jù)對題意的理解，合理地畫出示意圖（如樹形圖）或列出表格，使問題的實(shí)質(zhì)能直觀地表示出來.任意畫一條直線，在直線上任取n個分點(diǎn).(1)從這n個分點(diǎn)中任取2個點(diǎn)形成一條線段，可得到多少條線段?課本P11練習(xí)任意畫一條直線，在直線上任取n個分點(diǎn).(2)從這n個分點(diǎn)中任取2個點(diǎn)形成一個向量，可得到多少個向量?課本P11例3：用0、1、2、3、4這5個數(shù)字可組成多少個無重復(fù)數(shù)字的：（1）四位數(shù)？例題分析：完成“組成無重復(fù)數(shù)字的四位數(shù)”這件事需要分4步，我們將完成這件事用圖表示出來：千位百位十位個位其中的“千位”能不能取“0”？

.“0”是特殊元素，“千位”是特殊位置，特殊元素特殊位置要優(yōu)先考慮.不能解：完成“組成無重復(fù)數(shù)字的四位數(shù)”這件事需要分4步：千位百位十位個位第1步,安排千位有

種選擇；

種44

種

種

種第2步,安排百位有

種選擇；44第3步,安排十位有

種選擇；33第4步,安排個位有

種選擇.22根據(jù)分步乘法計數(shù)原理，一共有

種方法.4×4×3×2=96例3：用0、1、2、3、4這5個數(shù)字可組成多少個無重復(fù)數(shù)字的：（2）四位奇數(shù)？千位百位十位個位分析：完成“組成無重復(fù)數(shù)字的四位奇數(shù)”這件事，既要注意“千位”不能取“0”，還要注意“個位”只能取數(shù)字

，因此，完成這件事可以分兩類.1，3特殊元素特殊位置要優(yōu)先考慮.解法1：完成“組成無重復(fù)數(shù)字的四位奇數(shù)”這件事可以分兩類：千位百位十位個位第1類,個位數(shù)字是1，則安排千位有

種選擇，

種33

種

種

種安排百位有

種選擇，33安排十位有

種選擇.221根據(jù)分步乘法計數(shù)原理，一共有

種方法.3×3×2=18第2類,個位數(shù)字是3，同理一共有

種方法.3×3×2=18根據(jù)分類加法計數(shù)原理，總共有

種方法.18＋18=36解法2：完成“組成無重復(fù)數(shù)字的奇四位數(shù)”這件事需要分4步：千位百位十位個位第1步,安排個位有

種選擇，

種23

種

種

種第2步,安排千位有

種選擇；33第3步,安排百位有

種選擇；23第4步,安排十位有

種選擇.22根據(jù)分步乘法計數(shù)原理，一共有

種方法.2×3×3×2=36即1或3；練習(xí)解：要確定所有的兩位數(shù)中，個位數(shù)字小于十位數(shù)字的個數(shù)，可以分類完成：第1類，十位數(shù)字為1，有1個；第2類，十位數(shù)字為2，有2個；第3類，十位數(shù)字為3，有3個；第4類，十位數(shù)字為4，有4個；第5類，十位數(shù)字為5，有5個；第6類，十位數(shù)字為6，有6個；第7類，十位數(shù)字為7，有7個；第8類，十位數(shù)字為8，有8個；第9類，十位數(shù)字為9，有9個．根據(jù)分類加法計數(shù)原理，這樣的兩位數(shù)的個數(shù)為1＋2＋3＋4＋5＋6＋7＋8＋9＝45．2.在所有的兩位數(shù)中，個位數(shù)字小于十位數(shù)字的有多少個?課本P11例4：如圖所示，要給“創(chuàng)”、“新”、“設(shè)”、“計”四個區(qū)域分別涂上3種不同顏色中的某一種，允許同一種顏色使用多次，但相鄰區(qū)域必須涂不同的顏色，有多少種不同的涂色方法？解：“創(chuàng)”、“新”、“設(shè)”、“計”四個區(qū)域依次涂色，分四步.第1步，涂“創(chuàng)”區(qū)域，有3種選擇；第2步，涂“新”區(qū)域，有2種選擇；第3步，涂“設(shè)”區(qū)域，由于它與“創(chuàng)”、“新”區(qū)域顏色不同，有1種選擇；例題解：“創(chuàng)”、“新”、“設(shè)”、“計”四個區(qū)域依次涂色，分四步.第1步，涂“創(chuàng)”區(qū)域，有3種選擇；第2步，涂“新”區(qū)域，有2種選擇；第3步，涂“設(shè)”區(qū)域，由于它與“創(chuàng)”、“新”區(qū)域顏色不同，有1種選擇；第4步，涂“計”區(qū)域，由于它與“創(chuàng)”“設(shè)”區(qū)域顏色不同，有1種選擇.所以根據(jù)分步乘法計數(shù)原理，得不同的涂色方法共有3×2×1×1＝6(種).求解涂色(種植)問題一般是直接利用兩個計數(shù)原理求解，常用方法有：(1)按區(qū)域的不同以區(qū)域為主分步計數(shù)，用分步乘法計數(shù)原理分析；(2)以顏色(種植作物)為主分類討論，適用于“區(qū)域、點(diǎn)、線段”問題，用分類加法計數(shù)原理分析；(3)對于涂色(立方體)問題將空間問題平面化，轉(zhuǎn)化為平面區(qū)域涂色問題.反思?xì)w納1.長方形的兩條對角線把長方形分成四部分，如圖用五種不同的顏色給這四部分涂色，每一部分涂一種顏色，任何相鄰（具有公共邊）的兩部分涂不同顏色，問有多少種不同的涂色方法？ABCD解：若A,C同色，則不同的涂色方法有5×4×4＝80(種).(2)若A,C不同色，則不同的涂色方法有5×4×3×3＝180(種).綜上所述，由分類加法計數(shù)原理得：共有80＋180＝260(種).練習(xí)2.如圖所示，一環(huán)形花壇分成A，B，C，D四塊，現(xiàn)有四種不同的花供選種，要求在每塊里種一種花，且相鄰的兩塊種不同的花，則不同的種法種數(shù)為(

)A.96 B.84 C.60 D.48解析：依次種A，B，C，D4塊，當(dāng)C與A種同一種花時，有4×3×1×3＝36(種)種法；當(dāng)C與A所種的花不同時，有4×3×2×2＝48(種)種法.由分類加法計數(shù)原理知，不同的種法種數(shù)為36＋48＝84.1.某市汽車牌照號碼可以上網(wǎng)自編，但規(guī)定從左數(shù)第2個號碼只能從字母B，C，D中選擇，其他四個號碼可以從0～9這10個數(shù)字中選擇(數(shù)字可以重復(fù)).若某車主第1個號碼(從左到右)只想在數(shù)字3,5,6,8,9中選擇，其他號碼只想在1,3,6,9中選擇，則他可選的車牌號碼的所有可能情況有（

）A.180種 B.360種

C.720種D.960種解析：按照車主的要求，從左到右第1個號碼有5種選法，第2個號碼有3種選法，其余3個號碼各有4種選法，因此共有5×3×4×4×4＝960(種)情況.隨堂檢測2.從6名志愿者中選4人分別從事翻譯、導(dǎo)游、導(dǎo)購、保潔四項不同的工作，若其中甲、乙2名志愿者不能從事翻譯工作，則選派方案共有（

）A.280種 B.240種

C.180種 D.96種解析：由于甲、乙不能從事翻譯工作，因此翻譯工作從余下的4名志愿者中選1人，有4種選法.后面三項工作的選法有5×4×3種，因此共有4×5×4×3＝240(種)選派方案.解：(1)由分步計數(shù)原理得，所求三位數(shù)共有5×5×4＝100個．3.用0,1,2,3,4,5這6個數(shù)字：(1)可以組成______個數(shù)字不重復(fù)的三位數(shù);(2)可以組成______個數(shù)字允許重復(fù)的三位數(shù);(3)可以組成______個大于3000，小于5421的數(shù)字不重復(fù)的四位數(shù)．(2)由分步計數(shù)原理得，所求三位數(shù)共有5×6×6＝180個．3.用0,1,2,3,4,5這6個數(shù)字：(3)可以組成______個大于3000，小于5421的數(shù)字不重復(fù)的四位數(shù)．解：分四類：

①千位數(shù)字為3,4之一時，有2×5×4×3=120個；②千位數(shù)字為5，百位數(shù)字為0,1,2,3之一時，有4×4×3=48個；

③千位數(shù)字是5百位數(shù)字是4，十位數(shù)字是0,1之一時，有2×3=6個；

④千位數(shù)字是5百位數(shù)字是4，十位數(shù)字是2時，有1個；所以所求四位數(shù)共有120+48+6+1=175個．解法1：4.將一個四棱錐的每個頂點(diǎn)染上一種顏色，使同一條棱的兩端點(diǎn)異色，如果只有五種顏色可供使用，那么不同的染色方法總數(shù)是多少？SABCD若A,C同色，則不同的染色方法有5×4×3×3＝180(種).(2)若A,C不同色，則不同的染色方法有5×4×3×2×2＝240(種).所以不同的染色方法共有180＋240＝420(種).SABCD解法2：從顏色的種數(shù)進(jìn)行分類：若染5種顏色，則不同的染色方法有5×4×3×2×1＝120(種).(2)若染4種顏色，則不同的染色方法有5×4×3×2×2＝240(種).(3)若染3種顏色，則不同的染色方法有5×4×3＝60(種).所以不同的染色方法共有120＋240＋60＝420(種).4.將一個四棱錐的每個頂點(diǎn)染上一種顏色，使同一條棱的兩端點(diǎn)異色，如果只有五種顏色可供使用，那么不同的染色方法總數(shù)是多少？5.現(xiàn)有高一四個班學(xué)生34個，其中一、二、三、四班各7人、8人、9人、10人，他們自愿組成數(shù)學(xué)課外小組．(1)選其中一人為負(fù)責(zé)人，有多少種不同的選法？(2)每班選一名組長，有多少種不同的選法？(3)推選二人作中心發(fā)言，這二人需來自不同的班級，有多少種不同的選法？解：

(1)分四類，第一類，從一班學(xué)生中選1人，有7種選法；第二類，從二班學(xué)生中選1人，有8種選法；第三類，從三班學(xué)生中選1人，有9種選法；第四類，從四班學(xué)生中選1人