離散容斥原理與排列組合

離散容斥原理與排列組合演示文稿現(xiàn)在是1頁\一共有41頁\編輯于星期日（優(yōu)選）離散容斥原理與排列組合現(xiàn)在是2頁\一共有41頁\編輯于星期日PowerPointTemplate_Sub1計(jì)數(shù)基本原理2排列與組合3重集的排列與組合第3章組合論基礎(chǔ)計(jì)數(shù)4遞歸關(guān)系3第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是3頁\一共有41頁\編輯于星期日計(jì)數(shù)基本原理與排列組合TextbookPage30to36《離散數(shù)學(xué)》第5講現(xiàn)在是4頁\一共有41頁\編輯于星期日內(nèi)容提要6.1計(jì)數(shù)基本原理加法原理、乘法原理包含排斥原理（容斥原理）6.2排列與組合線排列、圓排列、組合在回顧中學(xué)知識(shí)的基礎(chǔ)上適度提高5第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是5頁\一共有41頁\編輯于星期日加法原理與乘法原理加法原理分類計(jì)數(shù)：完成一件事有n類辦法，在第1類辦法中有a1

種不同的方式，…，在第n類辦法中有an

種不同的方式，那么完成這件事共有a1+…+an種不同的方式若有限集合S=S1∪S2∪…∪Sn，且S1,S2,…,Sn兩兩不相交，那么|S|=|S1|+|S2|+…+|Sn|乘法原理分步計(jì)數(shù)：完成一個(gè)任務(wù)需要分成ｎ個(gè)步驟，做第1步有a1種不同的方式，…，做第ｎ步有an種不同的方式，那么完成整個(gè)任務(wù)共有a1×a2×…×an種方式對(duì)有限集合S1,S2,…,Sn，|S1×S2×

…×Sn|=|S1|×|S2|×…×|Sn|6第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是6頁\一共有41頁\編輯于星期日應(yīng)用例1(例3.2)一家服裝廠用4種式樣，5種顏色，8種尺寸生產(chǎn)男式服裝；用6種式樣，5種顏色，6種尺寸生產(chǎn)女式服裝，問這家服裝廠共計(jì)生產(chǎn)男女服裝多少種？解：男式服裝種類：4×5×8=160（種）

女式服裝種類：6×5×6=180（種）

共計(jì)：160+180=340（種）加法原理乘法原理乘法原理7第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是7頁\一共有41頁\編輯于星期日應(yīng)用例2(例3.1)從上海直達(dá)天津可以乘坐汽車、火車和飛機(jī)旅行，已知汽車有3個(gè)班次，火車有4個(gè)班次，飛機(jī)有2個(gè)班次。從天津直達(dá)大連可以乘坐輪船和飛機(jī)旅行，已知輪船有2個(gè)班次，飛機(jī)有3個(gè)班次。問從上海經(jīng)天津到大連有多少種旅行安排？解：從上海到天津有3+4+2=9種旅行安排從天津到大連有2+3=5種旅行安排

從上海經(jīng)天津到大連共有9×5=45種旅行安排乘法原理加法原理加法原理8第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是8頁\一共有41頁\編輯于星期日加法原理與乘法原理注意點(diǎn)都是把一個(gè)事件分解成若干個(gè)分事件來完成加法原理（分類計(jì)數(shù)原理）如果分事件相互獨(dú)立，分類完備，就用分類計(jì)數(shù)原理注意：分類時(shí)要做到不重不漏乘法原理（分步計(jì)數(shù)原理）如果分事件相互關(guān)聯(lián)，缺一不可，就用分步計(jì)數(shù)原理注意：分步時(shí)做到不缺經(jīng)常結(jié)合使用9第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是9頁\一共有41頁\編輯于星期日相交集合的計(jì)數(shù)加法原理中，S1,S2,…,Sn兩兩不相交，|S|=|S1|+|S2|+…+|Sn|若取消兩兩不相交的限制，該如何計(jì)算？考慮兩個(gè)集合的情況AB10第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是10頁\一共有41頁\編輯于星期日AB相交集合的計(jì)數(shù)加法原理中，S1,S2,…,Sn兩兩不相交，|S|=|S1|+|S2|+…+|Sn|若取消兩兩不相交的限制，該如何計(jì)算？考慮兩個(gè)集合的情況|A|+|B|112－

