1、兩個計數原理與排列組合知識點及例題兩個計數原理內容1、分類計數原理：完成一件事，有n類辦法，在第1類辦法中有m種不同的方法，在第2類辦法中有m2種不同的方法在第n類辦法中有m種不同的方法，那么完成這件事共有N=m+m2 + +mn種不同的方法.2、分步計數原理：完成一件事，需要分n個步驟，做第1步驟有m種不同的方法，做第2步驟有m2種不同的方法做第n步驟有mn種不同的方法，那么完成這件事共有N=mx m xx m種不同的方法.例題分析例1某學校食堂備有5種素菜、3種葷菜、2種湯。現要配成一葷一素一湯的套餐。問可以配制出多少種不同的品種？分析：1、完成的這件事是什么？2 、如何完成這件事？（配一

2、個葷菜、配一個素菜、配一湯）3 、它們屬于分類還是分步？（是否獨立完成）4 、運用哪個計數原理？5 、進行計算(2)從書架上任取一本數學書和一本語文書，有多少種不冋的取法?(1)分析:1、完成的這件事是什么？2、如何完成這件事？3、它們屬于分類還是分步？（是否獨立完成）4、運用哪個計數原理？5、進行計算。解:屬于分類：第一類從上層取一本書 有5種選擇第二類從下層取一本書有4種選擇共有N=5+4=9 （種）(2)分析:1、完成的這件事是什么？2、如何完成這件事？3、它們屬于分類還是分步？（是否獨立完成）4、運用哪個計數原理？5、進行計算解：屬于分步：第一步從上層取一本書有5種選擇第二步 從下層取

3、一本書有4種選擇共有 N=5X 4=20 （種）例3、 有1、2、3、4、5五個數字（1）可以組成多少個不同的三位數？（2）可以組成多少個無重復數字的三位數？（3）可以組成多少個無重復數字的偶數的三位數？（1）分析：1、完成的這件事是什么？2 、如何完成這件事？（配百位數、配十位數、配個位數）3 、它們屬于分類還是分步？（是否獨立完成）4 、運用哪個計數原理？5 、進行計算略解：N=5X 5X 5=125 （個）解：屬于分步：第一步配一個葷菜有3種選擇第二步配一個素菜有5種選擇第三步配一個湯有2種選擇共有 N=3X 5 X 2=30 (種)【例題解析】例2有一個書架共有2層，上層放有5本不同的

