1、 第十二章排列組合二項式定理 排列、組合是初等數學的重要基礎知識之一,在生產實際問題中有著廣泛的應用,同時也是學習概率和數理統計等數學知識的基礎。本章主要介紹有關排列、組合的基本概念、計算方法及二項式定理。第一節加法原理與乘法原理我們先看一個具體問題。圖12-1第二節排列一、排列的基本概念前面我們分析了兩個基本原理,下面就要用這兩個基本原理進一步分析排列的概念。先看下面兩個實例。例1北京、上海、重慶三個民航站之間的直達航線需要準備多少種不同的飛機票?解在這些直達航線上,每一個起點站到終點站之間都需要準備一種飛機票,即從這三個航站中每次任意取出兩個站,按照起點站在前、終點站在后的順序排法,那么一

2、種票就對應著一種排法,所有的票類數也就對應著所有的排法。完成上述排法可分兩步進行:第一步確定起點站,在三個航站中任選一站,共有3種選法;第二步確定終點站,選定起點站后,終點站只能從剩下的兩個航站中任選一站,共有2種選法。根據乘法原理,完成上述排法共有32=6(種)方法,也就是需要準備6種不同的飛機票。可以表示為:例2某班級要從甲、乙、丙三位學生中選兩位擔任正、副班長,問共有多少種不同選法?解這個問題可以分為兩個步驟完成:第一步,從甲、乙、丙三位學生中任選一位擔任正班長,共有3種選法;第二步,選出正班長后,從余下的兩位學生中任選一位擔任副班長,有2種選法。根據乘法原理,共有32=6(種)不同的選

3、法。上述選法,也可以表示為:盡管上面兩個實例考察的對象與研究的問題是不同的,但是,如果抽去它們的實際意義把考察的對象(民航站、學生)稱為元素,那么上述兩個例子都可以變為“從三個不同的元素里,每次取出兩個,然后按照一定順序排成一列,求共有多少種不同排法的問題。對于這樣的問題,給出下面的定義。定義從n個不同的元素中,任取m(mn)個元素,按照一定的順序排成一列,稱為從n個不同的元素中取出m個元素的一個排列。由排列的定義可知,如果兩個排列相同,不僅這兩個排列的元素完全相同,而且排列的順序也必須完全相同。如果兩個排列所含的元素或順序不完全相同,它們就是兩個不同的排列。當mn時,所得的排列稱為選排列。當

4、m=n時,所得的排列稱為全排列。二、排列種數的計算公式從上面兩例的排法知道,從3個不同元素中取出2個元素的所有排列的個數為6(種),我們把個數6稱為從3個不同元素中取出2個元素的排列種數。從n個不同元素中取出m(mn)個元素的所有排列的個數稱為從n個不同元素取出m個元素的排列種數,用符號表示。當n=m時,全排列種數為,也可表示為Pn。上述兩例的排列種數都是。下面我們就用乘法原理來推導排列種數的計算公式。如圖12-2所示,設有排好順序的m個空位,從n個不同的元素a1,a2,a3,an中任取m(mn)個元素去填空,一個空位填一個元素,每一種填法就得到一個排列,所有不同填法的種數就是排列種數。圖12

5、-2現在我們計算共有多少種不同的填法。第一步,第1個空位可以從n個元素中任選一個填上,共有n種填法;第二步,第2個空位只能從余下的n-1個元素中任選一個填上,共有n-1種填法;依次類推,當前面m-1個空位都填上后,第m個空位只能從余下的n-(m-1)個元素中任選一個填上,共有n-m+1種填法。根據乘法原理,全部填滿m個空位的填法數為 即排列種數的計算公式為 這里m,nN,且mn。式(12-1)中有以下特點:公式右邊的第一個因數是n,后面的每一個因數都比它前面的因數少1,最后一個因數為n-m+1,共有m個因數連乘。排列種數公式中,當m=n時,有 我們把乘積n(n-1)(n-2)321記為n!,讀

