組合數(shù)學(xué)-第二章-容斥原理_第1頁
組合數(shù)學(xué)-第二章-容斥原理_第2頁
組合數(shù)學(xué)-第二章-容斥原理_第3頁
組合數(shù)學(xué)-第二章-容斥原理_第4頁
組合數(shù)學(xué)-第二章-容斥原理_第5頁
已閱讀5頁,還剩16頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、第二章容斥原理 本章重點(diǎn)介紹容斥原理及其在排列組合中的應(yīng)用: 容斥原理 容斥原理的應(yīng)用 有限制排列與棋盤多項(xiàng)式2.1 基本技術(shù)定律2.1 容斥原理2.1.1 引論 SA SAB 容斥原理(包含排除原理)通過研究若干有限集合的交與并等基本運(yùn)算,解決實(shí)際中的計(jì)數(shù)問題。主要依據(jù): 若A為S 的子集,則 , 。 De Morgan定律:若A、B為S的子集,則 注:De Morgan定律可推廣到n個(gè)有限子集。2.1 容斥原理定理1-12.1 容斥原理2.1.2 計(jì)數(shù)定理定理 2.1可用Venn圖說明該定理的正確性?;蛲ㄟ^組合分析法,若A代表具有性質(zhì)a的元素集合,B代表具有性質(zhì)b的元素集合,等式左端表示至

2、少具有性質(zhì)a、b之一的元素個(gè)數(shù),|A|表示具有性質(zhì)a的元素個(gè)數(shù),|B|表示具有性質(zhì)b的元素個(gè)數(shù),但二者相加時(shí),同時(shí)具有性質(zhì)a、b的元素計(jì)數(shù)重復(fù)加了一次,故需要減去重復(fù)的數(shù)|AB|。注:加法法則相當(dāng)于該等式AB=的一個(gè)特例。2.1 容斥原理定理1-22.1 容斥原理2.1.2 計(jì)數(shù)定理定理 2.1同樣可用Venn圖說明該定理的正確性。該等式表示同時(shí)不具有性質(zhì)a、b的元素個(gè)數(shù)的計(jì)數(shù)方法。同時(shí)不具有性質(zhì)a、b的元素個(gè)數(shù)應(yīng)該在全集S中去掉|A|和|B|,但此時(shí)同時(shí)具有性質(zhì)a、b的元素計(jì)數(shù)重復(fù)減了一次,故需要加上重復(fù)的數(shù)|AB|。2.1 容斥原理定理22.1 容斥原理2.1.2 計(jì)數(shù)定理定理 2.22.

3、1 容斥原理例12.1 容斥原理2.1.2 計(jì)數(shù)定理例 題例1、一個(gè)學(xué)校只有三門課程:數(shù)學(xué)、物理、化學(xué)。已知修這三門科的學(xué)生分別有170、130、120人;同時(shí)修數(shù)學(xué)物理兩門課的學(xué)生有45人;同時(shí)修數(shù)學(xué)、化學(xué)的20人;同時(shí)修物理、化學(xué)的22人;同時(shí)修三門科的學(xué)生3人。問這學(xué)校有多少學(xué)生?解:令M為修數(shù)學(xué)課的學(xué)生集合,P為修物理課的學(xué)生集合,C為修化學(xué)課的學(xué)生集合。據(jù)題意有|M|=170,|P|=120,|C|=130,|MP|=45,|PC|=22,|CM|=20,|MPC|=3 , 則該學(xué)校的學(xué)生數(shù)為|MPC|=|M|+|P|+|C|-|MP|-|PC|-|CM|+|MPC|=3362.1

4、容斥原理定理32.1 容斥原理2.1.3 容斥原理定理 2.3若Ai (i=1,2,n) S,且Ai是S中具有性質(zhì)pi的元素的子集,則S中不具有性質(zhì)pi (i=1,2,n)的元素的個(gè)數(shù)為:證明:可以利用數(shù)學(xué)歸納法證明?;蛴媒M合分析方法如下:為證明等式成立,只需證明等式右端不具有性質(zhì)pi (i=1,2,n)的元素被計(jì)算的次數(shù)凈值為1,而至少具有性質(zhì)pi 中之一的元素被計(jì)算的次數(shù)凈值為0即可??紤]S中一個(gè)不具有n個(gè)性質(zhì)中任何一個(gè)性質(zhì)的元素x,因?yàn)閤Ai(i=1,2,n),故x被計(jì)算的次數(shù)凈值為1-0+0-(-1)n *0=1??紤]S中一個(gè)恰好具有n個(gè)性質(zhì)中的m(1mn)個(gè)性質(zhì)的一個(gè)元素y,由于yS

