計(jì)數(shù)問題競(jìng)賽講義一

1、計(jì)數(shù)問題競(jìng)賽講義一一分類加法計(jì)數(shù)原理與分步乘法計(jì)數(shù)原理1.分類加法計(jì)數(shù)原理 完成一件事情，有類不同方案，在第1類方案中有種不同的方法，在第2類方案中有種不同的方法在第類方案中有種不同的方法.那么完成這件事共有種不同的方法.說明：分類加法計(jì)數(shù)原理針對(duì)的是“分類”問題，完成一件事要分為若干類，各類的方法相互獨(dú)立，各類中的各種方法也相對(duì)獨(dú)立，用任何一類中的任何一種方法都可以單獨(dú)完成這件事.2.分步乘法計(jì)數(shù)原理 完成一件事情，需要個(gè)步驟，做第1步有種不同的方法，做第2步有種不同的方法做第步有種不同的方法.那么完成這件事共有種不同的方法.說明：分步計(jì)數(shù)原理針對(duì)的是“分步”問題，完成一件事要分為若干步，各

2、個(gè)步驟相互依存，完成任何其中的一步都不能完成該件事，只有當(dāng)各個(gè)步驟都完成后，才算完成這件事.3.理解分類加法計(jì)數(shù)原理與分步乘法計(jì)數(shù)原理異同點(diǎn)相同點(diǎn)：都是完成一件事的不同方法種數(shù)的問題不同點(diǎn)：分類加法計(jì)數(shù)原理針對(duì)的是“分類”問題，完成一件事要分為若干類，各類的方法相互獨(dú)立，各類中的各種方法也相對(duì)獨(dú)立，用任何一類中的任何一種方法都可以單獨(dú)完成這件事，是獨(dú)立完成；而分步乘法計(jì)數(shù)原理針對(duì)的是“分步”問題，完成一件事要分為若干步，各個(gè)步驟相互依存，完成任何其中的一步都不能完成該件事，只有當(dāng)各個(gè)步驟都完成后，才算完成這件事，是合作完成.4.運(yùn)用分類加法計(jì)數(shù)原理與分步乘法計(jì)數(shù)原理的注意點(diǎn)：首先要確定“完成一

3、件什么事”，然后確定怎樣去完成？（即需要“分類”還是“分步”）分類加法計(jì)數(shù)原理：首先確定分類標(biāo)準(zhǔn)，其次要保證分類時(shí)做到“不重不漏”。分步乘法計(jì)數(shù)原理：首先確定分步標(biāo)準(zhǔn)，其次要保證“步驟完整”，即必須并且只需連續(xù)完成這個(gè)步驟，這件事才算完成.【例題選講】例1 .在120共20個(gè)整數(shù)中取兩個(gè)數(shù)相加,使其和為偶數(shù)的不同取法共有多少種? 使其和大于20的不同取法又共有多少種?解:（1）取與取是同一種取法.分類標(biāo)準(zhǔn)為兩加數(shù)的奇偶性,第一類,偶偶相加,由分步計(jì)數(shù)原理得(10×9)/2=45種取法,第二類,奇奇相加,也有(10×9)/2=45種取法.根據(jù)分類計(jì)數(shù)原理共有45+45=90種

4、不同取法.（2）分類標(biāo)準(zhǔn)一,固定小加數(shù).小加數(shù)為1時(shí),大加數(shù)只有20這1種取法;小加數(shù)為2時(shí),大加數(shù)有19或20兩種取法;小加數(shù)為3時(shí),大加數(shù)為18,19或20共3種取法小加數(shù)為10時(shí),大加數(shù)為11,12,20共10種取法;小加數(shù)為11時(shí),大加數(shù)有9種取法小加數(shù)取19時(shí),大加數(shù)有1種取法.由分類計(jì)數(shù)原理,得不同取法共有1+2+9+10+9+2+1=100種.分類標(biāo)準(zhǔn)二:固定和的值.有和為21,22,39這幾類,依次有取法10,9,9,8,8, ,2,2,1,1種.由分類計(jì)數(shù)原理得不同取法共有10+9+9+2+2+1+1=100種.例2. 如圖,共有多少個(gè)不同的三角形?解:所有不同的三角形可分為