|A∩B|11第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是11頁\一共有41頁\編輯于星期日AB相交集合的計(jì)數(shù)加法原理中，S1,S2,…,Sn兩兩不相交，|S|=|S1|+|S2|+…+|Sn|若取消兩兩不相交的限制，該如何計(jì)算？考慮兩個(gè)集合的情況|A|+|B|－

|A∩B|111|A∪B|=|A|+|B|－

|A∩B|12第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是12頁\一共有41頁\編輯于星期日三個(gè)相交集合的計(jì)數(shù)三個(gè)集合的情況ABC|A|+|B|+|C|13第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是13頁\一共有41頁\編輯于星期日三個(gè)相交集合的計(jì)數(shù)三個(gè)集合的情況ABC|A|+|B|+|C|1112223－|A∩B|－

|A∩C|－

|B∩C|14第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是14頁\一共有41頁\編輯于星期日三個(gè)相交集合的計(jì)數(shù)三個(gè)集合的情況|A|+|B|+|C|－|A∩B|－

|A∩C|－

|B∩C|+|A∩B∩C|ABC1111113015第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是15頁\一共有41頁\編輯于星期日三個(gè)相交集合的計(jì)數(shù)三個(gè)集合的情況|AUBUC

|=|A|+|B|+|C|－|A∩B|－|A∩C|－|B∩C|+|A∩B∩C||A|+|B|+|C|－|A∩B|－

|A∩C|－

|B∩C|+|A∩B∩C|ABC111111116第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是16頁\一共有41頁\編輯于星期日n個(gè)相交集合的計(jì)數(shù)定理3.2考慮集合S1,S2,…,Sn,S=S1∪S2∪…∪Sn

，那么|S|=|S1∪S2∪…∪Sn|驗(yàn)證：n=1n=2n=317第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是17頁\一共有41頁\編輯于星期日定理3.2的證明用數(shù)學(xué)歸納法證明|S1∪S2∪…∪Sn|對(duì)n進(jìn)行歸納基礎(chǔ)步：n=1,2時(shí)，根據(jù)上面的驗(yàn)證，等式成立；歸納步：假設(shè)n=k(k≥1)時(shí)等式成立，則n=k+1時(shí)…………等式依然成立綜上，對(duì)任意自然數(shù)n≥1，均有等式成立

課后自己看書18第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是18頁\一共有41頁\編輯于星期日另一種證明思路從集合|S1∪S2∪…∪Sn|中每個(gè)元素被計(jì)數(shù)的次數(shù)來考慮設(shè)元素aS1∪S2∪…∪Sn

，它恰在Sa1,Sa2,…,Sar中出現(xiàn)(1≤a1<a2<…<ar≤n)則元素a被因?yàn)樗栽豠恰被計(jì)數(shù)1次計(jì)數(shù)了

次計(jì)數(shù)了

次計(jì)數(shù)了

次計(jì)數(shù)了

次……19第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是19頁\一共有41頁\編輯于星期日應(yīng)用(例3.3)試計(jì)算在集合{1，2，3，…，1000}中有多少元素至少能被5，6，8這三個(gè)數(shù)中的一個(gè)整除。解.用A、B、C分別表示1000以內(nèi)能被5、6、8整除的正整數(shù)集合，題意為求|A∪B∪C|

∵一個(gè)數(shù)能被若干個(gè)數(shù)同時(shí)整除當(dāng)且僅當(dāng)這個(gè)數(shù)能被它們的最小公倍數(shù)整除

