容斥原理

計數時無遺漏

徠在計數時,必須注意沒有重複,沒有遺漏。為了使重疊部分不被重複計算,人們研究出一種新的計數方法,這種方法的基本思想是:先不考慮重疊的情況,把包含於某內容中的所有對象的數目先計算出來,然後再把計數時重複計算的數目排斥出去,使得計算的結果既無遺漏又無重複,這種計數的方法稱為容斥原理。

定義


如果被計數的事物有A、B、C三類,那麼,A類和B類和C類元素個數總和= A類元素個數+ B類元素個數+C類元素個數—既是A類又是B類的元素個數—既是A類又是C類的元素個數—既是B類又是C類的元素個數+既是A類又是B類而且是C類的元素個數。(A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C)。
例如:一次期末考試,某班有15人數學得滿分,有12人語文得滿分,並且有4人語、數都是滿分,那麼這個班至少有一門得滿分的同學有多少人?
分析:依題意,被計數的事物有語、數得滿分兩類,“數學得滿分”稱為“A類元素”,“語文得滿分”稱為“B類元素”,“語、數都是滿分”稱為“既是A類又是B類的元素”,“至少有一門得滿分的同學”稱為“A類和B類元素個數”的總和。為15+12-4=23。

公式


也可表示為
設S為有限集, ,則
由於
所以
兩個集合的容斥關係公式:A∪B =|A∪B| = |A|+|B| - |A∩B |(∩:重合的部分)
三個集合的容斥關係公式:|A∪B∪C| = |A|+|B|+|C| - |A∩B| - |B∩C| - |C∩A| + |A∩B∩C|
詳細推理如下:
1、等式右邊改造 = {[(A+B - A∩B)+C - B∩C] - C∩A }+ A∩B∩C
2、維恩圖分塊標記如右圖圖:1245構成A,2356構成B,4567構成C
3、等式右邊()里指的是下圖的1+2+3+4+5+6六部分:
那麼A∪B∪C還缺部分7。
4、等式右邊[]號里+C(4+5+6+7)后,相當於A∪B∪C多加了4+5+6三部分,
減去B∩C(即5+6兩部分)后,還多加了部分4。
5、等式右邊{}里減去C∩A (即4+5兩部分)后,A∪B∪C又多減了部分5,
則加上A∩B∩C(即5)剛好是A∪B∪C。

嚴格證明


對於容斥原理我們可以利用數學歸納法證明:
證明:當 時,等式成立(證明略)。
假設 時結論成立,則當 時,
所以當 時,結論仍成立。因此對任意,均可使所證等式成立。

舉例


