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

1、一.分類加法計數(shù)原理與分步乘法計數(shù)原理1 .分類加法計數(shù)原理完成一件事情，有n類不同方案，在第1類方案中有m1種不同的方法，在第2類方案中有m2種不同的方法在第n類方案中有mn種不同的方法.那么完成這件事共有Nm1m2mn種不同的方法.說明：分類加法計數(shù)原理針對的是“分類”問題，完成一件事要分為若干類，各類的方法相互獨立，各類中的各種方法也相對獨立，用任何一類中的任何一種方法都可以單獨完成這件事2 .分步乘法計數(shù)原理完成一件事情，需要n個步驟，做第1步有mi種不同的方法，做第2步有m2種不同的方法做第n步有mn種不同的方法.那么完成這件事共有Nmim2mn種不同白方法.說明：分步計數(shù)原理針對的

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

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

4、共有45+45=90種不同取法.(2)分類標準一，固定小加數(shù).小加數(shù)為1時，大加數(shù)只有20這1種取法；小加數(shù)為2時，大加數(shù)有19或20兩種取法；小加數(shù)為3時，大加數(shù)為18,19或20共3種取法一小加數(shù)為10時，大加數(shù)為11,12，,20共10種取法；小加數(shù)為11時，大加數(shù)有9種取法小加數(shù)取19時，大加數(shù)有1種取法.由分類計數(shù)原理，得不同取法共有1+2+-+9+10+9+-+2+1=100種.,2,2,1,1 種.由分類計分類標準二：固定和的值.有和為21,22,39這幾類，依次有取法10,9,9,8,8,數(shù)原理得不同取法共有10+9+9+-+2+2+1+1=100種.例2.如圖，共有多少個不同

5、的三角形解：所有不同的三角形可分為三類”第一類：其中有兩條邊是原五邊形的邊，這樣的三角形共有5個第二類：其中有且只有一條邊是原五邊形的邊，這樣的三角形共有5X4=20個第三類：沒有一條邊是原五邊形的邊，即由五條對角線圍成的三角形，共有5+5=10個由分類計數(shù)原理得，不同的三角形共有5+20+10=35個.二.排列與組合1 .排列：從n個不同元素中取出m(mn)個元素，按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列。2 .排列數(shù)：從n個不同元素中取出m（mn）個元素的所有不同排列的個數(shù)叫做從n個不同元素中取出m個元素的排列數(shù)，用符號Am表示。3.排列數(shù)公式：Amn(n 1)(

6、n 2)L (n m 1)(n m)!(n,m N，且m n)4 .組合：從n個不同元素中取出m（mn）個元素合成一組，叫做從n個不同元素中取出m個元素的一個組合。5 .組合數(shù)：從n個不同元素中取出m（mn）個元素的所有不同組合的個數(shù)，叫做從n個不同元素中取出m個元素組合數(shù)。Amn!一6 .組合數(shù)公式：Cn-:,（n,mN，且mn）m!m!（nm）!7 .解排列、組合題的基本策略與方法（1）合理分類與準確分步（2）有序排列，無序組合（3）排列、組合混合問題先選后排（4）特殊元素、特殊位置優(yōu)先（5）正難則反，等價轉(zhuǎn)化（6）相鄰問題捆綁處理（7）不相鄰問題插空處理策略（8）定序問題除法處理（9）分

7、排問題直排處理（10）構(gòu)造模型的策略【基礎題型選講】例1.用數(shù)字0、1、2、3、4、5組成無重復數(shù)字。（1）可以組成多少個六位數(shù)（2）可以組成多少個四位奇數(shù)（3）可以組成至少有一個偶數(shù)數(shù)字的三位數(shù)多少個（4）可以組成多少個能被3整除的四位數(shù)（5）可以組成多少個大于324105的六位數(shù)解：（1）從特殊元素0入手，0不能排在十萬位，。有A；種排法，剩下的5個數(shù)字可排在5個數(shù)位下，有A5種，故可組成A5A；600個六位數(shù)。從特殊位置十萬位入手，有種排法，剩下的五個位置有A；種，故可組成AA；600個六位數(shù)。六個數(shù)字可組成A；個“六位數(shù)”（其中包括0在十萬位的情形），而0在最高位上的“六位數(shù)”應扣除，