∴|A∩B|==33|A∩C|==25|B∩C|==41|A∩B∩C|==8∴|A∪B∪C|=|A|+|B|+|C|?|A∩B|?|A∩C|?|B∩C|+|A∩B∩C|=400（個(gè)）|A|==200|B|==166|C|==12520第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是20頁\一共有41頁\編輯于星期日應(yīng)用學(xué)校1807個(gè)新生中有453人選了計(jì)算機(jī)科學(xué)課，567人選了數(shù)學(xué)課，299人同時(shí)選了計(jì)算機(jī)科學(xué)課和數(shù)學(xué)課。問有多少學(xué)生既沒選計(jì)算機(jī)科學(xué)課又沒選數(shù)學(xué)課？用S表示全體新生，用A、B分別表示選了計(jì)算機(jī)科學(xué)課和數(shù)學(xué)課的新生集合。AS，BS?？砂裇看作全集。Aˉ為沒選計(jì)算機(jī)科學(xué)課的新生集合，Bˉ為沒選數(shù)學(xué)課的新生集合，目標(biāo)是求|Aˉ∩Bˉ|∵Aˉ∩Bˉ=S－(A∪B)∴|Aˉ∩Bˉ|=|S－(A∪B)|=|S|－|A∪B|=|S|－(|A|+|B|－|A∩B|)=1807–(453+567–299)

=1086因此，共有1086人既沒選計(jì)算機(jī)科學(xué)課又沒選數(shù)學(xué)課21第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是21頁\一共有41頁\編輯于星期日容斥原理容斥原理(定理3.4)用S1,S2,…,Sn分別表示集合S中具有性質(zhì)P1,P2,…,Pn元素集合，則S中同時(shí)不具有這些性質(zhì)的元素個(gè)數(shù)為

|S1ˉ∩S2ˉ∩…∩Snˉ|

22第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是22頁\一共有41頁\編輯于星期日應(yīng)用例3.3（2）試計(jì)算在集合{1，2，3，…，1000}中有多少元素不能被5，6，8這三個(gè)數(shù)中的一個(gè)整除。解.用A、B、C分別表示1000以內(nèi)不能被5、6、8整除的正整數(shù)集合，題意為求|Aˉ∩Bˉ∩Cˉ|

∵一個(gè)數(shù)能被若干個(gè)數(shù)同時(shí)整除當(dāng)且僅當(dāng)這個(gè)數(shù)能被它們的最小公倍數(shù)整除

∴|A∩B|==33|A∩C|==25|B∩C|==41|A∩B∩C|==8∴|Aˉ∩Bˉ∩Cˉ|=1000-|A|-|B|-|C|+|A∩B|+|A∩C|+|B∩C|-|A∩B∩C|=1000–400=600（個(gè)）|A|==200|B|==166|C|==12523第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是23頁\一共有41頁\編輯于星期日應(yīng)用已知：密鑰是長度為L的0，1序列，為安全起見，須對(duì)密鑰進(jìn)行變換。變換方式是：對(duì)于被p整除和被q整除的各位改變其奇偶性。問：作此改變后，最終未改變奇偶性的有多少位？為了使未改變奇偶性的位盡可能地少，p,q應(yīng)滿足什么性質(zhì)？

L=50，p=4，q=6用S表示密鑰各位的集合（全集），用A、B分別表示被4整除和被6整除的各位組成的集合一次未改的密鑰位集合為Aˉ∩Bˉ；改變兩次，最終與原奇偶性相同的密鑰位集合為A∩B

∵根據(jù)容斥原理，|Aˉ∩Bˉ|+|A∩B|=|S|?|A|?|B|+|A∩B|+|A∩B|∴最終有38個(gè)密鑰位未改變奇偶性=3824第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是24頁\一共有41頁\編輯于星期日應(yīng)用已知：密鑰是長度為L的0，1序列，為安全起見，須對(duì)密鑰進(jìn)行變換。變換方式是：對(duì)于被p整除和被q整除的各位改變其奇偶性。問：作此改變后，最終未改變奇偶性的有多少位？為了使未改變奇偶性的位盡可能地少，p,q應(yīng)滿足什么性質(zhì)？1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950為使未改變奇偶性的位盡可能地少，p,q應(yīng)互質(zhì)25第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是25頁\一共有41頁\編輯于星期日應(yīng)用一次會(huì)議有2005位數(shù)學(xué)家參加，每人至少有1337位合作者，求證：可以找到4位數(shù)學(xué)家，他們中每兩人都合作過。記數(shù)學(xué)家們?yōu)閍，b，…，與其合作過的數(shù)學(xué)家集合分別記作A，B,…。任取一數(shù)學(xué)家a，并取bA（a與b合作過）∵|A|≥1337，|B|≥1337，|A∪B|≤2005∴|A∩B|=|A|+|B|－|A∪B|≥1337×2－2005＞0取cA∩B（c與a、b均合作過）因?yàn)閨A∩B∩C|=|A∩B|+|C|－|(A∩B)∪C|≥(1337×2－2005)+1337－2005=1因而存在數(shù)學(xué)家dA∩B∩C，d與a、b、c均合作過找到四位數(shù)學(xué)家a、b、c、d，他們兩兩合作過

