第十二章基本的組合計數(shù)公式分析

1、閩南師范大學(xué)計算機學(xué)院閩南師范大學(xué)計算機學(xué)院第十二章第十二章 基本的組合計數(shù)公式基本的組合計數(shù)公式第十二章第十二章 基本的組合計數(shù)公式基本的組合計數(shù)公式加法法則與乘法法則加法法則與乘法法則排列與組合排列與組合二項式定理與組合恒等式二項式定理與組合恒等式多項式定理多項式定理知知 識識 點：加法法則與乘法法則、排列和組合的定義、排列和組合的生點：加法法則與乘法法則、排列和組合的定義、排列和組合的生 成算法、基本恒等式成算法、基本恒等式、二項式定理、多項式定理二項式定理、多項式定理教學(xué)要求：深刻理解和掌握排列、組合的基本概念及基本應(yīng)用。教學(xué)要求：深刻理解和掌握排列、組合的基本概念及基本應(yīng)用。教學(xué)重點

2、：排列和組合的定義的概念及基本應(yīng)用。教學(xué)重點：排列和組合的定義的概念及基本應(yīng)用。學(xué)時學(xué)時: 412.1 加法法則與乘法法則加法法則與乘法法則加法法則加法法則: 如果事件如果事件 A 有有 m 種產(chǎn)生方式種產(chǎn)生方式 , 事件事件 B 有有n種產(chǎn)生方式種產(chǎn)生方式,當(dāng)當(dāng)A與與B產(chǎn)生的方式不重疊時產(chǎn)生的方式不重疊時, ”事件事件A或或B” 有有 m + n 種產(chǎn)生方式種產(chǎn)生方式n加法原理中事件的產(chǎn)生方式應(yīng)是互相排斥的加法原理中事件的產(chǎn)生方式應(yīng)是互相排斥的n加法法則加法法則 (集合形式集合形式): 若若 S=AB,AB=,則則 |S|=|A|+|B|n加法法則的推廣加法法則的推廣: 設(shè)設(shè)A1,A2,An

3、是是n個事件個事件,它們的產(chǎn)生方式分別它們的產(chǎn)生方式分別有有p1,p2,pn種種,當(dāng)其中任何兩個事件產(chǎn)生的方式都不重疊時當(dāng)其中任何兩個事件產(chǎn)生的方式都不重疊時,事事件件” A1或或A2或或或或An”有有p1+p2+pn種產(chǎn)生方式種產(chǎn)生方式汽車汽車火車火車甲地甲地乙地乙地飛機飛機輪船輪船陸路陸路水路水路甲地甲地乙地乙地12.1 加法法則與乘法法則加法法則與乘法法則乘法法則乘法法則: 事件事件 A 有有 m 種產(chǎn)生方式種產(chǎn)生方式, 事件事件B 有有n 種產(chǎn)生方式種產(chǎn)生方式,當(dāng)當(dāng)A與與B產(chǎn)生產(chǎn)生的方式彼此獨立時的方式彼此獨立時, “事件事件 A 與與 B ” 有有 mn 種產(chǎn)生方式種產(chǎn)生方式 n乘法

4、法則中各事件的出現(xiàn)應(yīng)是相互獨立的乘法法則中各事件的出現(xiàn)應(yīng)是相互獨立的, 也就是說也就是說B的出現(xiàn)不受的出現(xiàn)不受A的影響的影響, 同樣同樣A的出現(xiàn)也不受的出現(xiàn)也不受B的影響的影響n乘法法則乘法法則 (集合形式集合形式) : 若若 S=AB, 則則 |S|=|A|B|n乘法法則的推廣乘法法則的推廣: 設(shè)設(shè)A1,A2,An是是n個事件個事件,它們的產(chǎn)生方式分別它們的產(chǎn)生方式分別有有p1,p2,pn種種,當(dāng)其中任何兩個事件產(chǎn)生的方式都彼此獨立時當(dāng)其中任何兩個事件產(chǎn)生的方式都彼此獨立時,事件事件” A1與與A2與與與與An有有p1p2pn種產(chǎn)生方式種產(chǎn)生方式1甲地甲地乙地乙地32abcd丙地丙地1甲地甲