6、作n階乘。所以,全排列種數的計算公式為 這個公式指出,n個不同元素全部取出的排列種數等于自然數1到n的連乘積。例如:P6=6!=654321=720。排列種數式(12-1)經過變形也可寫成下列形式=n(n-1)(n-2)(n-m+1)= = 即=(12-3)為使公式在m=n時成立,規定:0!=1。例3計算:(1) 3-2;(2) 。解(1) 3-2=354-2543=60-120=-60;(2) =1。例4求滿足=42的n的值。解由=n(n-1)=42得n2-n-42=0分解因式得(n-7)(n+6)=0解得n1=7,n2=-6因為nN,故n=7 例5某段鐵路上有10個車站,共需要準備多少種普

7、通車票?解因為每張車票對應著2個車站的一個排列,因此需要準備的車票種數就是從10個車站中任取2個的排列數,即=109=90(種)因此,需要準備90種不同的車票。例6有5個同學排成一排拍照,共有多少種排法?解這個問題可看成是從5個不同元素中取出5個不同元素進行的全排列,所以P5=5!=54321=120(種)即有120種不同的排法。例7用0、1、2、3、4這五個數字可以組成多少個沒有重復數字的三位數? 解這個問題可用兩種方法求解。 方法一,直接法因為三位數的百位不能為0,所以用0、1、2、3、4這五個數字組成的三位數就有一個約束條件,0不能放在首位,這個問題可分兩步完成:第一步,從1、2、3、4

8、中任取一個數放在百位,有種方法;第二步從余下的4個數字中任取2個數進行選排列,有種方法。根據乘法原理所求的三位數的個數是=443=48(個)方法二,間接法如果先不考慮0是否能放在百位,則從0、1、2、3、4中任選3個數組成三位數的排列種數為。但這其中必須扣去0在百位的排列數,0放在百位后,余下2個空位,只能從1、2、3、4中任選2個,有種,所以所求三位數的個數是上述兩個排列的差。即-=543-43=60-12=48(個)該題也可用我們上一節講的方法,分三步考慮:第一步確定百位,只能從1、2、3、4中任取一個,有種;第二步從余下的四個數中任取1個確定十位,有種;第三步確定個位,從余下的三個數中任

9、取1個,有種。根據乘法原理得到所求三位數的個數為=443=48(個)三、重復排列上面討論的是從n個不同元素中,所取的m(mn)個元素是不相同的,即沒有元素重復出現。但在很多實際問題中,會遇到允許元素重復出現的情況。例如,1、2、3這三個數可以組成多少個兩位數?組成這個兩位數可以分兩步進行:第一步,先排十位,共有3種選擇;第二步,排個位,由于沒有要求數字不可重復,所以個位仍有3種選擇。由乘法原理可得兩位數的個數共有33=9(個),即:11、22、33、12、13、23、21、31、32,共9個。元素可以重復選取的排列,稱為重復排列一般地,從n個不同元素中允許重復地選取m個元素的排列種數為N=nm

10、 第三節組合一、組合的基本概念例1北京、上海、重慶三個民航站之間的直達航線,應有多少種不同的票價?解這個問題與上節求飛機票種數的問題不同,飛機票的種數要考慮起點、終點站的順序關系,從北京到上海和從上海到北京的飛機票是不相同的。但飛機票的票價與起點、終點站的順序無關,只與兩站間的距離有關。從北京到上海和從上海到北京的票價是一樣的,所以當三個航站之間距離兩兩不相等時,票價的種數只有飛機票種數的一半,即有=3種。例2從甲、乙、丙三位同學中選出兩位擔任班長候選人,共有多少種不同的選法?解這個問題與上節中選兩位同學擔任正、副班長的問題不一樣。選出兩位同學擔任正、副班長,要考慮順序,如甲擔任正班長、乙擔任