26第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是26頁\一共有41頁\編輯于星期日線排列的計(jì)數(shù)定義3.1：用Pnr或P(n,r)表示“從n個(gè)不同元素的集合中每次取出r個(gè)元素進(jìn)行有序排列時(shí)可得到的排列的總數(shù)”。Pnr或P(n,r)簡稱為r-排列數(shù)，P(n,n)簡稱為n-全排列數(shù)定理3.5：對(duì)任意正整數(shù)n,r,r≤n,r-排列數(shù)是特別地，Pn1=n，Pnn=n！27第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是27頁\一共有41頁\編輯于星期日排列組合求解方法例1：班里照相，12人站一排。8個(gè)男學(xué)員，4個(gè)女學(xué)員，要求女學(xué)員要排在一起，共有多少種不同的排法？將4個(gè)女學(xué)員看成是一個(gè)人,與8個(gè)男學(xué)員作全排列，共P(9,9)種，4個(gè)女學(xué)員內(nèi)部排列方式有P(4,4)種，所以共P(9,9)·P(4,4)種捆綁法：要求某幾個(gè)元素必須排在一起的問題,可以用捆綁法來解決。即將需要相鄰的元素合并為一個(gè)元素,再與其它元素一起作排列，同時(shí)要注意合并元素內(nèi)部也可以作排列。28第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是28頁\一共有41頁\編輯于星期日排列組合求解方法例2：班里照相，12人站一排。8個(gè)男學(xué)員，4個(gè)女學(xué)員，要求女學(xué)員在男學(xué)員中間，且女學(xué)員互不相鄰，共有多少種不同的排法？先排男學(xué)員共有P(8,8)種排法。然后把女學(xué)員插入男學(xué)員之間的空檔，共有7個(gè)空檔可插，選其中的4個(gè)空檔,共有P(7,4)種選法。根據(jù)乘法原理，共有不同排法P(8,8)·P(7,4)種。插空法：對(duì)于某兩個(gè)元素或者幾個(gè)元素要求不相鄰的問題,可以用插空法。即先排好沒有限制條件的元素,然后將有限制條件的元素按要求插到排好元素的空檔之中即可。29第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是29頁\一共有41頁\編輯于星期日排列組合求解方法例3：期末安排考試科目7門，英語要在離散數(shù)學(xué)之前考,有多少種不同的安排順序?不加任何限制條件，整個(gè)排法有P(7,7)種?！坝⒄Z安排在離散數(shù)學(xué)之前考”

與“離散數(shù)學(xué)安排在英語之前考”的排法是相等的，所以英語安排在離散數(shù)學(xué)之前考的排法共有P(7,7)/2種。對(duì)等法：在有些題目中，限制條件的肯定與否定是對(duì)等的，各占全體的二分之一。在求解中只要求出全體,就可以得到所求。30第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是30頁\一共有41頁\編輯于星期日例3.4有多少個(gè)大于5400，又同時(shí)滿足下列兩個(gè)性質(zhì)的整數(shù)：（1）各位數(shù)字均不相同；（2）不出現(xiàn)數(shù)字2和7解：不能出現(xiàn)數(shù)字2和7，且各位數(shù)字均不相同，所以只能是四、五、六、七、八位數(shù)1)對(duì)五、六、七、八位數(shù)來說，第一位只能從1、3、4、5、6、8、9中選取，即共有7種可能，其他各位可從剩余的7個(gè)數(shù)字中選擇進(jìn)行排列，共有P(7,i)種（i=4,5,6,7）所以：五、六、七、八位數(shù)共有7P(7,4)+7P(7,5)+7P(7,6)+7P(7,7)=