8、565有A5個，故共有A6A5600個六位數(shù)。（2）從特殊位置入手，個位上有A；種排法，首位上有R種排法，中間兩位上有A42種排法，故共有A3A4A2144個;從特殊元素入手，可分為兩類，含數(shù)字0的有a3A28個，不含有數(shù)字0的有a3a：個，故共有四位奇數(shù)A3A4A2144個。32米用去雜法，個位是奇數(shù)的數(shù)共有3A5個，其中不合條件的（0在首位）有3A4個，故符合條件的四位奇數(shù)共有3A；3A42144個。(3)分類：如果有0,則0可排在個位或十位有2種，其余5個數(shù)字可排在二個數(shù)位上有A；種，所以有2A40個三位數(shù)；如果無0,則2、4中可選出1個有2種，再從其余3個奇數(shù)中選出2個有C；種，然后將

9、3個數(shù)字全排列有N種，所以有2C2A336個二位數(shù)，如果無0,則2、4中可選出2個有1種,再從其余3個奇數(shù)中選出1個有3種，然后將3個數(shù)字全排列有A3種，所以有13A318個三位數(shù)，共有40361894個。三位數(shù)共有A11A；個，但其中三個數(shù)字都不是偶數(shù)即均為奇數(shù)的有A3個，故至少含有一個偶數(shù)的三位數(shù)有A；A；A394個。注：(3)中解法一(選化法)顯然比第二種解法(去雜法)煩。(4)一個整數(shù)能被3整除的充要條件是它的各位數(shù)字之和是3的倍數(shù)，符合條件的有5組數(shù)：0、1、2、3;0、2、3、4;0、3、4、5;0、1、3、5;1、2、4、5;前4組每組組成的四位數(shù)各有A3A3個，后一組組成的四位

10、數(shù)有A：個，故可組成能被3整除的四位數(shù)有4A3A3A496個。(5)采用去雜法，六位數(shù)共有5A5個，不大于324105的數(shù)列如3240XX有2個；321XXX與3203 -XXX 有 2A3 個； 31XXXX 與 30XXXX 有55有2A；個，所以滿足條件的六位數(shù)共有2A； 2采用選化法，符合條件的是形如 5XXXXX和4a一一，2A4 個； 324105 1 個； 2x x x x x 與 1xxxxx2 A3 2A4 1 2A；297 個。4XXXXX的數(shù)有2個個；35XXXX和 34XXXX的數(shù)有2A44個；325XXX的數(shù)有A；個；3245XX的數(shù)有A2個，還有1個324150,故

11、符合條件的六位數(shù)共有2A552A442A32A21297個。例2.七個人排成一排，按下列要求的有多少種排法(1)其中甲不站排頭；(2)其中甲不站排頭，乙不站排尾；(3)其中甲、乙兩人必須相鄰；(4)其中甲、乙兩人必須不相鄰；(5)甲乙相鄰，丙丁不相鄰；(6)甲乙不相鄰，丙丁不相鄰；(7)其中甲、乙中間有且只有1人；(8)其中甲必須排在乙的右邊；(9)前排3人，后排4人；(10)甲站前排，乙站后排變式：(1)要排一個有5個獨唱節(jié)目和3個舞蹈節(jié)目的節(jié)目單，如果舞蹈節(jié)目不排在開頭，并且任意兩個舞蹈節(jié)目不排在一起，則不同的排法種數(shù)有()(2)從6名運動員中選出4個參加4100m接力賽，如果甲不跑第一棒

