第四專題容斥原理

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

1、第四專題 容斥原理教學(xué)時數(shù)：4學(xué)時教學(xué)目標(biāo)： （1）理解組合數(shù)學(xué)三大原理之一的容斥原理；（2）了解運用容斥原理處理的常見問題；（3）靈活使用容斥原理解決問題。教學(xué)重點與難點： 如何將問題轉(zhuǎn)化成可利用容斥原理解決的問題。一、基礎(chǔ)知識（一）容斥原理及逐步淘汰原理容斥原理：（1）（簡單形式）對任何有限集合，有； （2）（一般形式）對任何個有限集合，有 簡記：逐步淘汰原理：（1）（簡單形式） （2）（一般形式）（二）容斥原理的兩種證明方法證法一：（數(shù)學(xué)歸納法） 當(dāng) 時，要證明： 這可由等于不相交的兩個集合和的并推出， 而等于不相交的兩個集合和的并。 所以， 由、知 假設(shè)對個集合，要證的等式成立； 對個

2、集合時，有 將和式中具有相同因子數(shù)的項合并，即可得到要證明的等式。 證法二：（貢獻法）如果，則，公式兩端均為0，成立；如果，設(shè)恰屬于個。此時，公式右端中對共計數(shù)次，對共計數(shù)次，對共計數(shù)次，.，對共計數(shù)次，并且在此后的各項中，均未被計數(shù)，故公式右端對共計數(shù)故等式成立。（三）逐步淘汰原理的另一種描述設(shè)有個元素，其中個元素具有特性，個元素具有特性，個元素既具有和特性，個元素既具有、和特性，則完全不具有中任何一種特性的元素個數(shù)為。為了便于記憶，逐步淘汰原理可采用符號形式：約定：，則（四）幾點說明1、容斥原理是19世紀英國數(shù)學(xué)家西爾維斯特（J.J.Sylvester）首先建立。 2、逐步淘汰原理也叫篩公

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

4、解質(zhì)數(shù)個數(shù)的一個方法。思考2：分母是1001的最簡真分數(shù)，共多少個？（提示：）例2、在一個代表團里，懂英語、法語的有10人，懂英語、法語、俄語的有5人，懂英語、法語、漢語的有3人，懂四種語言的有2人，問只懂英語、法語而不懂俄語、漢語的有幾人？【思路】關(guān)系較復(fù)雜，借助逐步淘汰的另一描述進行處理。設(shè)分別為懂英語、法語、俄語、漢語的性質(zhì)，問題即求 【評注】當(dāng)關(guān)系較復(fù)雜時，利用逐步淘汰的另一描述處理可能要簡單些。思考：在面積為6的正方形里有三個面積為3的多邊形。證明：在它們中間可以找到兩個多邊形使之公共部分的面積不小于1?！舅悸贰坑涍@三個多邊形的指標(biāo)為1，2，3，并用表示指標(biāo)的多邊形面積，表示指標(biāo)的多

5、邊形相交部分的面積，表示三者相交部分的面積，其中分別是某個指標(biāo)1，2，3。由容斥原理，有。因為，而，因此。于是由抽屜原理知，在中必有某個?！驹u注】問題求解最后用到了面積重疊原理，即抽屜原理。例3、7個人站一排，求甲不站最左邊，乙不站中間，丙不站最右邊的站法有多少種？ 【思路】利用容斥原理處理?！驹u注】對排列計數(shù)問題，用容斥原理比直接分類討論簡單。思考1：有3個，4個，2個，用這9個字母組成一個排列，若限定排列中同樣的字母不能全部相鄰，問這樣的排列有多少？【思路】設(shè)：9個字母的各種排列組成的集合； ：字母全相鄰的排列集合；：字母全相鄰的排列集合； ：字母全相鄰的排列集合； 則， ， ， ， ，

6、，所以 【評注】這個問題涉及到可重復(fù)排列問題。例4、從自然數(shù)1、2、3、4、5、中依次劃去3和4的倍數(shù)但保留其中是5的倍數(shù)，劃完后將剩下的數(shù)依次構(gòu)成一個新的數(shù)列：，求?！舅悸贰慨嬍疽鈭D，先弄清楚160中，剩下多少個數(shù)?！驹u注】這個問題涉及到周期段問題。定理：稱不大于正整數(shù)且與互質(zhì)的正整數(shù)的個數(shù)為的歐拉函數(shù)，記作。設(shè)是的全部質(zhì)因數(shù)，則是1到中，不能被中任何一個整除的整數(shù)的個數(shù)。易知：?！舅悸贰坑?，令則，所以， 例5、將與105互質(zhì)的所有正整數(shù)從小到大排成一排組成一個數(shù)列，比如，求這個數(shù)列的第1000項?！舅悸贰肯惹蟪?105中有多少項數(shù)。因為，故 因為，故 由于，所以，?！驹u注】該問題是一種常見

7、的問題，處理手段為分段處理。思考：已知，求滿足條件，且的整數(shù)的個數(shù).【思路】因為，所以不能被2，5，199整除，即模2不為1；模5不為1，4；模199不為1，198。令，規(guī)定的如下子集：， 則 ， ，故 ， ，所以，【評注】該問題是用道一點數(shù)論知識。例6、求這樣的無序三數(shù)組均為正整數(shù)）的個數(shù)，使得的最小公倍數(shù)是1600。【思路】將最小公倍數(shù)進行刻畫。因。從指數(shù)來看，2與5的指數(shù)取法有集合，中的一對對應(yīng)于1600的一個因子。所求的的個數(shù)相當(dāng)于下列選擇方法數(shù)：從中可重復(fù)地選擇三元素使。從中可重復(fù)地選擇3個元的方法數(shù)是；從中可重復(fù)地選擇3個元，且的方法數(shù)是；從中可重復(fù)地選擇3個元，且的方法數(shù)是；從中

