容斥原理講義

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

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