5、地乙地乙地32abcd丙地丙地丁地丁地戊地戊地stxyzA上的函數(shù)上的函數(shù) f 可以用二元關(guān)系表示成可以用二元關(guān)系表示成f=,每個每個yi都有都有n種不同的選擇種不同的選擇,根據(jù)乘法法則根據(jù)乘法法則,有有nn個不同的函數(shù)個不同的函數(shù)當(dāng)當(dāng) f 是雙射時是雙射時,yi y2,yn之間都互不相同之間都互不相同構(gòu)造雙射的方法構(gòu)造雙射的方法:第一步確定第一步確定y1,y1共有共有n種可能的取值種可能的取值第二步確定第二步確定y2,y1確定后確定后y2只有只有n-1種可能取值種可能取值第第n步確定步確定yn , yn只有一種取值只有一種取值根據(jù)乘法法則根據(jù)乘法法則 有有n(n-1)(n-2)1個不同的構(gòu)造

6、方法個不同的構(gòu)造方法12.1 加法法則與乘法法則加法法則與乘法法則例例12.1 設(shè)設(shè)A為為n元集元集,問問nA上的自反關(guān)系有多少個上的自反關(guān)系有多少個nA上的反自反關(guān)系有多少個上的反自反關(guān)系有多少個nA上的對稱關(guān)系有多少個上的對稱關(guān)系有多少個nA上的反對稱關(guān)系有多少個上的反對稱關(guān)系有多少個nA上的函數(shù)有多少個上的函數(shù)有多少個nA上的雙射函數(shù)有多少個上的雙射函數(shù)有多少個11*1111RMn元集元集A上的二元關(guān)系上的二元關(guān)系R的關(guān)系矩陣的關(guān)系矩陣R是是A上的自反關(guān)系當(dāng)且僅當(dāng)上的自反關(guān)系當(dāng)且僅當(dāng)在在MR中中 對主角線上的元素全都為對主角線上的元素全都為1,非主對角線上的元素可以是非主對角線上的元素可

7、以是0或或1。非主對角線的位置有非主對角線的位置有n2-n個個,根據(jù)乘法法根據(jù)乘法法則自反關(guān)系的個數(shù)是則自反關(guān)系的個數(shù)是 2 n2-n00*0000RMR是是A上的反自反關(guān)系當(dāng)且僅當(dāng)上的反自反關(guān)系當(dāng)且僅當(dāng)在在MR中中 對主角線上的元素全都為對主角線上的元素全都為0,非主對角線上的元素可以是非主對角線上的元素可以是0或或1。非主對角線的位置有非主對角線的位置有n2-n個個,根據(jù)乘法法根據(jù)乘法法則自反關(guān)系的個數(shù)是則自反關(guān)系的個數(shù)是 2 n2-n*0*10*1*RMR是是A上的對稱關(guān)系當(dāng)且僅當(dāng)上的對稱關(guān)系當(dāng)且僅當(dāng)MR是對稱矩陣。是對稱矩陣。主對角線上的元素可以是主對角線上的元素可以是0或或1,主對角

8、線的位置有主對角線的位置有n個個,在每對在每對非主對角線的非主對角線的對稱位置上對稱位置上,兩個元素取值同時是兩個元素取值同時是0或同時是或同時是1,這樣的對稱位置共有這樣的對稱位置共有(n2-n)/2對。對。根據(jù)乘法法則對稱關(guān)系的個數(shù)是根據(jù)乘法法則對稱關(guān)系的個數(shù)是 2 (n2+n)/2*$*$*RMR是是A上的反對稱關(guān)系當(dāng)且僅當(dāng)在上的反對稱關(guān)系當(dāng)且僅當(dāng)在MR非主對角線的位置非主對角線的位置上上,關(guān)于主對角線對稱的兩個位置取值不能全為關(guān)于主對角線對稱的兩個位置取值不能全為1。主對角線上的元素可以是主對角線上的元素可以是0或或1,主對角線的位置有主對角線的位置有n個個,在每對在每對非主對角線的非

