《奧數(shù) 容斥原理》由會員分享，可在線閱讀，更多相關《奧數(shù) 容斥原理（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、容斥原埋在很多計數(shù)問題中常用到數(shù)學上的一個包含與排除原理，也稱為容斥原理為了說明這個原理，我們先介紹一些集合的初步知識。例1、桌上有兩張圓紙片A、B假設圓紙片A的面積為30平方厘米，圓紙片B的面積為20平方厘米這兩張圓紙片重疊部分的面積為10平方厘米則這兩張圓紙片覆蓋桌面的面積由容斥原理的公式（1）可以算出為: 厘米）。I AUB I =30+20-10=40 （平方例2、求在1至100的自然數(shù)中能被3或7整除的數(shù)的個數(shù)。分析解這類問題時首先要知道在一串連續(xù)自然數(shù)中能被給定整數(shù)整 除的數(shù)的個數(shù)規(guī)律是：在n個連續(xù)自然數(shù)中有且僅有一個數(shù)能被n整除. 根據(jù)這個規(guī)律我們可以很容易地求出在1至100中能
2、被3整除的數(shù)的個數(shù) 為33個，被7整除的數(shù)的個數(shù)為14個，而其中被3和7都能整除的數(shù)有 4個，因而得到解：設A= 在1100的自然數(shù)中能被3整除的數(shù),B=在1100的自然數(shù)中能被7整除的數(shù)，則1304180943AAB= 在1100的自然數(shù)中能被21整除的數(shù)。100一3=331,.| A 1=33。100一7=142,.| B I =14。 100一21=416,.| APB I =4。由容斥原理的公式（1）：l AUB 1=33+14-4=43。答：在1100的自然數(shù)中能被3或7整除的數(shù)有43個。例3、求在1100的自然數(shù)中不是5的倍數(shù)也不是6的倍數(shù)的數(shù)有多少 個？分析如果在1100的自然數(shù)
3、中去掉5的倍數(shù)、6的倍數(shù)，剩下的數(shù) 就既不是5的倍數(shù)也不是6的倍數(shù)，即問題要求的結果。解：設A=在1100的自然數(shù)中5的倍數(shù)的數(shù),B= 在1100的自然數(shù)中6的倍數(shù)的數(shù),則問題就是更求AUB在集合1, 2,100中的補集AUBTL素個數(shù)為此先求I AUB I。100一50=20,| A I =20又100一6=164,I B I =16710030=3-10,| APB I =3,I AUB I = I A I + I B I - I APB I =20+16-3=33。 I 丨 AUB I =100- I AUB I =100-33= 67 C個）答：在1100的自然數(shù)中既不是5的倍數(shù)又不是
4、6的倍數(shù)的數(shù)共67 個。我們也可以把公式（1）用于求幾何圖形的面積這時，A和B是平面 上的兩個點集（即點的集合），都是幾何圖形.I A I,I B I,吩別表 示A的面積，B的面積，。例4、設下面圖中正方形的邊長為1厘米，半圓均以正方形的邊為直徑， 求圖中陰影部分的面積。答：陰影面積為0.57平方厘米。上面的例子是把一組事物按兩種不同的性質來分類后，求具有其中一 種性質的元素個數(shù)問題如果把一組事物按三種不同性質來分類后，求具 有其中一種性質的元素個數(shù)的公式該是什么樣的呢？我們仍用圖形來說 明它具有與公式（1）類似的公式：I AUBUC l = lAl + lBl + ICl-l APB I -
5、 I APC I - I BPCl + I APBPC I,(2)其中 AUBUC=AU(BUC), APBPC=AP(BPC)右圖中三個圓A、B、C分別表示具有三種不同性質的集合，并如圖用M1、M2、M3、M7表示由三個圓形成的內部互不重疊的部分所含元素的個數(shù)，可見：I AUBUC I=M1+M2+M7= (M1+M4+M6+M7) + (M2+M4+M5+M7) + (M3+M5+M6+M7) - (M4+M7) + (M5+M7) + (M6+M7) +M7= IAI + IBI + ICI-I APB I - I BPC I - I APC I + I APBPC I,即公式(2) 成立。事實上這個規(guī)律還可推廣到按多種性質來分類的情形設集合M中的每個元素至少具有t種性質中的一種，用n表示各個具有1種性質的集合1中的元素個數(shù)的和，n表示各個具有2種性質的集合中元素個數(shù)的和，2n表示具有t種性質的集合中元素的個數(shù)，則集合M中元素的個數(shù)m為:m=n -n +n-n+土 n1234t最后一項當t為偶數(shù)時取“-”號，否則取“+”號。
奧數(shù) 容斥原理