4、數學書，下層放有 4本不同的語文書。（1）從書架上任取一本書，有多少種不同的取法？1、某人有4條不同顏色的領帶和 6件不同款式的襯衣，問可以有多少種不同的搭配方法?學習必備熨迎下載取出m個元素的一個組合*7.組合數的概念：從n個不同元素中取出m m乞n個元素的所有組合的個數，叫做從n 個不同元素中取出m個元素的組合數.用符號cnm表示.2、有一個班級共有 46名學生，其中男生有 21名.(1) 現要選派一名學生代表班級參加學校的學代會，有多少種不同的選派方法？(2) 若要選派男、女各一名學生代表班級參加學校的學代會，有多少種不同的選派方法?8. 組合數公式：cj Amn-1)(n-2)(nm

5、1)或cm衛(n,m N ,且m")“Am!m!(n- m)!9. 組合數的性質1: cm = C；-m .規定：Cn =1 ；10. 組合數的性質 2: cn；二 Cnm+cn * Cn0+cn1+- +Cn=2na4種選法，然后其他 5人選，有 A種選法,3、有0、1、2、3、4、5六個數字.(1) 可以組成多少個不同的三位數？(2) 可以組成多少個無重復數字的三位數？(3) 可以組成多少個無重復數字的偶數的三位數？排列與組合1. 排列的概念：從n個不同元素中，任取m ( mn )個元素(這里的被取元素各不相同) 按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列

6、*2. 排列數的定義：從n個不同元素中，任取m ( mn)個元素的所有排列的個數叫做從n個元素中取出m元素的排列數，用符號A；表示3. 排列數公式：A?二 n(n -1)(n - 2川1(n- m 1) ( m, n N ,m n )4. 階乘：n!表示正整數1到n的連乘積，叫做n的階乘+規定0! =1.5. 排列數的另一個計算公式：Am= 匚 ”(n -m)!6. 組合概念：從n個不同元素中取出m mn個元素并成一組，叫做從n個不同元素中題型講解例1分別求出符合下列要求的不同排法的種數(1) 6名學生排3排，前排1人，中排2人，后排3人；(2) 6名學生排成一排，甲不在排頭也不在排尾；(3)

7、 從6名運動員中選出4人參加4 X 100米接力賽，甲不跑第一棒，乙不跑第四棒；(4) 6人排成一排，甲、乙必須相鄰；(5) 6人排成一排，甲、乙不相鄰；(6) 6人排成一排，限定甲要排在乙的左邊，乙要排在丙的左邊(甲、乙、丙可以不相鄰)解：(1)分排坐法與直排坐法一一對應，故排法種數為A；二720(2) 甲不能排頭尾，讓受特殊限制的甲先選位置，有故排法種數為 A4A? = 480(3) 有兩棒受限制，以第一棒的人選來分類： 乙跑第一棒，其余棒次則不受限制，排法數為 乙不跑第一棒，則跑第一棒的人有A：種選法，第四棒除了乙和第一棒選定的人外，也有A：種選法，其余兩棒次不受限制，故有a：a4a；種

8、排法，由分類計數原理，共有 A； A：a4a2二252種排法（4） 將甲乙“捆綁”成“一個元”與其他4人一起作全排列共有 A；A? =240種排法（5） 甲乙不相鄰，第一步除甲乙外的其余4人先排好；第二步，甲、乙選擇已排好的4人的左、右及之間的空擋插位，共有 A4A （或用6人的排列數減去問題（2）后排列數為 A； -240=480）（6） 三人的順序定，實質是從 6個位置中選出三個位置，然后排按規定的順序放置這三人，其余3 人在3個位置上全排列，故有排法 cX -120種點評：排隊問題是一類典型的排列問題，常見的附加條件是定位與限位、相鄰與不相鄰例3求證：Amj mA； = Am證明：利用排

9、列數公式左 Cnm1 - cm 2c；mm亠1n-2n-m n-1 ! m n-1 !(n_ m)!八m=An另一種證法：（利用排列的定義理解）從 n個元素中取m個元素排列可以分成兩類:第一類不含某特殊元素a的排列有第二類含元素a的排列則先從 n-1個元素中取出 m-1個元素排列有 An1種，然后將a插入,共有m個空檔，故有m 人匕種，因此人二1 + m，AnL = A：利用組合數公式2n !(n +2)!m 1 ! n - m 1 !m 1Cn2二石例2 假設在100件產品中有3件是次品，從中任意抽取 5件，求下列抽取方法各多少種？（1） 沒有次品；（2）恰有兩件是次品；（3）至少有兩件是次

10、品解：（1）沒有次品的抽法就是從 97件正品中抽取5件的抽法，共有C；7 =64446024種（2） 恰有2件是次品的抽法就是從 97件正品中抽取3件，并從3件次品中抽2件的抽法，共有 c；7c； = 442320 種（3）至少有2件次品的抽法，按次品件數來分有二類：第一類，從97件正品中抽取3件，并從3件次品中抽取2件，有C；7C；種第二類從97件正品中抽取2件，并將3件次品全部抽取，有 c97C；種按分類計數原理有 C；7CC&C： =446976種點評：此題是只選“元”而不排“序”的典型的組合問題，附加的條件是從不同種類的元素中抽取，應當注意：如果第（3）題采用先從3件次品抽取2

11、件（以保證至少有 2件是次品），再從余 下的98件產品中任意抽取 3件的抽法，那么所得結果是 C；C；8 = 466288種，其結論是錯誤的，錯 在“重復”：假設3件次品是A B、C,第一步先抽 A B第二步再抽C和其余2件正品，與第一步先 抽A C （或 B、C），第二步再抽B （或 A）和其余2件正品是同一種抽法，但在算式C；C；8中算作3種不同抽法左=(m+1)!( n - m1)(m 1)( n m + 1)! m(n m)!nm n - m 1 mm1 2m1 n - m 1 1另法：利用公式叫 cncn1推得左二 c：1 c；： c： cm'二 cnvccn%1二右點評：證

12、明排列、組合恒等式通常利用排列數、組合數公式及組合數基本性質例4 已知f是集合Aa,b,c,d到集合B0,1,2?的映射（1）不同的映射f有多少個?（2）若要求fafbfcfd二4則不同的映射f有多少個?分析：（1）確定一個映射f，需要確定a, b, c, d的像（2）a, b, c, d的象元之和為4，則加數可能出現多種情況，即4有多種分析方案，各方案獨立且并列需要分類計算解：（1） A中每個元都可選 0,1,2三者之一為像，由分步計數原理，共有3 3 334個不同映射(2) 根據a, b, c, d對應的像為2的個數來分類，可分為三類：第一類：沒有元素的像為 2，其和又為4,必然其像均為1

13、,這樣的映射只有一個；第二類：一個元素的像是 2，其余三個元素的像必為0,1,1，這樣的映射有 C；P31 =12個;第三類：二個元素的像是2，另兩個元素的像必為0,這樣的映射有 C： =6個由分類計數原理共有 1+12+6=19 (個)點評：問題(1)可套用投信模型：n封不同的信投入 m個不同的信箱，有 mn種方法；問題(2)的關鍵結合映射概念恰當確定分類標準，做到不重、不漏故取4個點不共面的不同取法有 C：0 - 4C： 6 3 = 141 (種)點評：由點構成直線、平面、幾何體等圖形是一類典型的組合問題，附加的條件是點共線與不 共線，點共面與不共面，線共面與不共面等小結：m個不同的元素必

14、須相鄰，有P；種“捆綁”方法+m個不同元素互不相鄰，分別“插入”到n個“間隙”中的m個位置有種不同的“插入”方法+m個相同的元素互不相鄰，分別“插入”到n個“間隙”中的m個位置，有C,；種不同的“插入”方法.若干個不同的元素“等分”為m個組，要將選取出每一個組的組合數的乘積除以P,.【例題解析】例5四面體的頂點和各棱的中點共10個點A在同一平面上，不同的取法有多(1) 設一個頂點為 A,從其他9點中取3個點，使它們和點 少種？(2) 在這10點中取4個不共面的點，不同的取法有多少種？解：(1)如圖，含頂點 A的四面體的三個面上，除點 A外都有5個點，從中取出3點必與點A共面，共有3C；種取法含

15、頂點A的棱有三條，每條棱上有3個點，它們與所對棱的中點共面，共有3種取法根據分類計數原理和點 A共面三點取法共有 3C；，3=33種(2)取出的4點不共面比取出的 4點共面的情形要復雜，故采用間接法：先不加限制任取4點4(C10種取法)減去4點共面的取法取出的4點共面有三類：第一類：從四面體的同一個面上的6點取出4點共面，有4C；種取法第二類：每條棱上的 3個點與所對棱的中點共面，有 6種取法 第三類：從6條棱的中點取4個點共面，有3種取法根據分類計數原理4點共面取法共有4C： 6 69例1完成下列選擇題與填空題(1) 有三個不同的信箱，今有四封不同的信欲投其中，則不同的投法有種。A.81B.

16、64C.24D.4(2) 四名學生爭奪三項冠軍，獲得冠軍的可能的種數是()A.81B.64C.24D.4(3) 有四位學生參加三項不同的競賽， 每位學生必須參加一項競賽，則有不同的參賽方法有 ; 每項競賽只許有一位學生參加，則有不同的參賽方法有 ; 每位學生最多參加一項競賽，每項競賽只許有一位學生參加，則不同的參賽方法有。解析 (1)完成一件事是“分步”進行還是“分類”進行，是選用基本原理的關鍵。將“投四封信”這件事分四步完成，每投一封信作為一步，每步都有投入三個不同信箱的三種方法，因此：4N=3X 3 X 3 X 3=3=81,故答案選 A。本題也可以這樣分類完成， 四封信投入一個信箱中，有

17、C31種投法；四封信投入兩個信箱中，有C32 (C4 Ae2+C42 C22)種投法；四圭寸信投入三個信箱，有兩圭寸信在同一信箱中，有C? . As3種投法、，故共有 G1+G2 (G1 A22+C42Cb2) +C42 A33=81 (種)。故選 A。(2) 因學生可同時奪得 n項冠軍，故學生可重復排列，將4名學生看作4個“店”，3項冠軍看作“客”，每個“客”都可住進 4家“店”中的任意一家，即每個“客”有4種住宿法。由分步計數原理得：N=4X 4X 4=64。故答案選B。(3) 學生可以選擇項目，而競賽項目對學生無條件限制，所以類似(1)可得N=34=81 (種)； 競賽項目可以挑學生，而

18、學生無選擇項目的機會，每一項可以挑4種不同學生，共有N=4=64 (種)； 等價于從4個學生中挑選3個學生去參加三個項目的競賽，每人參加一項，故共有 C3 A3=24 (種)。注：本題有許多形式，一般地都可以看作下列命題：設集合 A=ai,a2,an,集合B=bi,b2,b m，貝U f: 2 B的不同映射是 m,f :A的不同映射是nmo若nw m,則f ： AtB的單值映射是：血。例2同室四人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀年卡，則四 張賀年卡不同的分配方式有（A.6種B.9種解法一由于共四人（用1, 2, 3, 題之后，可用窮舉法進行具體的填寫：C.11 種4D

19、.23 種代表甲、乙、丙、丁四人），這個數目不大，化為填數問解法二 記四人為甲、乙、丙、丁，則甲送出的卡片可以且只可以由其他三人之一收到，故有3種分配方式；以乙收到為例，其他人收到卡片的情況可分為兩類：第一類：甲收到乙送出的卡片，這時丙、丁只有互送卡片1種分配方式；第二類：甲收到的不是乙送出的卡片，這時，甲收到卡片的方式有 2種（分別是丙和丁送出的）對每一種情況，丙、丁收到卡片的方式只有一種。因此，根據乘法原理，不同的分配方式數為3X（ 1+2） =9o解法三 給四個人編號：1 , 2, 3, 4,每個號碼代表1個人，人與號碼之間的關系為一對一的關系；每個人送出的賀年卡賦給與其編號相同的數字作

20、為代表，這樣，賀年卡的分配問題可抽象為如下“數學問題”：將數字1, 2, 3, 4,填入標號為1, 2, 3, 4的4個方格里，每格填寫一個數字， 且每個方格的編號與所填數字都不同的填法共有多少種（也可以說成：用數字1, 2, 3, 4組成沒有重復數字的4位數，而且每位數字都不等于位數的4位數共有多少個）？這時，可用乘法原理求解答案：首先，在第1號方格里填寫數字，可填上 2、3、4中的任一個數，有 3種填法；其次，當第1號方格填寫的數字為i （2 w i w 4）時，則填寫第i種方格的數字，有 3種填法； 最后，將剩下的兩個數填寫到空著的兩個空格里，只有1種填法（因為剩下的兩個數中，至少有1個

21、與空著的格子的序號相同）。因此，根據乘法原理，得不同填法：3X 3X 1=9注：本題是“亂坐問題”，也稱“錯排問題”，當元素較大時，必須用容斥原理求解，但元素較小時，應用分步計數原理和分類計數原理便可以求解，或可以窮舉。例3宿舍樓走廊上有有編號的照明燈一排8盞，為節約用電又不影響照明，要求同時熄掉其中3盞，但不能同時熄掉相鄰的燈，問熄燈的方法有多少種？解法一 我們將8盞燈依次編號為1 , 2, 3, 4, 5, 6, 7, &在所熄的三盞燈中，若第一盞熄1號燈，第二盞熄3號燈，則第3盞可以熄5, 6, 7, 8號燈中的任意一盞，共有4種熄法。若第一盞熄1號燈，第2盞熄4號燈，則第3盞可

22、以熄6,乙8號燈中的任意一盞。依次類推，得若1號燈熄了，則共有 4+3+2+仁10種熄法。若1號燈不熄，第一盞熄的是 2號燈，第二盞熄的是 4號燈，則第三盞可以熄 6, 7, 8號燈中 的任意一盞，共有 3種熄法。依次類推得，若第一盞燈熄的是2號燈，則共有3+2+1=6種熄法。同理，若第一盞熄的是 3號燈，則共有2+1=3種熄法。同理，若第一盞熄的是 4號燈，則有1種熄法。綜上所述共有：10+6+3+仁20種熄法。解法二 我們可以假定8盞燈還未安裝，其中 5盞燈是亮著的，3盞燈不亮。這樣原問題就等 價于：將5盞亮著的燈與3盞不亮的燈排成一排，使 3盞不亮的燈不相鄰（燈是相同的）。5盞亮著 的燈

23、之間產生6個間隔（包括兩邊），從中插入3個作為熄滅的燈一一就是我們經常解決的“相鄰不 相鄰”問題，采用“插入法”，得其答案為C63=20種。注 解法一是窮舉法，將所有可能的情況依次逐一排出。這種方法思路清晰，但有時較繁。方 法二從另外一個角度審題，認清其數學本質，抽象成數學模型，解題時有一種豁然開朗的感覺。例4 已知直線ax+by+c=0中的a,b,c 是取自集合-3,-2,-1,0,1,2,3 中的3個不同的元素， 并且該直線的傾斜角為銳角，求符合這些條件的直線的條數。解 設傾斜角為B,由B為銳角，得 tan 0 =- - >0,即a、b異號。b（1）若 c=0, a、b 各有 3 種

24、取法，排除 2 個重復（3x-3y=0,2x-2y=0,x-y=0）,故有 3X 3-2=7（條）。（2）若c豐0, a有3種取法，b有3種取法，而同時c還有4種取法，且其中任兩條直線均不相同，故這樣的直線有 3 X 3X 4=36條，從而符合要求的直線共有7+36=43條。注：本題是1999年全國高中數學聯賽中的一填空題，據抽樣分析正確率只有 0.37。錯誤原因沒有對c=0與cm0正確分類；沒有考慮 c=0中出現重復的直線。例5平面上給定10個點，任意三點不共線，由這10個點確定的直線中，無三條直線交于同一點（除原10點外），無兩條直線互相平行。求：（1）這些直線所交成的點的個數（除原 10

25、點外）。（2）這些直線交成多少個三角形。解法一 （1 ）由題設這10點所確定的直線是 C10 =45條。這45條直線除原10點外無三條直線交于同一點，由任意兩條直線交一個點，共有C452個交點。而在原來10點上有9條直線共點于此。所以，在原來點上有10C92點被重復計數。所以這些直線交成新的點是：C452-10C92=630。（2）這些直線所交成的三角形個數可如下求：因為每個三角形對應著三個頂點，這三個點來自 上述630個點或原來的10個點。所以三角形的個數相當于從這640個點中任取三個點的組合，即C640 =43 486080 （個）。解法二 （1）如圖對給定的10點中任取4個點，四點連成6

26、條直線，這6條直線交3個新的點。故原題對應于在10個點中任取 4點的不同取法的3Cio =630。3倍，即這些直線新交成的點的個數是:例7(1 )求4 X 6n+5n+1被20除后的余數;(2) 7n+C?7n-1+G2 嚴+Gn-1X 7除以9,得余數是多少？(3) 根據下列要求的精確度，求1.02 5的近似值。精確到 解 (1 )首先考慮4 6n+5n+1被4整除的余數。n+1n+1 n+1_1 n _2 n-1_ n5 =(4+1) =4 +G+1 4 +G+1 4 + +G+1 4+1其被4整除的余數為10.01 :精確到 0.001。被20整除的余數可以為1 , 5, 9, 13 ,

27、 17然后考慮4 6n+1+5n+1被5整除的余數。/ 4 6n=4 (5+1) n=4(5 n+Cn1 5n-1+G2 5n-2 +Gn-1 5+1) 被5整除的余數為4(2)同解法一。注 用排列、組合解決有關幾何計算問題，除了應用排列、組合的各種方法與對策之外，還要 考慮實際幾何意義。其被20整除的余數可以為 4, 9, 14, 19。綜上所述，被20整除后的余數為9。2)7 n+Cn1 7n-1+G2 7n-2+Gn-1 7項;(1)如果(X+1) 2n展開式中，第四項與第六項的系數相等。求n,并求展開式中的常數x 1 8求(.、x-1)展開式中的所有的有理項。2如=(7+1) n-1=

28、8 n-1=(9-1) n-1n _ 1n-1 _ 2n-2n-1 _ n-1n _ n=9 -Cn 9 +G 9 + +(-1) G 9+(-1) C-1 (i)當n為奇數時原式=9n-Cn1 9n-1+G2 9n-2+ (-1 ) n-1Gn-1 9-2除以9所得余數為7。35(1)由 C2n =C2n,可得 3+5=2n解/ n=4。設第k+1項為常數項k則 T k+i=C8 x 8-2k=0 ,常數項為(2)設第(ii)當n為偶數時原式=9n-Cn1 9n-1+G2 9n-2+(-1) n-1Gn-1 98-k-k k&2k x =C8 x即k=44T5=G =70。k+1項有

29、理項，則除以9所得余數為5(3) (1.02)疋=1+c0,即被9整除。5(1+0.02 )51 0.02+C52 0.02 2+G3 0.02 3+C540.02 4+G5 0.02 5/ C2X 0.02 2=0.004,C 53x 0.02 3=8X 10-5當精確到0.01時，只要展開式的前三項和，1+0.10+0.004=1.104，近似值為1.10。當精確到 0.001時，只要取展開式的前四項和，1+0.10+0.004+0.0008=1.10408 ，近似值為8 -kX亍(弓kxi14 x k(-尹 4)1641.104。注 (1 )用二項式定理來處理余數問題或整除問題時，通常把

30、底數適當地拆成兩項之和或之差 再按二項式定理展開推得所求結論。(2)用二項式定理來求近似值，可以根據不同精確度來確定應該取到展開式的第幾項。16 3k Z,只有使k分別取0, 4, 84所以所求的有理項應為：4351-2T1=x ,T 5= x,T 9=x8256注 (1) 二項式展開中，要注意“系數”與“二項式系數”的區別;(2)在二項展開式中求得 k后，對應的項應該是 k+1項。例8 證明下列不等式:因為0< k w 8,要使(1)a + b)n, (a、b x|x 是正實數,n N)21 1(2)已知 a、b 為正數，且一+ =1,則對于 n N有(a+b) n-an-bn>

31、22n-2n+1。a b證明 (1 )令 a=x+ S, b=x- S則x=n n ,、n ,、na +b =(x+ S ) +(x- S )n 1n-1n 從 n n 1n-1n n=x +Cn x S + +Cn S +x -Cn x S + (-1) G S由得，2Gp=Gp+Gpn + 1- p p + 1兩邊約去Gp,可得：n 2 n-2 、 24 n-4 、 4、=2(x +Cn x S +G x S + )n> 2x由得,2G+1pCn+1n n 1 n-1n. n(2) (a+b) =a +Cn a b+ +G b1. n-1(a+b) =b+Gb a+C a上述兩式相加

32、得：n n n _ 1n-1n-1_ k n-k k n-k k_ n n n2(a+b) =(a+b)+Cn(a b+b a)+G (a b +b a)+Cn (a +b) (*)1 1_ +_=1，且a、b為正數a b/ ab=a+b> 2 ab / ab>4約去G+/可得，n=3p+1n = 3p 1又an-kbk+bn-kak> 2 .an bn=2( . ab )"(k=1,2,n-1)得：n=7,p=2.將p=2 ,n=7代入得：C57(-a) 5+C76 - (-a) 6=0解之得：a=0或3。若a=0，則(1-0 x) 8的中間項T5=0, (1-0

33、 x) 7展開式中系數最大的項是T1=1。若a=3,則(1-3x ) 8的中間項T5=C84 (-3x ) 4=5670x4, ( 1-3x ) 7的展開式中，奇數項系數為正,k個元素的不同組合有Cn+1。 2(a+b) n >2an+2bn+cn12( ab) n+Cn22 ( . ab ) n+- +Gn-12( . ab )n (a+b) n-a n-bn> (c'+G2+Gn-1) ( i ab ) nnn> (2 -2) 2=22n-2 n+1注 利用二項式定理的展開式，可以證明一些與自然數有關的不等式問題。題(1)中的換元法稱之為均值換元(對稱換元)。這樣消去S奇數次項，從而使每一項均大于或等于零。題(2)中，由由稱