94080

個(gè)滿足條件。2)對(duì)于四位數(shù)來說，2.1)若第一位大于5（共有3種可能），則其余3位可從剩余的7個(gè)數(shù)字選取3個(gè)排列，即共有3*P(7,3)=630個(gè)。2.2)若第一位為5，則第二位只能從4、6、8、9種選擇，其余2位可從剩余的6個(gè)數(shù)字選取2個(gè)排列，即共有1*4*P(6,2)=120個(gè)。綜上，根據(jù)加法原理，共有94080+630+120=94830個(gè)31第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是31頁\一共有41頁\編輯于星期日?qǐng)A排列的計(jì)數(shù)定義(圓排列)：從n個(gè)不同元素的集合中每次取出r個(gè)元素，圍繞一個(gè)圓周進(jìn)行有序排列的排列總數(shù)（可旋轉(zhuǎn)，但不可翻轉(zhuǎn)）對(duì)于圓排列(1,2,3,4,5)12345(1,2,3,4,5)(2,3,4,5,1)(3,4,5,1,2)(4,5,1,2,3)(5,1,2,3,4)一個(gè)圓排列對(duì)應(yīng)r個(gè)線排列線排列數(shù)是圓排列數(shù)的r倍32第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是32頁\一共有41頁\編輯于星期日?qǐng)A排列的計(jì)數(shù)定理3.6：對(duì)任意正整數(shù)n,r,r≤n,從n個(gè)不同元素的集合中每次取出r個(gè)元素，圍繞一個(gè)圓周進(jìn)行有序排列時(shí)可得到的排列的總數(shù)是：33第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是33頁\一共有41頁\編輯于星期日例3.5六位女士和六位先生圍著一張圓桌聚餐，要求安排女士和先生交替就座。問有多少可能的安排方案？解：可分為兩個(gè)步驟來分配座位：先安排女士就座，兩人之間留一個(gè)空位，然后再安排先生就座。安排女士就座的方案共有 種（圓排列）安排好女士后，再安排先生就座時(shí)，是線排列而非圓排列問題，因?yàn)榇藭r(shí)已經(jīng)有了女士作參照，相同的圓排列與女士圓排列對(duì)齊方式不同將導(dǎo)致不同的就座方案。因此，對(duì)每一種女士就座方式，可有P(6,6)=720種男士就座方式。根據(jù)乘法原理，共有120720=86400種就座方案。34第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是34頁\一共有41頁\編輯于星期日例五對(duì)夫婦圍著一張圓桌聚餐，試問每對(duì)夫妻相鄰而坐的方式有多少種？解：分為兩步：第一步先安排五對(duì)夫婦的位置，第二步再具體安排每對(duì)夫妻兩人的相對(duì)位置。第一步共有圓排列 種；第二步每對(duì)夫妻都有兩種相對(duì)坐法，因此共有25=32種坐法（乘法原理）。根據(jù)乘法原理，共有2432=768種就座方式。35第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是35頁\一共有41頁\編輯于星期日例A、B、C、D、E、F六人圍圓桌而坐，若A、B、C三人相鄰，共有多少種坐法？解：第一步將A、B、C看成一個(gè)整體，將其與D、E、F一起分配座位，共有 就座方式；第二步規(guī)定A、B、C的座位，此時(shí)為線排列問題，共有P(3,3)=6種安排方式。根據(jù)乘法原理，一共有66=36種坐法。36第5講計(jì)數(shù)基本原理與排列組合現(xiàn)在是36頁\一共有41頁\編輯于星期日組合的計(jì)數(shù)定義3.2：用Cnr或C(n,r)表示“從n個(gè)元素的集合中每次取出r個(gè)元素（不進(jìn)行有序排列）組成子集合的總數(shù)”。Cnr或C(n,r)簡稱為r-組合數(shù)定理3.7：

對(duì)任意正整數(shù)n,r,r≤n,r-組合數(shù)是：