5、三類”第一類:其中有兩條邊是原五邊形的邊,這樣的三角形共有5個(gè)第二類:其中有且只有一條邊是原五邊形的邊,這樣的三角形共有5×4=20個(gè)第三類:沒有一條邊是原五邊形的邊,即由五條對(duì)角線圍成的三角形,共有5+5=10個(gè)由分類計(jì)數(shù)原理得,不同的三角形共有5+20+10=35個(gè).二排列與組合1.排列：從個(gè)不同元素中取出個(gè)元素，按照一定的順序排成一列，叫做從個(gè)不同元素中取出個(gè)元素的一個(gè)排列。2.排列數(shù)：從個(gè)不同元素中取出個(gè)元素的所有不同排列的個(gè)數(shù)叫做從個(gè)不同元素中取出個(gè)元素的排列數(shù)，用符號(hào)表示。3. 排列數(shù)公式：，4.組合：從個(gè)不同元素中取出個(gè)元素合成一組，叫做從個(gè)不同元素中取出個(gè)元素的一個(gè)組

6、合。5.組合數(shù)：從個(gè)不同元素中取出個(gè)元素的所有不同組合的個(gè)數(shù)，叫做從個(gè)不同元素中取出個(gè)元素組合數(shù)。6. 組合數(shù)公式：，7解排列、組合題的基本策略與方法（1）合理分類與準(zhǔn)確分步 （2）有序排列，無序組合 （3）排列、組合混合問題先選后排 （4）特殊元素、特殊位置優(yōu)先 （5）正難則反，等價(jià)轉(zhuǎn)化 （6）相鄰問題捆綁處理（7）不相鄰問題插空處理策略（8）定序問題除法處理（9）分排問題直排處理（10）構(gòu)造模型的策略【基礎(chǔ)題型選講】例1用數(shù)字0、1、2、3、4、5組成無重復(fù)數(shù)字。（1）可以組成多少個(gè)六位數(shù)？ （2）可以組成多少個(gè)四位奇數(shù)？（3）可以組成至少有一個(gè)偶數(shù)數(shù)字的三位數(shù)多少個(gè)？（4）可以組成多少個(gè)

7、能被3整除的四位數(shù)？ （5）可以組成多少個(gè)大于324105的六位數(shù)？解：（1）從特殊元素0入手，0不能排在十萬位，0有種排法，剩下的5個(gè)數(shù)字可排在5個(gè)數(shù)位下，有種，故可組成個(gè)六位數(shù)。從特殊位置十萬位入手，有種排法，剩下的五個(gè)位置有種，故可組成個(gè)六位數(shù)。六個(gè)數(shù)字可組成個(gè)“六位數(shù)”（其中包括0在十萬位的情形），而0在最高位上的“六位數(shù)”應(yīng)扣除，有個(gè)，故共有個(gè)六位數(shù)。（2）從特殊位置入手，個(gè)位上有種排法，首位上有種排法，中間兩位上有種排法，故共有個(gè)；從特殊元素入手，可分為兩類，含數(shù)字0的有個(gè)，不含有數(shù)字0的有個(gè)，故共有四位奇數(shù)個(gè)。采用去雜法， 個(gè)位是奇數(shù)的數(shù)共有個(gè)，其中不合條件的（0在首位）有個(gè)，故

