歡迎來(lái)到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁(yè) 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

第四專題容斥原理

  • 資源ID:146749275       資源大?。?span id="sqioao0" class="font-tahoma">781KB        全文頁(yè)數(shù):12頁(yè)
  • 資源格式: DOC        下載積分:10積分
快捷下載 游客一鍵下載
會(huì)員登錄下載
微信登錄下載
三方登錄下載: 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要10積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫(xiě)的郵箱或者手機(jī)號(hào),方便查詢和重復(fù)下載(系統(tǒng)自動(dòng)生成)
支付方式: 微信支付   
驗(yàn)證碼:   換一換

 
賬號(hào):
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會(huì)被瀏覽器默認(rèn)打開(kāi),此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁(yè)到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請(qǐng)使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無(wú)水印,預(yù)覽文檔經(jīng)過(guò)壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒(méi)有明確說(shuō)明有答案則都視為沒(méi)有答案,請(qǐng)知曉。

第四專題容斥原理

第四專題 容斥原理 教學(xué)時(shí)數(shù):4學(xué)時(shí) 教學(xué)目標(biāo): (1)理解組合數(shù)學(xué)三大原理之一的容斥原理; (2)了解運(yùn)用容斥原理處理的常見(jiàn)問(wèn)題; (3)靈活使用容斥原理解決問(wèn)題。 教學(xué)重點(diǎn)與難點(diǎn): 如何將問(wèn)題轉(zhuǎn)化成可利用容斥原理解決的問(wèn)題。 一、基礎(chǔ)知識(shí) (一)容斥原理及逐步淘汰原理 容斥原理:(1)(簡(jiǎn)單形式) 對(duì)任何有限集合,有; (2)(一般形式) 對(duì)任何個(gè)有限集合,有 簡(jiǎn)記: 逐步淘汰原理:(1)(簡(jiǎn)單形式) (2)(一般形式) (二)容斥原理的兩種證明方法 證法一:(數(shù)學(xué)歸納法) 當(dāng) 時(shí),要證明: 這可由等于不相交的兩個(gè)集合和的并推出, 而等于不相交的兩個(gè)集合和的并。 所以, ① ② 由①、②知 假設(shè)對(duì)個(gè)集合,要證的等式成立; 對(duì)個(gè)集合時(shí),有 將和式中具有相同因子數(shù)的項(xiàng)合并,即可得到要證明的等式。 證法二:(貢獻(xiàn)法) 如果,則,公式兩端均為0,成立; 如果,設(shè)恰屬于個(gè)。此時(shí),公式右端中對(duì)共計(jì)數(shù)次,對(duì)共計(jì)數(shù)次,對(duì)共計(jì)數(shù)次,…..,對(duì)共計(jì)數(shù)次,并且在此后的各項(xiàng)中,均未被計(jì)數(shù),故公式右端對(duì)共計(jì)數(shù) 故等式成立。 (三)逐步淘汰原理的另一種描述 設(shè)有個(gè)元素,其中個(gè)元素具有特性,個(gè)元素具有特性,…,個(gè)元素既具有和特性,…,個(gè)元素既具有、和特性,…,則完全不具有中任何一種特性的元素個(gè)數(shù)為 。 為了便于記憶,逐步淘汰原理可采用符號(hào)形式: 約定:,,,,則 (四)幾點(diǎn)說(shuō)明 1、容斥原理是19世紀(jì)英國(guó)數(shù)學(xué)家西爾維斯特(J.J.Sylvester)首先建立。 2、逐步淘汰原理也叫篩公式,它和數(shù)論中的篩法有密切聯(lián)系。 3、容斥原理的更為一般的形式: 令為一有限集,為從到實(shí)數(shù)的一個(gè)函數(shù)。對(duì)每一個(gè)子集, 令其中。若,則。 若為常值函數(shù),即對(duì)所有的,。便為通常情況下的容斥原理。 二、典型例題選講 例1、在1~600中,能被6整除,但不能被8整除的數(shù)有多少個(gè)? 【思路】畫(huà)個(gè)示意圖,理清關(guān)系。 【評(píng)注】解決問(wèn)題的基本方法是畫(huà)個(gè)示意圖。 思考1:求1~100這100個(gè)正整數(shù)數(shù)中有多少個(gè)質(zhì)數(shù)? 【思路】(逆向思維,先求1~100中合數(shù)的個(gè)數(shù)) 因?yàn)?,從?~100中的合數(shù)必然是1~10中的質(zhì)數(shù)2,3,5,7之一的倍數(shù)。 設(shè),,則 所以,全體質(zhì)數(shù)的個(gè)數(shù)為:。 【評(píng)注】質(zhì)數(shù)個(gè)數(shù)求解方法常見(jiàn)的是“篩子法”;當(dāng)不大時(shí),這是求解質(zhì)數(shù)個(gè)數(shù)的一個(gè)方法。 思考2:分母是1001的最簡(jiǎn)真分?jǐn)?shù),共多少個(gè)?(提示:) 例2、在一個(gè)代表團(tuán)里,懂英語(yǔ)、法語(yǔ)的有10人,懂英語(yǔ)、法語(yǔ)、俄語(yǔ)的有5人,懂英語(yǔ)、法語(yǔ)、漢語(yǔ)的有3人,懂四種語(yǔ)言的有2人,問(wèn)只懂英語(yǔ)、法語(yǔ)而不懂俄語(yǔ)、漢語(yǔ)的有幾人? 【思路】關(guān)系較復(fù)雜,借助逐步淘汰的另一描述進(jìn)行處理。 設(shè)分別為懂英語(yǔ)、法語(yǔ)、俄語(yǔ)、漢語(yǔ)的性質(zhì),問(wèn)題即求 【評(píng)注】當(dāng)關(guān)系較復(fù)雜時(shí),利用逐步淘汰的另一描述處理可能要簡(jiǎn)單些。 思考:在面積為6的正方形里有三個(gè)面積為3的多邊形。證明:在它們中間可以找到兩個(gè)多邊形使之公共部分的面積不小于1。 【思路】記這三個(gè)多邊形的指標(biāo)為1,2,3,并用表示指標(biāo)的多邊形面積,表示指標(biāo)的多邊形相交部分的面積,表示三者相交部分的面積,其中分別是某個(gè)指標(biāo)1,2,3。由容斥原理,有。因?yàn)?,而,因此。于是由抽屜原理知,在中必有某個(gè)。 【評(píng)注】問(wèn)題求解最后用到了面積重疊原理,即抽屜原理。 例3、7個(gè)人站一排,求甲不站最左邊,乙不站中間,丙不站最右邊的站法有多少種? 【思路】利用容斥原理處理。 【評(píng)注】對(duì)排列計(jì)數(shù)問(wèn)題,用容斥原理比直接分類討論簡(jiǎn)單。 思考1:有3個(gè),4個(gè),2個(gè),用這9個(gè)字母組成一個(gè)排列,若限定排列中同樣的字母不能全部相鄰,問(wèn)這樣的排列有多少? 【思路】設(shè):9個(gè)字母的各種排列組成的集合; :字母全相鄰的排列集合; :字母全相鄰的排列集合; :字母全相鄰的排列集合; 則, , , , , , 所以 【評(píng)注】這個(gè)問(wèn)題涉及到可重復(fù)排列問(wèn)題。 例4、從自然數(shù)1、2、3、4、5、……中依次劃去3和4的倍數(shù)但保留其中是5的倍數(shù),劃完后將剩下的數(shù)依次構(gòu)成一個(gè)新的數(shù)列:,求。 【思路】畫(huà)示意圖,先弄清楚1~60中,剩下多少個(gè)數(shù)。 【評(píng)注】這個(gè)問(wèn)題涉及到周期段問(wèn)題。 定理:稱不大于正整數(shù)且與互質(zhì)的正整數(shù)的個(gè)數(shù)為的歐拉函數(shù),記作。設(shè)是的全部質(zhì)因數(shù),則是1到中,不能被中任何一個(gè)整除的整數(shù)的個(gè)數(shù)。易知:。 【思路】記,令] 則,,……, 所以, 例5、將與105互質(zhì)的所有正整數(shù)從小到大排成一排組成一個(gè)數(shù)列},比如 ,求這個(gè)數(shù)列的第1000項(xiàng)。 【思路】先求出1~105中有多少項(xiàng)數(shù)。 因?yàn)椋? 因?yàn)?,? 由于, ,所以,。 【評(píng)注】該問(wèn)題是一種常見(jiàn)的問(wèn)題,處理手段為分段處理。 思考:已知,求滿足條件,且的整數(shù)的個(gè)數(shù). 【思路】因?yàn)?,所以不能?,5,199整除, 即模2不為1;模5不為1,4;模199不為1,198。 令,規(guī)定的如下子集: ,, 則 , , 故 ,,,,, ,, 所以, 【評(píng)注】該問(wèn)題是用道一點(diǎn)數(shù)論知識(shí)。 例6、求這樣的無(wú)序三數(shù)組均為正整數(shù))的個(gè)數(shù),使得的最小公倍數(shù)是1600。 【思路】將最小公倍數(shù)進(jìn)行刻畫(huà)。 因。從指數(shù)來(lái)看,2與5的指數(shù)取法有集合, 中的一對(duì)對(duì)應(yīng)于1600的一個(gè)因子。 所求的的個(gè)數(shù)相當(dāng)于下列選擇方法數(shù):從中可重復(fù)地選擇三元素 使。 從中可重復(fù)地選擇3個(gè)元的方法數(shù)是; 從中可重復(fù)地選擇3個(gè)元,且的方法數(shù)是; 從中可重復(fù)地選擇3個(gè)元,且的方法數(shù)是; 從中可重復(fù)地選擇3個(gè)元,且的方法數(shù)是; 由容斥原理知, 【評(píng)注】該問(wèn)題是涉及可重復(fù)組合問(wèn)題。 例7、由數(shù)字1、2、3組成的位數(shù),要求位數(shù)中1、2、3的每一個(gè)數(shù)字至少出現(xiàn)一次,求這樣的位數(shù)的個(gè)數(shù)。 【思路】直接法比較煩瑣,考慮間接求解。 記由1,2,3構(gòu)成的位數(shù)的全體是, 并記 則 【評(píng)注】該問(wèn)題也可建立遞推關(guān)系處理。 思考:在不含數(shù)字0,9的所有位正整數(shù)中,同時(shí)包括數(shù)字1,2,3,4,5的數(shù)有多少個(gè)?這里數(shù)字可重復(fù),。 【思路】記:由1,2,3,4,5,6,7,8組成的位數(shù)集; :中不含數(shù)字()的位數(shù)集。 中不全含1,2,3,4,5的位數(shù)集為, 則 所以,中同時(shí)包括1,2,3,4,5的位數(shù)共有, 【評(píng)注】處理手段與例7差不多,體會(huì)該處理手段。 例8、4個(gè)人各寫(xiě)一張賀年卡,先集中起來(lái),然后各取一張,使每人所取得的賀年卡都是別人寫(xiě)的取法有多少種? 定理:設(shè)元按序排列為,要求元重新排列,使沒(méi)有一個(gè)元在原來(lái)的位置,這樣就叫錯(cuò)位排列,以表示元的所有可能的錯(cuò)位排列, 則。 【思路】記為 的所有排列的集合,是中所有滿足在第號(hào)位置上的排列的集合,。 顯然,,,……, 所以, 思考:5雙不同的鞋排成一行,求沒(méi)有一雙鞋相鄰的排列種數(shù)。 【思路】設(shè)為第雙鞋相鄰的10只鞋的排列組成的集合。 則,, , 則至少有一雙鞋相鄰的排列總數(shù)為: 所以,沒(méi)有一雙鞋相鄰的排列總數(shù)為: 。 例9、對(duì)于任何的集合,記為集合的元素的個(gè)數(shù),記為集合的子集個(gè)數(shù).如果是三個(gè)集合,滿足下列條件: (1); (2),求的最小值. 【思路】如果一個(gè)集合有個(gè)元素,則它有個(gè)子集。由題設(shè)有 ,即 因?yàn)槭谴笥?且等于一個(gè)2的整數(shù)冪,所以,, 從而 由容斥原理得, 從而 顯然,,, 故 另一方面,取,, 滿足題設(shè)條件,這時(shí) 所以,的最小值為97。 例10、設(shè)是有理數(shù)的集合,其中,且有循環(huán)小數(shù)的展開(kāi)式為 ,不一定相異。在的元素中,能寫(xiě)成最簡(jiǎn)分?jǐn)?shù)的不同的分子有多少個(gè)? 【思路】因?yàn)?,又,故如果既不能?整除也不能被37整除,則分?jǐn)?shù)就是最簡(jiǎn)形式。 設(shè)={不超過(guò)999的正整數(shù)中3的倍數(shù)},={不超過(guò)999的正整數(shù)中37的倍數(shù)}。 易知 故 即此類最簡(jiǎn)分?jǐn)?shù)的不同分子有648個(gè)。 此外,還有形如的數(shù),其中正整數(shù)是小于37且為3的倍數(shù)的數(shù),這樣的有12個(gè)。所以,滿足條件的分子有648+12=660個(gè)。 例11、求不定方程滿足條件: 的正整數(shù)解的個(gè)數(shù). 【思路】設(shè)是該不定方程的正整數(shù)解的集合,則 又令; ; ; 。 為了計(jì)算,可作如下分析: 若,因,故,將代入原方程得① 于是是①的正整數(shù)解。因此, 同理,; , 由此可知,原方程的解為: 例12、25支球隊(duì)進(jìn)行單循環(huán)比賽,若每個(gè)球隊(duì)已賽場(chǎng)次均不小于19。 證明;必存在5個(gè)球隊(duì),它們之間的每場(chǎng)比賽都已經(jīng)進(jìn)行。 【思路】任取一球隊(duì),用表示與賽過(guò)的球隊(duì)所成的集合,由條件,故有球隊(duì),與間的比賽已經(jīng)進(jìn)行過(guò)。用表示與已賽過(guò)的球隊(duì)所成的集合,由容斥原理知, 故有球隊(duì),此時(shí),,間比賽均已經(jīng)進(jìn)行過(guò)。用表示與已賽過(guò)的球隊(duì)所成的集合,由容斥原理知, 故有球隊(duì),此時(shí),,,間比賽均已經(jīng)進(jìn)行過(guò)。用表示與已賽過(guò)的球隊(duì)所成的集合,由容斥原理知, 故存在球隊(duì),此時(shí),,,,間比賽均已經(jīng)進(jìn)行過(guò)。 【評(píng)注】該問(wèn)題可用圖論知識(shí)處理,用容斥原理處理也比較間接。 例13、對(duì)正實(shí)數(shù),記。設(shè)是三個(gè)大于1的正實(shí)數(shù),滿足,則三個(gè)集合中,必有兩個(gè)的交集是無(wú)限集。 解:我們不妨直接考慮無(wú)限集合,而且引入一個(gè)參量(為正整數(shù)),考慮有限集合,類似定義。 則,, 由容斥原理及知 所以, 由于是正常數(shù),而是任意大的正整數(shù),從而中必有兩個(gè)的交集是無(wú)限集。 【說(shuō)明】:或,關(guān)于有類似的結(jié)果; 【評(píng)注】將無(wú)限問(wèn)題轉(zhuǎn)化為有限問(wèn)題是處理這類問(wèn)題的常見(jiàn)技巧。 例14、設(shè),求最小的使得中的每個(gè)不同元素中均可找出4個(gè)兩兩互質(zhì)的數(shù). 【思路】(極端化原理,尋找的一個(gè)下界)先考察2的倍數(shù),3的倍數(shù),5的倍數(shù)的數(shù)的個(gè)數(shù)。這是3個(gè)比較多的數(shù)。 設(shè),,,則 所以,在中是2或3或5的倍數(shù)的數(shù)有 于是,對(duì)于上述的74元集,從中任取4個(gè)數(shù),由抽屜原理知其中必有兩個(gè)數(shù)同為2或3或5的倍數(shù),它們不互質(zhì)。所以,。 下面證明是可以的。 構(gòu)造如下4個(gè)集合(注意:1~100中共有25個(gè)質(zhì)數(shù)) ;; ; 這四個(gè)集合每?jī)蓚€(gè)的交集為空集,且每個(gè)集合中的任意兩個(gè)數(shù)都互質(zhì)。所以 設(shè),且,則中至少有 個(gè)元素取自,于是由抽屜原理知, 至少有個(gè)數(shù)取自某個(gè),由構(gòu)造知,這4個(gè)數(shù)是兩兩互質(zhì)的。 綜上所述,的最小值為75。 【評(píng)注】先找到的下界,再證明它符合。這是處理組合極值的常見(jiàn)思路。 思考:設(shè),求最小的使得中的每個(gè)不同元素中均可找出5個(gè)兩兩互質(zhì)的數(shù). (答案:的最小值為217)。 第四專題 容斥原理 (第 12 頁(yè) 共 12 頁(yè))

注意事項(xiàng)

本文(第四專題容斥原理)為本站會(huì)員(無(wú)***)主動(dòng)上傳,裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請(qǐng)重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  sobing.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!

五月丁香婷婷狠狠色,亚洲日韩欧美精品久久久不卡,欧美日韩国产黄片三级,手机在线观看成人国产亚洲