12、，乙不跑第四棒，共有種不同的參賽方法。(3)現(xiàn)安排甲、乙、丙、丁、戌5名同學參加上海世博會志愿者服務活動，每人從事翻譯、導游、禮儀、司機四項工作之一，每項工作至少有一人參加。甲、乙不會開車但能從事其他三項工作，丙丁戌都能勝任四項工作，則不同安排方案的種數(shù)是()A.152(4)某單位安排7位員工在10月1日至7日值班，每天1人，每人值班1天，若7位員工中的甲、乙排在相鄰兩天，丙不排在10月1日，丁不排在10月7日，則不同的安排方案共有A.504種B.960種C.1008種D.1108種【答案】C解析：分兩類：甲乙排1、2號或6、7號共有種方法甲乙排中間，丙排7號或不排7號，共有種方法故共有100

13、8種不同的排法(5)用1,2,3,4,5,6組成六位數(shù)(沒有重復數(shù)字)，要求任何相鄰兩個數(shù)字的奇偶性不同，且1和2相鄰，這樣的六位數(shù)的個數(shù)是(用數(shù)字作答)。(6)用1,2,3,4,5,6,7,8組成沒有重復數(shù)字的八位數(shù)，要求1與2相鄰，3與4相鄰，5與6相鄰，而7與8不相鄰，這樣的八位數(shù)共有個(用數(shù)字作答)例3.從6男4女中，選出5人，按下列要求的有多少種不同的選法(1)甲必須當選；(2)乙不能當選；(3)甲當選一不當選；(4)至少1名女生至少2名男生，變式：(1)某班級有20名男生和18名女生，從這38名學生中任選4名參加一個"Party”。(1)其中恰有2名女生的選法有多少種(2

14、)其中至少有2名女生的選法有多少種解：(1)C1C2029070(2)分3類：4人中無女生：CM4人中恰有1女生C30C;；4人中恰有2女生C20C28,故共有C4054435種C3C1C2C2C20C18C20C18(2)某餐廳供應客飯，每位顧客可以在餐廳提供的菜肴中任選2葷2素共4種不同的品種，現(xiàn)在餐廳準備了5種不同的葷菜，若要彳證每位顧客有200種以上的不同選擇，則餐廳至少還需準備不同的素菜品種種.(3) 5個身高不等的學生站成一排合影，從中間到兩邊一個比一個矮的排法有()種,在一個長方體中，由 )A.6B.8C.10(4)如果一條直線與一個平面平行，那么稱此直線與平面構(gòu)成一個“平行線面