5、 ,故在S中被計(jì)算的次數(shù)為C(m,0);又由于y恰好具有m個(gè)性質(zhì),故它是Ai(i=1,2,n)中的m個(gè)集合的元素,因而在 中被計(jì)算的次數(shù)為C(m,1) ;又因?yàn)樵趍個(gè)性質(zhì)中取出一對性質(zhì)的方法有C(m,2)個(gè),故y是C(m,2)個(gè)集合AiAj(ij)的一個(gè)元素,在 中被計(jì)算的次數(shù)為C(m,2),因此y在等式右端被計(jì)算的次數(shù)凈值C(m,0)-C(m,1)+C(m,2)+(-1)nC(m,n),由于mk時(shí),C(m,k)=0,有C(m,0)-C(m,1)+C(m,2)+(-1)nC(m,n)= C(m,0)-C(m,1)+C(m,2)+(-1)mC(m,m)=0。因此y具有n個(gè)性質(zhì)中至少一個(gè)性質(zhì)時(shí),被

6、計(jì)算的次數(shù)凈值為0。 定理得證。2.1 容斥原理定理42.1 容斥原理2.1.3 容斥原理定理 2.4若Ai (i=1,2,n) S,且Ai是S中具有性質(zhì)pi的元素的子集,則S中至少具有性質(zhì)pi (i=1,2,n)的一個(gè)性質(zhì)的元素個(gè)數(shù)為:證明:由于集合 是S中至少具有n個(gè)性質(zhì)中一個(gè)性質(zhì)元素所組成的子集,所以有代入上述定理,即可得證。2.1 容斥原理例22.1 容斥原理2.1.3 容斥原理例 題例2、求a,b,c,d,e,f六個(gè)字母的全排列中不允許出現(xiàn)ace和df圖像的排列數(shù)。解:令S為這六個(gè)字母的全排列集合,A為ace作為一個(gè)元素出現(xiàn)的排列集合,B為df作為一個(gè)元素出現(xiàn)的排列集合。根據(jù)題意有|

7、S|=6!,|A|=4!,|B|=5!,|AB|=3!,根據(jù)容斥原理,不允許出現(xiàn)ace和df的排列數(shù)為2.1 容斥原理例32.1 容斥原理2.1.3 容斥原理例 題例3、求從1到500的整數(shù)中被3或5除盡的數(shù)的個(gè)數(shù)。解:令A(yù)為1500中能被3除盡的整數(shù)集合,B為1500中能被5除盡的整數(shù)集合。根據(jù)題意有根據(jù)容斥原理,從1到500的整數(shù)中被3或5除盡的數(shù)的個(gè)數(shù)為2.1 容斥原理例42.1 容斥原理2.1.3 容斥原理例 題例4、求有a,b,c,d四個(gè)字符構(gòu)成的n位符號(hào)串中,a,b,c至少出現(xiàn)一次的符號(hào)串的數(shù)目。解:令S為四個(gè)字符的所有n位符號(hào)串集合,A,B,C分別為n位符號(hào)串中不出現(xiàn)a,b,c的

8、集合。根據(jù)題意有根據(jù)容斥原理, a,b,c至少出現(xiàn)一次的符號(hào)串?dāng)?shù)目為2.1 容斥原理例52.1 容斥原理2.1.3 容斥原理例 題例5、求不超過120的素?cái)?shù)個(gè)數(shù)。解:設(shè)S=1,2,120,因?yàn)?02120112,故120以內(nèi)的合數(shù)必然是2,3,5,7的倍數(shù),令A(yù)i為120以內(nèi)數(shù)i的倍數(shù)集,i=2,3,5,7,有根據(jù)容斥原理,有但該計(jì)算過程排除了素?cái)?shù)2,3,5,7,又包含1這個(gè)非合數(shù),故所求120以內(nèi)的素?cái)?shù)數(shù)目為27+4-1=302.1 容斥原理例62.1 容斥原理2.1.3 容斥原理例 題例6、用26個(gè)英文字母做不允許重復(fù)的全排列,要求排除dog, god, gum, depth, thing