11、副班長和乙擔任正班長、甲擔任副班長是屬于兩種不同的選法。而作為本例,選兩位候選人,則屬同一種選法。所以從三位同學中選出兩位班長候選人的種數,也只有從三位同學中選兩位擔任正、副班長種數的一半,即有=3種。由此可見,這兩個實例和上節排列的問題不同,它們都是從三個不同元素中每次取出兩個元素,但不必考慮順序,并成一組,求共有多少種不同組數的問題。對于這類問題,給出下面的定義。定義從n個不同的元素中,任取m(mn)個元素,不考慮順序并成一組,稱為從n個不同的元素中取出m個元素的一個組合。在排列中,要考慮取出元素間的順序,例如,ab,ba是屬于兩個不同的排列;在組合中不需考慮元素間的順序,例如,ab與ba

12、是屬于同一個組合。例3寫出a、b、c、d這四個字母中每次取出三個字母的所有組合。解按給定字母從左到右的順序考慮,共有:abc,abd,acd,bcd四種不同的組合。二、組合種數的計算公式從n個不同元素中取出m(mn)個元素的所有組合的個數稱為從n個不同元素中取出m個元素的組合種數,用符號表示。如,本節例1和例2的組合種數都是,例3中從四個不同元素中取出三個元素的組合種數表示為。下面我們從研究組合種數與排列種數的關系來推導出組合種數的計算公式。先考察從四個不同元素a、b、c、d中取出三個不同元素的排列與組合的關系,如圖12-4所示。圖12-3從圖12-3可以看出,從四個不同元素中任取三個元素的排

13、列種數可以分兩步完成:第一步,先從四個不同元素中任取三個不同元素作組合,共有=4種;第二步,對每一個組合中的3個不同元素作全排列,各有P3種。由乘法原理得:=P3。所以= 這個結論可以作進一步推廣。一般地,從n個不同元素中取出m個不同元素的排列種數也可分兩步完成:第一步,求出從n個不同元素中取出m個元素的組合種數;第二步,求出每一個組合中m個元素的全排列Pm。由乘法原理得:=Pm。所以得出組合種數的計算公式為=(12-4)這里,m、nN,且mn。因為=,Pm=m!,所以=(12-5)球隊的順序無關,所以這是一個組合問題。即=66(場)故需要安排66場足球比賽。例4有12支足球隊進行單循環比賽,

14、共需安排多少場比賽?解因為每一場比賽只與哪兩支球隊參賽有關,而與這兩支三、組合種數的兩個性質性質1=(12-6)證明因為=,有= 所以= 由性質1可知,當n=m時,=1。性質2+=(12-7)證明+=+ = = = 例6解方程=。解方程中,x與x-4的關系有兩種可能:(1) x=x-4,此時方程無解;(2) 由性質1得x=18-(x-4), 有x=11經檢驗,x=11是原方程的解。例7求證:+=。證明由=1=,再由性質2得左式=+=+ =+ = = 即左式=右式。四、排列、組合的綜合應用我們在前面已經學習了排列、組合的一些簡單的應用問題。但在實際問題中有些既含有排列,又含有組合的問題,需要綜合

15、應用排列、組合的知識來解決。綜合應用題的關鍵在于分清所求問題是否與順序有關,如與順序有關就屬于排列問題。與順序無關則屬于組合問題。 例8從6位男同學中選出3位,從4位女同學中選出2位,分別擔任班委中五項不同的職務,求共有多少種不同的選法?解這個問題要分三步進行:第一步,先從6位男同學中任選3位,這與順序無關,屬于組合問題,共有種;第二步,從4位女同學中任選2位,也與順序無關,屬于組合問題,共有種;第三步,從選出的5位學生中安排5項不同職務,這與順序有關,屬于全排列問題,共有P5種。由乘法原理得到不同的選法為:P5=206120=14400(種)。第四節二項式定理一、二項式定理的基本概念我們以前學過(a+b)2=a2+2ab+b2 (a+b)3=a3+3a2b+3ab2+b3 但是如何進一步求(a+b)4、(a+b)5(a+b)n(nN)的展開式呢?如果用多項式的乘法來求太煩瑣。先看(a+b)3的展開式(a+b)3=(a+b)(a+b)(a+b)=aaa+(aab+aba+baa)+(abb+bab+bba)+bbb=a3+3a2b+3ab2+b3 可見等式右端的各項,是三個相同的括號(a+b)里,各任取a、b中之一相乘,再合并同類項而得