8、符合條件的四位奇數(shù)共有個(gè)。（3）分類：如果有0，則0可排在個(gè)位或十位有2種，其余5個(gè)數(shù)字可排在二個(gè)數(shù)位上有種，所以有個(gè)三位數(shù)；如果無0，則2、4中可選出1個(gè)有2種，再?gòu)钠溆?個(gè)奇數(shù)中選出2個(gè)有種，然后將3個(gè)數(shù)字全排列有種，所以有個(gè)二位數(shù)，如果無0，則2、4中可選出2個(gè)有1種，再?gòu)钠溆?個(gè)奇數(shù)中選出1個(gè)有3種，然后將3個(gè)數(shù)字全排列有種，所以有個(gè)三位數(shù)，共有個(gè)。三位數(shù)共有個(gè)，但其中三個(gè)數(shù)字都不是偶數(shù)即均為奇數(shù)的有個(gè)，故至少含有一個(gè)偶數(shù)的三位數(shù)有個(gè)。注：（3）中解法一（選化法）顯然比第二種解法（去雜法）煩。（4）一個(gè)整數(shù)能被3整除的充要條件是它的各位數(shù)字之和是3的倍數(shù)，符合條件的有5組數(shù)：0、1、2

9、、3；0、2、3、4；0、3、4、5；0、1、3、5；1、2、4、5；前4組每組組成的四位數(shù)各有個(gè)，后一組組成的四位數(shù)有個(gè)，故可組成能被3整除的四位數(shù)有個(gè)。（5）采用去雜法，六位數(shù)共有個(gè)，不大于324105的數(shù)列如3240××有2個(gè)；321×××與320×××有個(gè)；31××××與30××××有個(gè)；324105 1個(gè)；2×××××與1××××

10、5;有個(gè)，所以滿足條件的六位數(shù)共有個(gè)。采用選化法，符合條件的是形如5×××××和4×××××的數(shù)有個(gè)；35××××和34××××的數(shù)有個(gè)；325×××的數(shù)有個(gè)；3245××的數(shù)有個(gè)，還有1個(gè)324150，故符合條件的六位數(shù)共有個(gè)。例2七個(gè)人排成一排，按下列要求的有多少種排法？（1）其中甲不站排頭； （2）其中甲不站排頭，乙不站排尾；（3）其中甲、乙兩人必須相鄰； （4

11、）其中甲、乙兩人必須不相鄰；（5）甲乙相鄰，丙丁不相鄰； （6）甲乙不相鄰，丙丁不相鄰；（7）其中甲、乙中間有且只有1人； （8）其中甲必須排在乙的右邊；（9）前排3人，后排4人； （10）甲站前排，乙站后排變式：（1）要排一個(gè)有5個(gè)獨(dú)唱節(jié)目和3個(gè)舞蹈節(jié)目的節(jié)目單，如果舞蹈節(jié)目不排在開頭，并且任意兩個(gè)舞蹈節(jié)目不排在一起，則不同的排法種數(shù)有（ ）A B C D（2）從6名運(yùn)動(dòng)員中選出4個(gè)參加接力賽，如果甲不跑第一棒，乙不跑第四棒，共有 種不同的參賽方法。（3）現(xiàn)安排甲、乙、丙、丁、戌5名同學(xué)參加上海世博會(huì)志愿者服務(wù)活動(dòng)，每人從事翻譯、導(dǎo)游、禮儀、司機(jī)四項(xiàng)工作之一，每項(xiàng)工作至少有一人參加。甲、乙不

12、會(huì)開車但能從事其他三項(xiàng)工作，丙丁戌都能勝任四項(xiàng)工作，則不同安排方案的種數(shù)是（ ）A152 B.126 C.90 D.54（4）某單位安排7位員工在10月1日至7日值班，每天1人，每人值班1天，若7位員工中的甲、乙排在相鄰兩天，丙不排在10月1日，丁不排在10月7日，則不同的安排方案共有A. 504種 B. 960種 C. 1008種 D. 1108種 【答案】C解析：分兩類：甲乙排1、2號(hào)或6、7號(hào) 共有種方法甲乙排中間,丙排7號(hào)或不排7號(hào)，共有種方法故共有1008種不同的排法（5） 用1，2，3，4，5，6組成六位數(shù)（沒有重復(fù)數(shù)字），要求任何相鄰兩個(gè)數(shù)字的奇偶性不同，且1和2相鄰，這樣的六位