8、可重復(fù)地選擇3個元，且的方法數(shù)是；由容斥原理知，【評注】該問題是涉及可重復(fù)組合問題。例7、由數(shù)字1、2、3組成的位數(shù)，要求位數(shù)中1、2、3的每一個數(shù)字至少出現(xiàn)一次，求這樣的位數(shù)的個數(shù)?！舅悸贰恐苯臃ū容^煩瑣，考慮間接求解。記由1，2，3構(gòu)成的位數(shù)的全體是，并記則【評注】該問題也可建立遞推關(guān)系處理。思考：在不含數(shù)字0，9的所有位正整數(shù)中，同時包括數(shù)字1，2，3，4，5的數(shù)有多少個？這里數(shù)字可重復(fù)，。【思路】記：由1，2，3，4，5，6，7，8組成的位數(shù)集； ：中不含數(shù)字（）的位數(shù)集。 中不全含1，2，3，4，5的位數(shù)集為， 則所以，中同時包括1，2，3，4，5的位數(shù)共有，【評注】處理手段與例7差

9、不多，體會該處理手段。例8、4個人各寫一張賀年卡，先集中起來，然后各取一張，使每人所取得的賀年卡都是別人寫的取法有多少種？定理：設(shè)元按序排列為，要求元重新排列，使沒有一個元在原來的位置，這樣就叫錯位排列，以表示元的所有可能的錯位排列，則。【思路】記為的所有排列的集合，是中所有滿足在第號位置上的排列的集合，。顯然，所以， 思考：5雙不同的鞋排成一行，求沒有一雙鞋相鄰的排列種數(shù)?！舅悸贰吭O(shè)為第雙鞋相鄰的10只鞋的排列組成的集合。則，則至少有一雙鞋相鄰的排列總數(shù)為： 所以，沒有一雙鞋相鄰的排列總數(shù)為： 。例9、對于任何的集合，記為集合的元素的個數(shù)，記為集合的子集個數(shù).如果是三個集合，滿足下列條件：（

10、1）；（2），求的最小值. 【思路】如果一個集合有個元素，則它有個子集。由題設(shè)有 ，即 因為是大于1且等于一個2的整數(shù)冪，所以， 從而 由容斥原理得， 從而顯然，故另一方面，取，滿足題設(shè)條件，這時所以，的最小值為97。例10、設(shè)是有理數(shù)的集合，其中，且有循環(huán)小數(shù)的展開式為，不一定相異。在的元素中，能寫成最簡分數(shù)的不同的分子有多少個？【思路】因為，又，故如果既不能被3整除也不能被37整除，則分數(shù)就是最簡形式。設(shè)=不超過999的正整數(shù)中3的倍數(shù)，=不超過999的正整數(shù)中37的倍數(shù)。易知故即此類最簡分數(shù)的不同分子有648個。此外，還有形如的數(shù)，其中正整數(shù)是小于37且為3的倍數(shù)的數(shù)，這樣的有12個。所

11、以，滿足條件的分子有648+12=660個。例11、求不定方程滿足條件： 的正整數(shù)解的個數(shù).【思路】設(shè)是該不定方程的正整數(shù)解的集合，則又令； ； ； 。為了計算，可作如下分析：若，因，故，將代入原方程得 于是是的正整數(shù)解。因此， 同理，； ，由此可知，原方程的解為：例12、25支球隊進行單循環(huán)比賽，若每個球隊已賽場次均不小于19。證明；必存在5個球隊，它們之間的每場比賽都已經(jīng)進行?！舅悸贰咳稳∫磺蜿?，用表示與賽過的球隊所成的集合，由條件，故有球隊，與間的比賽已經(jīng)進行過。用表示與已賽過的球隊所成的集合，由容斥原理知，故有球隊，此時，間比賽均已經(jīng)進行過。用表示與已賽過的球隊所成的集合，由容斥原理知

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

13、質(zhì)的數(shù).【思路】（極端化原理，尋找的一個下界）先考察2的倍數(shù)，3的倍數(shù)，5的倍數(shù)的數(shù)的個數(shù)。這是3個比較多的數(shù)。 設(shè)，則所以，在中是2或3或5的倍數(shù)的數(shù)有于是，對于上述的74元集，從中任取4個數(shù)，由抽屜原理知其中必有兩個數(shù)同為2或3或5的倍數(shù)，它們不互質(zhì)。所以，。下面證明是可以的。構(gòu)造如下4個集合（注意：1100中共有25個質(zhì)數(shù)）；這四個集合每兩個的交集為空集，且每個集合中的任意兩個數(shù)都互質(zhì)。所以設(shè)，且，則中至少有個元素取自，于是由抽屜原理知，至少有個數(shù)取自某個，由構(gòu)造知，這4個數(shù)是兩兩互質(zhì)的。 綜上所述，的最小值為75?！驹u注】先找到的下界，再證明它符合。這是處理組合極值的常見思路。思考：設(shè)，求最小的使得中的每個不同元素中均可找出5個兩兩互質(zhì)的數(shù). （答案：的最小值為217）。第四專題 容斥原理 （第 12 頁 共 12 頁）