例1(小學奧數題)
某校六⑴班有學生45人,每人在暑假裡都參加體育訓練隊,其中參加足球隊的有25人,參加排球隊的有22人,參加游泳隊的有24人,足球、排球都參加的有12人,足球、游泳都參加的有9人,排球、游泳都參加的有8人,問:三項都參加的有多少人?
分析:參加足球隊的人數25人為A類元素,參加排球隊人數22人為B類元素,參加游泳隊的人數24人為C類元素,既是A類又是B類的為足球排球都參加的12人,既是B類又C類的為足球游泳都參加的9人,既是C類又是A類的為排球游泳都參加的8人,三項都參加的是A類B類C類的總和設為X。注意:這個題說的每人都參加了體育訓練隊,所以這個班的總人數即為A類B類和C類的總和。
答案:25+22+24-12-9-8+X=45 ,解得X=3
例2(高中題)
在1到1000的自然數中,能被3或5整除的數共有多少個?不能被3或5整除的數共有多少個?
分析:顯然,這是一個重複計數問題(當然,如果不怕麻煩你可以分別去數3的倍數,5的倍數)。我們可以把“能被3或5整除的數”分別看成A類元素和B類元素,能“同時被3或5整除的數(15的倍數)”就是被重複計算的數,即“既是A類又是B類的元素”。求的是“A類或B類元素個數”。我們還不能直接計算,必須先求出所需條件。1000÷3=333……1,能被3整除的數有333個(想一想,這是為什麼?)同理,可以求出其他的條件。
例3(高中題)
分母是1001的最簡分數一共有多少個?
分析:這一題實際上就是找分子中不能與1001進行約分的數。由於1001=7×11×13,所以就是找不能被7,11,13整除的數。
解答:1~1001中,有7的倍數1001/7 = 143 (個);有11的倍數1001/11 = 91 (個),有13的倍數1001/13 = 77 (個);有7*11=77;77是11的倍數1001/77 = 13 (個),有7*13=91;91是13的倍數;1001/91 = 11 (個),有11*13=143;143是13的倍數1001/143 = 7 (個).有1001的倍數1個。
由容斥原理知:在1~1001中,能被7或11或13整除的數有(143+91+77)-(13+11+7)+1=281(個),從而不能被7、11或13整除的數有1001-281=720(個).也就是說,分母為1001的最簡分數有720個。
例4(小學奧數題)
某個班的全體學生在進行了短跑、游泳、投擲三個項目的測試后,有4名學生在這三個項目上都沒有達到優秀,其餘每人至少有一項達到了優秀,達到了優秀的這部分學生情況如下表:
短跑游泳投擲
短跑
游泳
短跑
投擲
游泳
投擲
短跑
游泳
投擲
1 71 81 56652
求這個班的學生共有多少人?
分析:這個班的學生數,應包括達到優秀和沒有達到優秀的。
4+17+18+15-6-6-5+2=39(人)
例5(小學奧數題)
在一根長的木棍上有三種刻度線,第一種刻度線將木棍分成10等份,第二種將木棍分成12等份,第三種將木棍分成15等份。如果沿每條刻度線將木棍鋸斷,木棍總共被鋸成多少段?
分析:
很顯然,要計算木棍被鋸成多少段,只需要計算出木棍上共有多少條不同的刻度線,在此基礎上加1就是段數了。
若按將木棍分成10等份的刻度線鋸開,木棍有9條刻度線。在此木棍上加上將木棍分成12等份的11條刻度線,顯然刻度線有重複的,如5/10和6/12都是1/2。同樣再加上將木棍分成15等份的刻度線,也是如此。所以,我們應該按容斥原理的方法來解決此問題。用容斥原理的那一個呢?想一想,被計數的事物有那幾類?每一類的元素個數是多少?
解答
解一:[10,12,15]=60,設木棍60厘米
60÷10=6厘米,60÷12=5厘米,60÷15=4(厘米
10等分的為第一種刻度線,共10-1=9(條)
12等分的為第二種刻度線,共12-1=11(條)
15等分的為第三種刻度線,過15-1=14(條)
第一種與第二種刻度線重合的[6,5]=30,60÷30-1=2-1=1(條)
第一種與第三種刻度線重合的[6,4]=12,60÷12-1=5-1=4(條)
第二種與第三種刻度線重合的[5,4]=20,60÷20-1=3-1=2(條)
三種刻度線重合的沒有,[6、5、4]=60
徠因此,共有刻度線9+11+14-1-4-2=27條,木棍總共被鋸成27+1=28段。
解二:總長看成單位1分別分成10、12、15段。1/10與1/12的最小公倍數1/2,1/10與1/15的最小公倍數1/5,1/12與1/15的最小公倍數1/3,1/10,1/12和1/15的最小公倍數為1,有10+12+15-(2+5+3)+1=28
解三:
10、12、15的最小公倍數是60,假設木棍就是長60,
1、那麼,分成10等份的每份6,刻度就是
0,6,12,18,24,30,36,42,48,54,60
2、分成12等分的每份就是5,
0,5,10,15,20,25,30,35,40,45,50,55,60
3、分成15等分的每份就是4,
0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60
4、把相同刻度的合併,就是有刻度如下:
0,4,5,6,8,10,12,15,16,18,20,24,25,28,30,32,35,36,40,42,44,45,48,50,52,54,55,56,60