第四專題容斥原理

《第四專題容斥原理》由會(huì)員分享，可在線閱讀，更多相關(guān)《第四專題容斥原理（12頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第四專題 容斥原理教學(xué)時(shí)數(shù)：4學(xué)時(shí)教學(xué)目標(biāo)： （1）理解組合數(shù)學(xué)三大原理之一的容斥原理；（2）了解運(yù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è)

2、集合時(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、逐步淘汰原理也叫篩公

3、式，它和數(shù)論中的篩法有密切聯(lián)系。 3、容斥原理的更為一般的形式： 令為一有限集，為從到實(shí)數(shù)的一個(gè)函數(shù)。對(duì)每一個(gè)子集，令其中。若，則。 若為常值函數(shù)，即對(duì)所有的，。便為通常情況下的容斥原理。二、典型例題選講例1、在1600中，能被6整除，但不能被8整除的數(shù)有多少個(gè)？ 【思路】畫個(gè)示意圖，理清關(guān)系?！驹u(píng)注】解決問(wèn)題的基本方法是畫個(gè)示意圖。思考1：求1100這100個(gè)正整數(shù)數(shù)中有多少個(gè)質(zhì)數(shù)？【思路】（逆向思維，先求1100中合數(shù)的個(gè)數(shù)）因?yàn)椋瑥亩?100中的合數(shù)必然是110中的質(zhì)數(shù)2，3，5，7之一的倍數(shù)。設(shè)，則 所以，全體質(zhì)數(shù)的個(gè)數(shù)為：?！驹u(píng)注】質(zhì)數(shù)個(gè)數(shù)求解方法常見的是“篩子法”；當(dāng)不大時(shí)，這是求

4、解質(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)的多

5、邊形相交部分的面積，表示三者相交部分的面積，其中分別是某個(gè)指標(biāo)1，2，3。由容斥原理，有。因?yàn)?，而，因此。于是由抽屜原理知，在中必有某個(gè)?！驹u(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è)字母的各種排列組成的集合； ：字母全相鄰的排列集合；：字母全相鄰的排列集合； ：字母全相鄰的排列集合； 則， ， ， ， ，

6、，所以 【評(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ù)列：，求?！舅悸贰慨嬍疽鈭D，先弄清楚160中，剩下多少個(gè)數(shù)?！驹u(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)?！舅悸贰肯惹蟪?105中有多少項(xiàng)數(shù)。因?yàn)?，?因?yàn)椋?由于，所以，?！驹u(píng)注】該問(wèn)題是一種常見

7、的問(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)行刻畫。因。從指數(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ù)是；從中

8、可重復(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差

9、不多，體會(huì)該處理手段。例8、4個(gè)人各寫一張賀年卡，先集中起來(lái)，然后各取一張，使每人所取得的賀年卡都是別人寫的取法有多少種？定理：設(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è)集合，滿足下列條件：（

10、1）；（2），求的最小值. 【思路】如果一個(gè)集合有個(gè)元素，則它有個(gè)子集。由題設(shè)有 ，即 因?yàn)槭谴笥?且等于一個(gè)2的整數(shù)冪，所以， 從而 由容斥原理得， 從而顯然，故另一方面，取，滿足題設(shè)條件，這時(shí)所以，的最小值為97。例10、設(shè)是有理數(shù)的集合，其中，且有循環(huán)小數(shù)的展開式為，不一定相異。在的元素中，能寫成最簡(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è)。所

11、以，滿足條件的分子有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ì)所成的集合，由容斥原理知

12、， 故有球隊(duì)，此時(shí)，間比賽均已經(jīng)進(jìn)行過(guò)。用表示與已賽過(guò)的球隊(duì)所成的集合，由容斥原理知， 故存在球隊(duì)，此時(shí)，間比賽均已經(jīng)進(jìn)行過(guò)?！驹u(píng)注】該問(wèn)題可用圖論知識(shí)處理，用容斥原理處理也比較間接。例13、對(duì)正實(shí)數(shù)，記。設(shè)是三個(gè)大于1的正實(shí)數(shù)，滿足，則三個(gè)集合中，必有兩個(gè)的交集是無(wú)限集。解：我們不妨直接考慮無(wú)限集合，而且引入一個(gè)參量（為正整數(shù)），考慮有限集合，類似定義。則，由容斥原理及知 所以， 由于是正常數(shù)，而是任意大的正整數(shù)，從而中必有兩個(gè)的交集是無(wú)限集?！菊f(shuō)明】：或，關(guān)于有類似的結(jié)果；【評(píng)注】將無(wú)限問(wèn)題轉(zhuǎn)化為有限問(wèn)題是處理這類問(wèn)題的常見技巧。例14、設(shè)，求最小的使得中的每個(gè)不同元素中均可找出4個(gè)兩兩互

13、質(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è)集合（注意：1100中共有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)注】先找到的下界，再證明它符合。這是處理組合極值的常見思路。思考：設(shè)，求最小的使得中的每個(gè)不同元素中均可找出5個(gè)兩兩互質(zhì)的數(shù). （答案：的最小值為217）。第四專題 容斥原理 （第 12 頁(yè) 共 12 頁(yè)）