9、主對角線的對稱位置上對稱位置上,兩個元素取值有三種兩個元素取值有三種不同的情況不同的情況,這樣的對稱位置共有這樣的對稱位置共有(n2-n)/2對。對。根據(jù)乘法法則對稱關(guān)系的個數(shù)是根據(jù)乘法法則對稱關(guān)系的個數(shù)是 2n3 (n2-n)/2這兩個元素的取值有三這兩個元素的取值有三種不同的情況種不同的情況:(0,0), (0,1), (1,0)上、下三角區(qū)域上、下三角區(qū)域分別有分別有1+2+(n-1)個元素個元素例例12.2 Ipv4協(xié)議網(wǎng)址計數(shù)協(xié)議網(wǎng)址計數(shù): 32 位地址位地址(w.x.y.z):網(wǎng)絡(luò)標(biāo)識網(wǎng)絡(luò)標(biāo)識+主機標(biāo)識主機標(biāo)識 A類類:最大網(wǎng)絡(luò)；最大網(wǎng)絡(luò)；B類類:中等網(wǎng)絡(luò)；中等網(wǎng)絡(luò)；C:最小網(wǎng)絡(luò)；

10、最小網(wǎng)絡(luò)；D類類:多路廣播；多路廣播；E類類:備用備用 限制條件：限制條件：1111111 在在A 類中的網(wǎng)絡(luò)標(biāo)識部分無效類中的網(wǎng)絡(luò)標(biāo)識部分無效 主機標(biāo)識部分不允許全主機標(biāo)識部分不允許全0或全或全1 A 類類: netid 271, hostid 2242 , 地址數(shù)地址數(shù): 127 * 16777214 B 類類: netid 214, hostid 2162 , 地址數(shù)地址數(shù): 16384 * 65534 C 類類: netid 221, hostid 282 , 地址數(shù)地址數(shù): 2097152 * 254 Ipv4協(xié)議網(wǎng)址總數(shù)協(xié)議網(wǎng)址總數(shù)= 2130706178+1073709056+5

11、32676608 = 373709184212.1 加法法則與乘法法則加法法則與乘法法則12.1 加法法則與乘法法則加法法則與乘法法則加法法則與乘法法則的其它加法法則與乘法法則的其它例子例子n從城市從城市A到城市到城市B有兩條陸路有兩條陸路, 兩條水路兩條水路, 一條航線一條航線, 則由推廣的加法原理知則由推廣的加法原理知, 從從A到到B有有2 + 2 + 1 = 5種走法。種走法。n書架上有三本不同的英語書書架上有三本不同的英語書, 兩本不同的日語書兩本不同的日語書, 兩本不同的俄語兩本不同的俄語書書, 一個學(xué)生要選英語、日語、俄語書各一本一個學(xué)生要選英語、日語、俄語書各一本, 由推廣的乘法

12、原理知共有由推廣的乘法原理知共有3 2 2 = 12種選法。種選法。 n求比求比10000小的正整數(shù)中含有數(shù)字小的正整數(shù)中含有數(shù)字1的數(shù)的個數(shù)。的數(shù)的個數(shù)。 12.2 排列與組合排列與組合設(shè)設(shè)n元集合元集合S,從從S 中選取中選取r 個元素個元素,根據(jù)是否有序根據(jù)是否有序,是否允許是否允許重復(fù)可以將該問題分為四個子類型重復(fù)可以將該問題分為四個子類型例例: S=1,2,3,4,5,從從S中選取中選取3個元素個元素n無重復(fù)排列無重復(fù)排列: 1 2 3 , 2 1 3 , 5 2 4 看作不同的選取結(jié)果看作不同的選取結(jié)果n可重復(fù)排列可重復(fù)排列: 1 1 2 , 1 2 1 , 2 1 3 看作不同的

13、選取結(jié)果看作不同的選取結(jié)果n無重復(fù)組合無重復(fù)組合: 1 2 3 , 2 4 5 是不同的選取結(jié)果是不同的選取結(jié)果 但但 1 2 3 , 2 1 3看作相同的選取結(jié)果看作相同的選取結(jié)果n可重復(fù)組合可重復(fù)組合: 1 1 3 , 2 4 5 是不同的選取結(jié)果是不同的選取結(jié)果 但但 1 1 3 , 1 3 1看作相同的選取結(jié)果看作相同的選取結(jié)果不重復(fù)不重復(fù)重復(fù)重復(fù)有序有序集合排列集合排列P(n,r)多重集排列多重集排列無序無序集合組合集合組合C(n,r)多重集組合多重集組合12.2 排列與組合排列與組合定義定義12.1 設(shè)設(shè)n元集合元集合Sn從從S 中有序選取的中有序選取的r 個元素稱作個元素稱作S的

