容斥原理講義

駱老師教室容斥原理例題在很多計數(shù)問題中常用到數(shù)學(xué)上的一個包含與排除原理，也稱為容斥原理。為了說明這個原理，我們先介紹一些集合的初步知識。在討論問題時，常常需要把具有某種性質(zhì)的同類事物放在一起考慮。如：A=｛五（1）班全體同學(xué)｝。我們稱一些事物的全體為一個集合。A=｛五（1）班全體同學(xué)｝就是一個集合。B=｛全體自然數(shù)｝=｛1，2，3，4，…｝是一個具體的有無限多個元素的集合。C=｛在1，2，3，…，100中能被3整除的數(shù)｝=｛3，6，9，12，…，99｝是一個具有有限多個元素的集合。通常集合用大寫的英文字母A、B、C、…表示。構(gòu)成這個集合的事物稱為這個集合的元素。如上面例子中五（1）班的每一位同學(xué)均是集合A的一個元素。又如在例1中任何一個自然數(shù)都是集合B的元素。像集合B這種含有無限多個元素的集合稱為無限集。像集合C這樣含有有限多個元素的集合稱為有限集。有限集合所含元素的個數(shù)常用符合︱A︱、︱B︱、︱C︱、…表示。記號A∪B表示所有屬于集合A或?qū)儆诩螧的元素所組成的集合，就是下邊示意圖中兩個圓所覆蓋的部分。集合A∪B叫做集合A與的并集?！啊取弊x作“并”，“A∪B”讀AAB設(shè)集合A=｛1，2，3，4｝，集合B=｛2，4，6，8｝，則A∪B=｛1，2，3，4，6，8｝。元素2，4在集合A、B中都有，在并集中只寫一個。記號A∩B表示所有既屬于集合A也屬于集合B中的元素的全體。就是上面圖中陰影部分所表示的集合。即是由集合A、B的公共元素所組成的集合。它稱為集合A、B的交集。符號“∩”讀作“交”，“A∩B”讀作“A交B”。如例3中的集合A、B，則A∩B=｛2，4｝。設(shè)集合I=｛1，3，5，7，9｝，集合A=｛3，5，7｝，=｛屬于集合，但不屬于集合A的全體元素｝=｛1，9｝。我們稱屬于集合I但不屬于集合A的元素的集合為集合A在集合I中的補集（或余集），如下圖中陰影部分表示的集合（整個長方形表示集合I），常記作。如例4中=｛1，9｝就是集合A在集合I中的補集。顯然，A和沒有公共元素，即A∩=（表示空集，即沒有元素的集合）。實驗小學(xué)各年級都參加的一次書法比賽中，四年級與五年級共有20人獲獎，在獲獎?wù)咧杏?6人不是四年級的，有12人不是五年級的。該校書法比賽獲獎的總?cè)藬?shù)是多少人？分析由“16人不是四年級的”可知：16人是五年級和其他年級的；由“12人不是五年級的”可知：12人是四年級和其它年級的。用16＋12可算出四年級加五年級以及兩個其它年級的人數(shù)和，再減去20就得兩個其他年級的人數(shù)，這樣其他年級的人數(shù)是：（16＋12－20）÷2=4人，該校參加書法比賽獲獎的總?cè)藬?shù)是4＋20=24人。在100個外語教師中，懂英語的有75人，懂日語的有45人，其中必然有既懂英語又懂日語的老師。問：只懂英語的老師有多少人？分析顯然，兩種語言都懂的人在懂英語的75人中統(tǒng)計過一次，在懂日語的45人中又統(tǒng)計過一次。因此，75＋45=120人，比100多出的20人就是兩種語言都懂的人數(shù)。然后，從懂英語的75人中減去兩種語言都懂的20人，就是只懂英語的人數(shù)了：75－20=55人。求在1至100的自然數(shù)中能被3或7整除的數(shù)的個數(shù)。分析解這類問題時首先要知道在一串連續(xù)自然數(shù)中能被給定整數(shù)整除的數(shù)的個數(shù)規(guī)律是：在n個連續(xù)自然數(shù)中有且僅有一個數(shù)能被n整除。根據(jù)這個規(guī)律我們可以很容易地求出在1至100中能被3整除的數(shù)的個數(shù)為33個，被7整除的數(shù)的個數(shù)為14個，而其中被3和7都能整除的數(shù)有4個。因而得到：解：設(shè)A=｛在1～100的自然數(shù)中能被3整除的數(shù)｝，B=｛在1～100的自然數(shù)中能被7整除的數(shù)｝，則A∩B=｛在1～100的自然數(shù)中能被21整除的數(shù)｝。因為100÷3=33…1，所以︱A︱=33；因為100÷7=14…2，所以︱B︱=14；因為100÷21=4…16，所以︱A∩B︱=4。由容斥原理的公式（1）：︱A∪B︱=33+14-4=43。答：在1～100的自然數(shù)中能被3或7整除的數(shù)有43個。求在1～100的自然數(shù)中不是5的倍數(shù)也不是6的倍數(shù)的數(shù)有多少個？分析如果在1～100的自然數(shù)中去掉5的倍數(shù)、6的倍數(shù)，剩下的數(shù)就既不是5的倍數(shù)也不是6的倍數(shù)，即問題要求的結(jié)果。解：設(shè)A=｛在1～100的自然數(shù)中5的倍數(shù)的數(shù)｝B=｛在1～100的自然數(shù)中6的倍數(shù)的數(shù)｝則問題就是要求A∪B在集合｛1，2，…，100｝中的補集A∪B的元素個數(shù)。為此先求︱A∪B︱。因為100÷5=20，所以︱A︱=20又因為100÷6=16…4，所以︱B︱=16因為100÷30=3…10，所以︱A∩B︱=3︱A∪B︱=︱A︱＋︱B︱－︱A∩B︱20＋16－3=33所以A∪B=100－︱A∪B︱=100－33=67（個）答：在1～100的自然數(shù)中既不是5的倍數(shù)又不是6的倍數(shù)的數(shù)共67個。上面的例子是把一組事物按兩種不同的性質(zhì)來分類后，求具有其中一種性質(zhì)的元素個數(shù)問題。如果把一組事物按三種不同性質(zhì)來分類后，求具有其中一種性質(zhì)的元素個數(shù)的公式該是什么樣的呢？我們?nèi)杂脠D形來說明它具有與公式（1）類似的公式：︱A∪B∪C︱=︱A︱＋︱B︱＋︱C︱－︱A∩B︱－︱A∩C︱－︱B∩C︱＋︱A∩B∩C︱，（2）【非常重要，三個集合的容斥關(guān)系】例題如下

假設(shè)有100人參加了三個興趣小組。其中參加