9、字樣的出現(xiàn),求滿足這些條件的排列數(shù)。解:設(shè)S為26個(gè)字母的全排列集,令A(yù)i分別為出現(xiàn)dog, god, gum,depth, thing的排列集,i=1,2,3,4,5。出現(xiàn)dog的排列,可把dog作為一個(gè)元素看,|A1|=24!,同理|A2|=|A3|=24!,|A4|=|A5|= 22!。因dog, god不可能同時(shí)出現(xiàn),故|A1A2|=0,同理|A2A3|=|A1A4|= |A1A5|= 0,gum, dog可以在dogum中同時(shí)出現(xiàn),故|A3A1|=22!,同理|A2A4|=|A3A4|=|A5A2|=|A5A3|=20!, |A4A5|=19!。同理|A1A2A3|=|A1A2A4|

10、=|A1A2A5| =|A2A3A4|=|A2A3A5|=|A1A4A5|=|A1A3A4|=|A1A3A5|=|A2A4A5|= 0,|A3A4A5|=17!,其他4個(gè)、5個(gè)子集的交集均為空集。根據(jù)容斥原理,所求的排列數(shù)為26!-324!-22!+420!+19!-17!2.1 容斥原理例72.1 容斥原理2.1.3 容斥原理例 題例7、歐拉函數(shù)(n)是求小于n且與n互素的自然數(shù)的個(gè)數(shù)。 (nN)求歐拉函數(shù)表達(dá)式。解:對任一大于1的正整數(shù)n都可惟一地分解為其中p1p2pk都是不超過n的素?cái)?shù),且1,2,k都是正整數(shù)。設(shè)S=1,2, n, Ai為S中能被pk整除的子集,i=1,2,k。顯然有|S

11、|=n, |Ai|=n/pi, (i=1,2,k), |AiAj|=n/(pi pj), (i,j=1,2,k; ij),|A1A2 Ak|=n/(p1p2pk),根據(jù)容斥原理,有2.1 容斥原理例82.1 容斥原理2.1.3 容斥原理例 題例8、某校甲班共有學(xué)生60名,其中24個(gè)學(xué)生喜愛數(shù)學(xué),28個(gè)學(xué)生喜愛物理,26個(gè)學(xué)生喜愛化學(xué),10個(gè)學(xué)生既喜愛數(shù)學(xué)又喜愛物理,8個(gè)學(xué)生既喜愛數(shù)學(xué)又喜愛化學(xué),14個(gè)學(xué)生既喜愛物理又喜愛化學(xué),6個(gè)學(xué)生對這三門學(xué)科都喜愛,問有多少學(xué)生對這三門學(xué)科都不喜愛?解:設(shè)S為60名學(xué)生的集合,令M為喜歡數(shù)學(xué)課的學(xué)生集合,P為喜歡物理課的學(xué)生集合,C為喜歡化學(xué)課的學(xué)生集合。

12、根據(jù)題意有|S|=60,|M|=24,|P|=28,|C|=26,|MP|=10,|PC|=14, |CM|=8, |MPC |=6 ,根據(jù)容斥原理,則該班級三門學(xué)科都不喜歡的學(xué)生數(shù)為|S|-(|M|+|P|+|C|)+(|MP|+|PC|+|CM|)-|MPC |=82.1 容斥原理例92.1 容斥原理2.1.3 容斥原理例 題例9、求從1到1000的整數(shù)中不能被5,6和8中任何一個(gè)整除的整數(shù)個(gè)數(shù)。解:用lcma1,a2,an表示n個(gè)整數(shù)a1,a2,an的最小公倍數(shù)。設(shè)S=1,2,1000,令A(yù),B,C分別為11000中能被5,6,8除盡的整數(shù)集合。顯然,其補(bǔ)集代表不具備被整除性質(zhì)的集合。根據(jù)題意有根據(jù)容斥原理,不能被5,6,8中任何一個(gè)數(shù)整除的數(shù)目為2.1 容斥原理例102.1 容斥原理2.1.3 容斥原理例 題例10、把n本不同的書放入m個(gè)有編號(hào)的箱子中去(nm),使得沒有一個(gè)箱子為空。共有多少種方法?解:設(shè)S表示n本不同的書任意放入m個(gè)有編號(hào)的箱子里的所有方法的集合,顯然|S|=mn 。令pi(i=1,2,m)表示箱子i為空這一性質(zhì),Ai(i=1,2,m)表示S中具有性質(zhì)pi的元素組成的集

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論