14、一個的一個r排列排列,S的不同的不同r排列總數(shù)排列總數(shù)記作記作P(n,r), r=n時的排列稱為時的排列稱為S的全排列的全排列n從從S 中無序選取的中無序選取的r 個元素稱作個元素稱作S的一個的一個r組合組合,S的不同的不同r組合總數(shù)組合總數(shù) 記作記作C(n,r),有時也記作有時也記作定理定理12.1 設(shè)設(shè)n,r為自然數(shù)為自然數(shù),規(guī)定規(guī)定0!=1,則則rnrnrnnnrnnrnP,0,) 1).(1()!(!),(rnrnrnrnrrnPrnC,0,)!( !),(),(rn12.2 排列與組合排列與組合例例 設(shè)設(shè)S=1,2,3,4n從從S的所有不同的所有不同3排列排列(從從S中有序選取中有序

15、選取3個元素得到的排列個元素得到的排列) 1 2 3 , 1 3 2 , 2 1 3 , 2 3 1 , 3 1 2 , 3 2 1 1 2 4 , 1 4 2 , 2 1 4 , 2 4 1 , 4 1 2 , 4 2 1 1 3 4 , 1 4 3 , 3 1 4 , 3 4 1 , 4 1 3 , 4 3 1 2 3 4 , 2 4 3 , 3 2 4 , 3 4 2 , 4 2 3 , 4 3 2 P(4,3)=24n從從S的所有不同的所有不同3組合組合(從從S中無序選取中無序選取3個元素得到的組合個元素得到的組合) 1 2 3 , 1 2 4 , 1 3 4 , 2 3 4 C(4,

16、3)=412.2 排列與組合排列與組合推論推論1 元素依次排成一個圓圈的排列稱為環(huán)排列元素依次排成一個圓圈的排列稱為環(huán)排列.S的的r環(huán)環(huán)排列數(shù)等于排列數(shù)等于 P(n,r)/rn證證: 設(shè)線排列的設(shè)線排列的r個元素依次為個元素依次為 a1,a2,ar , 將將a1接在接在ar的后面的后面就組成一個環(huán)排列就組成一個環(huán)排列.只要相鄰關(guān)系不變只要相鄰關(guān)系不變,這這r個元素中的任何一個作為個元素中的任何一個作為線排列的首元素線排列的首元素,首尾相連所構(gòu)成的環(huán)排列都是相同首尾相連所構(gòu)成的環(huán)排列都是相同.因此環(huán)排列數(shù)因此環(huán)排列數(shù)是線排列數(shù)的是線排列數(shù)的1/r .例例 一家人請客入席一家人請客入席, 共共8個

17、人個人, 圍圓桌而坐圍圓桌而坐, 若座位不編號有多少種坐法若座位不編號有多少種坐法? 座位編號呢座位編號呢? 解解 座位不編號為環(huán)狀排列問題座位不編號為環(huán)狀排列問題, 有有7! = 5040種坐法種坐法. 座位編號實際上為非環(huán)狀排列問題座位編號實際上為非環(huán)狀排列問題 , 故有故有8! = 40320種坐法種坐法 . aedcbcabde12.2 排列與組合排列與組合推論推論2 設(shè)設(shè)S=a,b,c,d,e,n=5,r=3, C(5,3)=10n考慮含有考慮含有a的組合的生成方法的組合的生成方法: 從余下的從余下的4個元素中取個元素中取2個再加上個再加上a, 含有含有a的組合共有的組合共有C(4,

18、2)=6種種,同理含有同理含有b,c,d,e的組合都各有的組合都各有6種種,這樣共得到這樣共得到 5*C(4,2)種組合種組合. 但每種組合都被重復(fù)計算了但每種組合都被重復(fù)計算了3次次. 例如例如(a,b,c),分別在計算含有分別在計算含有a,b,c的組合中各被計算了一次的組合中各被計算了一次 所以所以 C(5,3)=5*C(4,2)/3=5*6/3=10n選取一個選取一個3組合時組合時,沒有被選取的元素同時也組成了一個沒有被選取的元素同時也組成了一個2組合組合 例如例如 選取選取 (a,b,c),同時也得到一個同時也得到一個2組合組合(d,e),即即C(5,3)=C(5,2)n所有的所有的3

19、組合分成一類含有組合分成一類含有a,一類不含有一類不含有a . 含有含有a的組合如上述方的組合如上述方法法 共有共有C(4,2)種種,不含有不含有a的組合是從余下的的組合是從余下的4個元素中選取出個元素中選取出,共共有有C(4,3)種種,根據(jù)加法法則根據(jù)加法法則 C(5,3)=C(4,2)+C(4,3)1,1(),1(),(),(),()1,1(),(rnCrnCrnCrnnCrnCrnCrnrnC12.2 排列與組合排列與組合多重集多重集: S= n: S= n1 1aa1 1 , , n n2 2aa2 2 , , , , n nk kaak k n其中其中 a a1 1 , a, a2

20、2 , , a, , ak k 是是 k k 個不同的元素個不同的元素nN Ni i 表示表示 a ai i 在在S S中出現(xiàn)的次數(shù)中出現(xiàn)的次數(shù), ,稱作稱作a ai i的重復(fù)度的重復(fù)度nn ni i=時表示有足夠多的時表示有足夠多的a ai i以備選取以備選取, ,即即a ai i的選取次數(shù)不受限制的選取次數(shù)不受限制定義定義12.2 12.2 設(shè)設(shè)S=S= n n1 1aa1 1 , , n n2 2aa2 2 , , , , n nk kaak k 為多重集為多重集, , n=n n=n1 1+n+n2 2+n+nk k 表示表示S S中元素的總數(shù)中元素的總數(shù) (1)(1)從從S S中有序

21、選取的中有序選取的r r個元素稱為多重集個元素稱為多重集S S的一個的一個 r r排列排列. . 當(dāng)當(dāng) r=n r=n 時的排列稱為時的排列稱為 S S 的全排列的全排列 (2)(2)從從S S中無序選取的中無序選取的r r個元素稱為多重集個元素稱為多重集S S的一個的一個r r組合組合例例 由由a,b,c,da,b,c,d四個字母組成的長度為四個字母組成的長度為1010的字符串是多重集的的字符串是多重集的1010排列排列 英文單詞英文單詞 mathematics mathematics 中出現(xiàn)的所有字母中出現(xiàn)的所有字母 a a c e h i m m s t t a a c e h i m

22、m s t t 是多重集的一個是多重集的一個1111組合組合12.2 排列與組合排列與組合定理定理12.2 12.2 設(shè)設(shè)S= nS= n1 1aa1 1 , , n n2 2aa2 2 , , , , n nk kaak k 為多重集為多重集 (1)S(1)S的全排列數(shù)是的全排列數(shù)是 (2)(2)若若r r n ni i , i=1,2,k, i=1,2,k,那么那么S S的的r r排列數(shù)是排列數(shù)是 k k r rS S的全排列數(shù)也記作的全排列數(shù)也記作例例 由由1 1個個a,2a,2個個b,3b,3個個c,4c,4個個d d組成的長度為組成的長度為1010的字符串共有的字符串共有 10! /

23、(1!2!3!4!) 10! /(1!2!3!4!) 種種!21knnnnknnnn2112.2 排列與組合排列與組合定理定理12.2 當(dāng)當(dāng) r ni , i=1,2,k 時時,多重集多重集S的的r組合是組合是 C(k+r-1,r) 證明證明 設(shè)設(shè) S= n11 , n22 , , nkk 現(xiàn)有現(xiàn)有k個盒子如圖所示，編號分別為個盒子如圖所示，編號分別為1,2,k 將將 r 個完全相同的球投入到盒子中個完全相同的球投入到盒子中 第第 i 只盒子中裝有的球數(shù)只盒子中裝有的球數(shù) ti 表示表示 S中的元素中的元素 i 被取出被取出 ti 次次, 由于由于 t1+t2+ t k =r 則每次投球的結(jié)果

24、都可以得到一個從則每次投球的結(jié)果都可以得到一個從S中取中取r個元素的可重復(fù)組合。個元素的可重復(fù)組合。 將將r個球和個球和 k-1個盒子的隔板位置選好，就可以得到各個盒子的球數(shù)個盒子的隔板位置選好，就可以得到各個盒子的球數(shù) 而這樣的位置選擇恰好有而這樣的位置選擇恰好有 C(k+r-1,r) 種種 123ik12.2 排列與組合排列與組合例例 設(shè)設(shè) S=1,2,3,4,從從S中取中取3個元素的可重復(fù)組合個元素的可重復(fù)組合1234表示組合表示組合 (234)1234表示組合表示組合 (122)1234表示組合表示組合 (222)1234表示組合表示組合 (144)球與隔板共占有球與隔板共占有(4-1

25、)+3個位置個位置, 球和隔板的位置選擇代表可重復(fù)組合球和隔板的位置選擇代表可重復(fù)組合即從即從4+3-1個位置中選擇個位置中選擇3個位置放球，其余位置放隔板就可以得到一個個位置放球，其余位置放隔板就可以得到一個可重復(fù)組合可重復(fù)組合,所以總共有所以總共有 C(4+3-1,3)=C(6,3)=6!/(3!(6-3)!)=20 種可重復(fù)組合種可重復(fù)組合12.2 排列與組合排列與組合例例12.3 排列排列26 個字母個字母,使得使得a與與b之間恰有之間恰有7 個字母個字母,求方法數(shù)求方法數(shù). 解解 固定固定a和和b, 中間插入中間插入7 個字母個字母,有有 2 P(24,7) 種方法種方法, 將它看作

26、大字母與其余將它看作大字母與其余17 個全排列有個全排列有 18！種，共！種，共 N = 2 P(24,7) 18! 或者或者 從第從第1個位置至第個位置至第18個位置中選取一個位置個位置中選取一個位置,設(shè)為第設(shè)為第k個位個位 從從a,b中選取一個放在第中選取一個放在第k個位置上個位置上,另一個放在第另一個放在第k+8個位置上個位置上 將其余的將其余的24個字母排在剩余的個字母排在剩余的24個位置上個位置上 這樣得到的這樣得到的26個字母全排列數(shù)為個字母全排列數(shù)為 C(18,1)C(2,1)24!=2P(24,7)18!第第1個位置個位置第第26個位置個位置第第18個位置個位置第第k個位置個位

27、置第第k+8個位置個位置12.2 排列與組合排列與組合例例12.4 把把 2n 個人分成個人分成n 組組,每組每組2 人人,有多少分法？有多少分法？ 解解: 相當(dāng)于把相當(dāng)于把 2n個不同的球放到個不同的球放到 n 個相同的盒子個相同的盒子,每個盒子每個盒子2 個個, 放法為放法為 (將將2n個球排成一列個球排成一列,按順序依次各取按順序依次各取2個球放入每個盒子中個球放入每個盒子中,再消除次序再消除次序)例例12.5 下而給出一段簡單的程序下而給出一段簡單的程序,問它的輸出問它的輸出x是什么是什么? Algorithm 輸出結(jié)果為輸出結(jié)果為 C(n+k-1,k)1. x02. for i11

28、to n3. for i21 to i1 K+1. for ik to ik-1K+2. xx+1K+3. return x!2)!2(!) !2()!2(nnnnNnn例例: x=0; for(i=1;i=5;i+) for(j=1;j=i;j+) for(k=1;kn-k+1時無解時無解 當(dāng)當(dāng) kn-k+1時時,設(shè)設(shè)有有 n-k+1 個盒子如圖所示個盒子如圖所示 將將 k 個完全相同的球投入到盒子中個完全相同的球投入到盒子中,每個盒子最多投入一個球每個盒子最多投入一個球 則不同投球的結(jié)果可以得到從則不同投球的結(jié)果可以得到從S中取中取k個不相鄰數(shù)的不同方法。個不相鄰數(shù)的不同方法。 具體做法是

29、從左至右將具體做法是從左至右將k個球和個球和(n-k)個盒子中間隔板依次編號為個盒子中間隔板依次編號為 1,2,3,n 則則k個球所對應(yīng)的編號就是選擇個球所對應(yīng)的編號就是選擇k個不相鄰數(shù)的一種方法個不相鄰數(shù)的一種方法 而這樣的投球結(jié)果恰好有而這樣的投球結(jié)果恰好有 C(n-k+1,k) 種種 123n45n-1n-2n-k+1個盒子個盒子12.2 排列與組合排列與組合例例 設(shè)設(shè) S=1,2,3,4,5,6,7,8,9,從從S中取中取3個不相鄰的數(shù)個不相鄰的數(shù)表示選擇的表示選擇的3個數(shù)是個數(shù)是 1,3,7表示選擇的表示選擇的3個數(shù)是個數(shù)是 2,5,7表示選擇的表示選擇的3個數(shù)是個數(shù)是 3,5,9表

30、示選擇的表示選擇的3個數(shù)是個數(shù)是 2,5,8表示選擇的表示選擇的3個數(shù)是個數(shù)是 2,4,6從從S中選擇中選擇3個不相鄰的數(shù)的方法總數(shù)為個不相鄰的數(shù)的方法總數(shù)為 C(9-3+1,3)=3512.3 二項式定理與組合恒等式二項式定理與組合恒等式定理定理12.4 (二項式定理二項式定理),設(shè)設(shè)n是正整數(shù)是正整數(shù),對一切對一切x和和y推論推論 設(shè)設(shè)n是正整數(shù)是正整數(shù),則則nkknknyxknyx0)(nkknxknx0)1 (例例 (x+y)5=(x+y)(x+y)(x+y)(x+y)(x+y)=+C(5,3)x3y2+ 構(gòu)成構(gòu)成x3y2的項必須是從的項必須是從5個個(x+y)中選中選3個提供個提供x

31、,其他其他5-3個提供個提供y 因此因此,x3y2的系數(shù)是的系數(shù)是C(5,3)12.3 二項式定理與組合恒等式二項式定理與組合恒等式主要恒等式主要恒等式knNknknnkn,. 1knZknknknkn,11. 2knZknknknkn,111. 3Nnknnnk2. 40Nnknnkk0) 1(. 50Nknknklnl,11. 60Nkrnkrnkrknknkrrn,. 7),min(,. 80nmrNrnmrnmkrnkmrkNnmmnmknkmnk,. 9012.3 二項式定理與組合恒等式二項式定理與組合恒等式例例12.7 證明以下組合恒等式證明以下組合恒等式 證證 (1) 由二項式定

32、理有由二項式定理有 兩邊求導(dǎo)數(shù)得兩邊求導(dǎo)數(shù)得 令令x=1即可得原等式即可得原等式 (2) Znnknknnk,2) 1 (10nkknxknx0)1 (nkknkxknxn011)1 (Znnnknknnk,2) 1()2(202nknknknkknknknknknknkknk00020211 1) 1(1111 nknknknkknnknknknnknkn110001111111) 1(2122) 1(22) 1(nnnnnnnn12.3 二項式定理與組合恒等式二項式定理與組合恒等式非降路徑問題非降路徑問題: 設(shè)設(shè)m,n是正整數(shù)是正整數(shù),從從(0,0)點到點到(m,n)點的非降路徑是點的非降

33、路徑是 一條折線一條折線,這條折線由這條折線由m+n次移動構(gòu)成次移動構(gòu)成,每次允許向上每次允許向上 或者向右移動一步或者向右移動一步. 問不同的非降路徑有多少條問不同的非降路徑有多少條? 解解 不同的路徑取決于不同的路徑取決于m+n步的選擇步的選擇 其中包含其中包含m步向右步向右,n步向上。步向上。 這種路徑的條數(shù)等于從這種路徑的條數(shù)等于從m+n個個 位置中選位置中選m個位置的方法數(shù)。個位置的方法數(shù)。 即即 C(m+n,m) 或或 C(m+n,n)例例 某城市某城市7條南北走向的街道條南北走向的街道, 6條東西走向的街道。問從西南角到東北角的最短路有幾條條東西走向的街道。問從西南角到東北角的最

34、短路有幾條? 解解 記東西走向的路段為記東西走向的路段為x,南北走向的路段為南北走向的路段為y, 則每條最短路由則每條最短路由6個個x和和5個個y組成組成. x,y的不同排列構(gòu)成不同的最短路的不同排列構(gòu)成不同的最短路 所以共有所以共有 11!/(5!6!)=C(11,5)條最短路條最短路(0,0)(m,n)12.3 二項式定理與組合恒等式二項式定理與組合恒等式給定非負(fù)整數(shù)給定非負(fù)整數(shù)a,b,m,n,其中其中am,bn. 從從(a,b)點到點到(m,n)點的非降路徑數(shù)等于點的非降路徑數(shù)等于 從從(0,0)點到點到(m-a,n-b)點的非降路徑數(shù)點的非降路徑數(shù), 即即 C(m-a+n-b,m-a)

35、設(shè)設(shè)a,b,c,d,m,n是非負(fù)整數(shù)是非負(fù)整數(shù),其中其中acm,bdn. 從從(a,b)點經(jīng)過點經(jīng)過(c,d)點到點到(m,n)點的非降路徑數(shù)點的非降路徑數(shù) = 從從(a,b)點到點到(c,d)點的非降路徑數(shù)點的非降路徑數(shù) 從從(c,d)點到點到(m,n)點的非降路徑數(shù)點的非降路徑數(shù)(a,b)(m,n)(0,0)(c,d)12.3 二項式定理與組合恒等式二項式定理與組合恒等式例例12.8 求集合求集合1,2,n上的單調(diào)遞增函數(shù)的個數(shù)上的單調(diào)遞增函數(shù)的個數(shù) 解解 將自變量看作橫坐標(biāo)將自變量看作橫坐標(biāo),對應(yīng)的函數(shù)值看作縱坐標(biāo)對應(yīng)的函數(shù)值看作縱坐標(biāo),得到得到n個點個點, 再增加兩個點再增加兩個點(1

36、,1)和和(n+1,n),共有共有n+2個點個點(如果如果f(1)1) (1,1) , (1,f(1) , (2,f(2) , (n,f(n) , (n+1,n) 如果如果 f(1)1,那么從那么從 (1,1) 直接向上連接到直接向上連接到 (1,f(1) 每個點都按先向右每個點都按先向右,后向上的規(guī)則連接到下一個點后向上的規(guī)則連接到下一個點, 這樣得到一條從這樣得到一條從 (1,1) 到到 (n+1,n) 的非降路徑的非降路徑. 這種非降路徑和集合這種非降路徑和集合 1,2,n上單調(diào)遞增函數(shù)是一一對應(yīng)的上單調(diào)遞增函數(shù)是一一對應(yīng)的 根據(jù)公式根據(jù)公式,集合集合1,2,n上單調(diào)遞增函數(shù)個數(shù)是上單調(diào)

37、遞增函數(shù)個數(shù)是 C(2n-1,n)例例 設(shè)設(shè)A=1,2,3,4 , 如右圖所示如右圖所示 黑線表示的非降路徑對應(yīng)黑線表示的非降路徑對應(yīng)A上的遞增函數(shù)上的遞增函數(shù) f(1)=1,f(2)=1,f(3)=2,f(4)=2 紅線表示的非降路徑對應(yīng)紅線表示的非降路徑對應(yīng)A上的遞增函數(shù)上的遞增函數(shù) f(1)=2,f(2)=3,f(3)=3,f(4)=4(1,1)(5,4)(0,0)12.3 二項式定理與組合恒等式二項式定理與組合恒等式例例12.9 棧棧(后進(jìn)先出棧后進(jìn)先出棧)的輸出計數(shù)問題的輸出計數(shù)問題 解解 將進(jìn)棧、出棧分別記作將進(jìn)棧、出棧分別記作x,y,一個輸出對應(yīng)了一個輸出對應(yīng)了n個個x,n個個y的排列的排列, 且排列的任何前綴中的且排列的任何前綴中的x個數(shù)不少于個數(shù)不少于y的個數(shù)的個數(shù).將排列中的將排列中的x看作向右看作向右 走一步走一步,y看作向上走一步看作向上走一步,這樣一個排列就對應(yīng)了一條從這樣一個排列就對應(yīng)了一條從(0,0)點到點到 (n,n)點的非降路徑點的非降路徑,且不穿過對角線。且不穿過對角線。 如右圖所示如右圖所示,任何一條從任何一條從(0,0)到到(n,n)穿過對角線的路徑一定要穿過