15、組”兩個頂點確定的直線與含有四個頂點的平面構(gòu)成的“平行線面組”的個數(shù)是(A.60C.36例4.從0到9這10個數(shù)字中選出(1)可組成多少個沒有重復數(shù)字的 變式：(1) 25人排成5X 5方陣，從中選出 同的任職方法有多少種(3600)(2)某地奧運火炬接力傳遞路線共分3個偶數(shù)和2個奇數(shù)5位數(shù)(2)可組成多少個沒有重復數(shù)字的被5整除的5位數(shù)3人分別擔任三種不同的職務，要求這3人既不同行也不同列，則不6段，傳遞活動分別由 6名火炬手完成.如果第一棒火炬手只能從甲、乙、丙三人中產(chǎn)生，最后一棒火炬手只能從甲、乙兩人中產(chǎn)生，則不同的傳遞方案共有種.(用數(shù)字作答)(3)四棱錐的8條棱代表8種不同的化工產(chǎn)品

16、，有公共點的兩條棱代表的化工產(chǎn)品放在同一倉庫是危險的，沒有公共頂點的兩條棱代表的化工產(chǎn)品放在同一倉庫是安全的，現(xiàn)打算用編號為、的4個倉庫存放這8種化工產(chǎn)品，那么安全存放的不同方法種數(shù)為()(4)以集合Ua,b,c,d的子集中選出4個不同的子集，需同時滿足以下兩個條件：(1)a,b都要選出;(2)對選出的任意兩個子集A和B,必有AB或BA,那么共有種不同的選法。例5.(從集合角度)10人組成的籃球隊中，有5人只適于打鋒，3人只適于打衛(wèi)，2人打鋒打衛(wèi)即可，現(xiàn)選5人參加比賽3鋒2衛(wèi)，問共有多少種不同的選擇例6.(1)以正方體的頂點為頂點的四面體共有個。(2)四面體的頂點和各棱中點共10點，在其中取4

17、個不共面的點，不同的取法共有種(141)(3)變式：四面體的一個頂點為A,從其他頂點與棱的中點中取3個點，使它們和點A在同一個平面上，則不同的取法有種(33)變式：(1)如圖2-1,共有個不同的矩形如圖2-2,共有個不同的直角三角形如圖2-3,從A到B有種不同的走法(2)在正方體的8個頂點中，能構(gòu)成一個直角三角形的3個頂點的直角三角形的個數(shù)為.*(3)一個圓周上共有10個不同的點，試問：這10個點可構(gòu)成弦；這些弦可以構(gòu)成個不同的交點；這些弦又可以構(gòu)成個不同的直角三角形個不同的銳角角三角形個不同的鈍角角三角形(4)在xOy平面上，頂點坐標(x,y)滿足1x4,1y4,且x,y取整數(shù)的三角形有多少

18、個例3.75600有多少個正約數(shù)有多少個奇約數(shù)解:75600的約數(shù)就是能整除75600的整數(shù)，所以本題就是分別求能整除75600的整數(shù)和奇約數(shù)的個數(shù).由于75600=24X33X52X7。(1)75600的每個約數(shù)都可以寫成2l3j5k7l的形式，其中0i4,0j3,0k2,0l1。于是，要確定75600的一個約數(shù)，可分四步完成，即i,j,k,l分別在各自的范圍內(nèi)任取一個值，這樣i有5種取法，j有4種取法，k有3種取法，l有2種取法，根據(jù)分步計數(shù)原理得約數(shù)的個數(shù)為5X4X3X2=120個.(2)奇約數(shù)中步不含有2的因數(shù)，因此75600的每個奇約數(shù)都可以寫成3j5k7l的形式，同上奇約數(shù)的個數(shù)為

19、4X3X2=24個.例4.(排數(shù)問題)用0,1,2,3,4,5這六個數(shù)字，(1) 可以組成多少個數(shù)字不重復的三位數(shù)(2) 可以組成多少個數(shù)字允許重復的三位數(shù)(3) 可以組成多少個數(shù)字不允許重復的三位數(shù)的奇數(shù)(4) 可以組成多少個數(shù)字不重復的小于1000的自然數(shù)(5) 可以組成多少個大于3000,小于5421的數(shù)字不重復的四位數(shù)解(1)分三步：先選百位數(shù)字.由于0不能作百位數(shù)，因此有5種選法；十位數(shù)字有5種選法;個位數(shù)字有4種選法.由乘法原理知所求不同三位數(shù)共有5X5X4=100個.（2）分三步：（1）百位數(shù)字有5種選法；（ii）十位數(shù)字有6位選法；（iii）個位數(shù)字有6種選法。所求三位數(shù)共有5X6X6=180個.（1） 分三步：先選個位數(shù)字，有3種選法；再選百位數(shù)字，有4種選法；選十位數(shù)字也是4種選法，所求三位奇數(shù)共有3X4X4=48個.（2） 分三類：一位數(shù)，共有6個；兩位數(shù)，共有5X5=25個；三位數(shù)共有5X5X4=100個.因此，比1000小的自然數(shù)共有6+25+100=131個.（3） 分4類：千位數(shù)字為3,4之一時，共有2X5X4X3=120個；千位數(shù)字為5,百位數(shù)字