13、數(shù)的個(gè)數(shù)是_（用數(shù)字作答)。（6） 用1，2，3，4，5，6,7,8組成沒有重復(fù)數(shù)字的八位數(shù)，要求1與2相鄰， 3與4相鄰，5與6相鄰，而7與8不相鄰，這樣的八位數(shù)共有 個(gè)（用數(shù)字作答）例3從6男4女中，選出5人，按下列要求的有多少種不同的選法？（1）甲必須當(dāng)選； （2）乙不能當(dāng)選；（3）甲當(dāng)選一不當(dāng)選；（4）至少1名女生至少2名男生，變式：（1）某班級(jí)有20名男生和18名女生，從這38名學(xué)生中任選4名參加一個(gè)“Party”。（1）其中恰有2名女生的選法有多少種？ （2）其中至少有2名女生的選法有多少種？解：（1）（2）分3類：4人中無女生：；4人中恰有1女生；4人中恰有2女生，故共有種（2）

14、某餐廳供應(yīng)客飯，每位顧客可以在餐廳提供的菜肴中任選2葷2素共4種不同的品種，現(xiàn)在餐廳準(zhǔn)備了5種不同的葷菜，若要保證每位顧客有200種以上的不同選擇，則餐廳至少還需準(zhǔn)備不同的素菜品種 種（3）5個(gè)身高不等的學(xué)生站成一排合影，從中間到兩邊一個(gè)比一個(gè)矮的排法有（ ）種 A. 6 B. 8 C. 10 D.12（4）如果一條直線與一個(gè)平面平行，那么稱此直線與平面構(gòu)成一個(gè)“平行線面組”，在一個(gè)長(zhǎng)方體中，由兩個(gè)頂點(diǎn)確定的直線與含有四個(gè)頂點(diǎn)的平面構(gòu)成的“平行線面組”的個(gè)數(shù)是（ ） A. 60 B.48 C. 36 D.24例4從0 到9這10個(gè)數(shù)字中選出3個(gè)偶數(shù)和2個(gè)奇數(shù)（1）可組成多少個(gè)沒有重復(fù)數(shù)字的5位

15、數(shù)？（2）可組成多少個(gè)沒有重復(fù)數(shù)字的被5整除的5位數(shù)？變式：（1）25人排成5×5方陣，從中選出3人分別擔(dān)任三種不同的職務(wù)，要求這3人既不同行也不同列，則不同的任職方法有多少種？（3600）（2）某地奧運(yùn)火炬接力傳遞路線共分6段，傳遞活動(dòng)分別由6名火炬手完成如果第一棒火炬手只能從甲、乙、丙三人中產(chǎn)生，最后一棒火炬手只能從甲、乙兩人中產(chǎn)生，則不同的傳遞方案共有 種（用數(shù)字作答）（3）四棱錐的8條棱代表8種不同的化工產(chǎn)品,有公共點(diǎn)的兩條棱代表的化工產(chǎn)品放在同一倉(cāng)庫(kù)是危險(xiǎn)的,沒有公共頂點(diǎn)的兩條棱代表的化工產(chǎn)品放在同一倉(cāng)庫(kù)是安全的,現(xiàn)打算用編號(hào)為、的4個(gè)倉(cāng)庫(kù)存放這8種化工產(chǎn)品,那么安全存放的

16、不同方法種數(shù)為( ) A.96 B.48 C.24 D.0（4）以集合的子集中選出4個(gè)不同的子集，需同時(shí)滿足以下兩個(gè)條件：（1）都要選出；（2）對(duì)選出的任意兩個(gè)子集和，必有或，那么共有 種不同的選法。例5.（從集合角度） 10人組成的籃球隊(duì)中，有5人只適于打鋒，3人只適于打衛(wèi)，2人打鋒打衛(wèi)即可，現(xiàn)選5人參加比賽3鋒2衛(wèi)，問共有多少種不同的選擇？ 例6.（1） 以正方體的頂點(diǎn)為頂點(diǎn)的四面體共有 個(gè)。（2）四面體的頂點(diǎn)和各棱中點(diǎn)共10點(diǎn)，在其中取4個(gè)不共面的點(diǎn)，不同的取法共有 種（141）（3）變式：四面體的一個(gè)頂點(diǎn)為，從其他頂點(diǎn)與棱的中點(diǎn)中取3個(gè)點(diǎn)，使它們和點(diǎn)在同一個(gè)平面上，則不同的取法有 種（

