第四專題容斥原理

第四專題 容斥原理 教學(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è)）