17、33）例變式：（1）如圖2-1,共有 個(gè)不同的矩形? 如圖2-2,共有 個(gè)不同的直角三角形? 如圖2-3,從A到B有 種不同的走法？（2）在正方體的8個(gè)頂點(diǎn)中，能構(gòu)成一個(gè)直角三角形的3個(gè)頂點(diǎn)的直角三角形的個(gè)數(shù)為 .*（3）一個(gè)圓周上共有10個(gè)不同的點(diǎn)，試問：這10個(gè)點(diǎn)可構(gòu)成 弦；這些弦可以構(gòu)成 個(gè)不同的交點(diǎn)；這些弦又可以構(gòu)成 個(gè)不同的直角三角形？ 個(gè)不同的銳角角三角形？ 個(gè)不同的鈍角角三角形？（4）在xOy平面上，頂點(diǎn)坐標(biāo)（x,y）滿足且x,y取整數(shù)的三角形有多少個(gè)？ 例3 .75600有多少個(gè)正約數(shù)?有多少個(gè)奇約數(shù)?解:75600的約數(shù)就是能整除75600的整數(shù),所以本題就是分別求能整除75

18、600的整數(shù)和奇約數(shù)的個(gè)數(shù). 由于 75600=24×33×52×7。(1) 75600的每個(gè)約數(shù)都可以寫成的形式,其中,。于是,要確定75600的一個(gè)約數(shù),可分四步完成,即分別在各自的范圍內(nèi)任取一個(gè)值,這樣有5種取法,有4種取法,有3種取法,有2種取法,根據(jù)分步計(jì)數(shù)原理得約數(shù)的個(gè)數(shù)為5×4×3×2=120個(gè).(2)奇約數(shù)中步不含有2的因數(shù),因此75600的每個(gè)奇約數(shù)都可以寫成的形式,同上奇約數(shù)的個(gè)數(shù)為4×3×2=24個(gè).例4.（排數(shù)問題）用0，1，2，3，4，5這六個(gè)數(shù)字，（1） 可以組成多少個(gè)數(shù)字不重復(fù)的三位數(shù)

19、？（2） 可以組成多少個(gè)數(shù)字允許重復(fù)的三位數(shù)？（3） 可以組成多少個(gè)數(shù)字不允許重復(fù)的三位數(shù)的奇數(shù)？（4） 可以組成多少個(gè)數(shù)字不重復(fù)的小于1000的自然數(shù)？（5） 可以組成多少個(gè)大于3000，小于5421的數(shù)字不重復(fù)的四位數(shù)？解（1）分三步：先選百位數(shù)字由于0不能作百位數(shù)，因此有5種選法；十位數(shù)字有5種選法； 個(gè)位數(shù)字有4種選法由乘法原理知所求不同三位數(shù)共有5×5×4=100個(gè)（2）分三步：(1)百位數(shù)字有5種選法；(ii)十位數(shù)字有6位選法；(iii)個(gè)位數(shù)字有6種選法。 所求三位數(shù)共有5×6×6=180個(gè)（1） 分三步：先選個(gè)位數(shù)字，有3種選法；再選百位數(shù)字，有4種選法；選十位數(shù)字也是4種選法，所求三位奇數(shù)共有3×4×4=48個(gè)（2） 分三類：一位數(shù)，共有6個(gè)；兩位數(shù)，共有5×5=25個(gè)；三位數(shù)共有5×5×4=100個(gè)因此，比1000小的自然數(shù)共有6+25+100=131個(gè)（3） 分4類：千位數(shù)字為3，4之一時(shí)，共有2×