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

1、容斥原埋 在很多計數(shù)問題中常用到數(shù)學上的一個包含與排除原理，也稱為容斥 原理?為了說明這個原理，我們先介紹一些集合的初步知識。 例1、桌上有兩張圓紙片A、B?假設(shè)圓紙片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ù)中有且

2、僅有一個數(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ù)｝，則 1304180943 AAB= ｛在1?100的自然數(shù)中能被21整除的數(shù)｝。 ???100一3=33???1,.?.| A 1=33。 ???100一7=14???2,.?.| B I =14。 ? 100一21=4???16,.?.| APB I =4。 由容斥原理的公式（1）：l AUB 1=

3、33+14-4=43。 答：在1?100的自然數(shù)中能被3或7整除的數(shù)有43個。 例3、求在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ù)｝, 則問題就是更求AUB在集合｛1, 2, 100｝中的補集AUB^TL素個 數(shù)?為此先求I AUB I。 ???100一50=20,???| A I =20 又???100一6=16???4,?I B I =16

4、 7100^30=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個）□ 答：在1?100的自然數(shù)中既不是5的倍數(shù)又不是6的倍數(shù)的數(shù)共67 個。 我們也可以把公式（1）用于求幾何圖形的面積?這時，A和B是平面 上的兩個點集（即點的集合），都是幾何圖形.I A I,I B I,…吩別表 示A的面積，B的面積，…。 例4、設(shè)下面圖中正方形的邊長為1厘米，半圓均以正方形的邊為直徑， 求圖中陰影部分的面積。

5、答：陰影面積為0.57平方厘米。 上面的例子是把一組事物按兩種不同的性質(zhì)來分類后，求具有其中一 種性質(zhì)的元素個數(shù)問題?如果把一組事物按三種不同性質(zhì)來分類后，求具 有其中一種性質(zhì)的元素個數(shù)的公式該是什么樣的呢？我們?nèi)杂脠D形來說 明它具有與公式（1）類似的公式： I AUBUC l = lAl + lBl + ICl-l APB I - I APC I - I BP Cl + I APBPC I, (2) 其中 AUBUC=AU(BUC), APBPC=AP(BPC)? 右圖中三個圓A、B、C分別表示具有三種不同性質(zhì)的集合，并如圖 用M1、M2、M3、…、M7表示由三個圓形成的內(nèi)部互不

6、重疊的部分所 含元素的個數(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 APB PC I, 即公式(2) 成立。 事實上這個規(guī)律還可推廣到按多種性質(zhì)來分類的情形?設(shè)集合M中的 每個元素至少具有t種性質(zhì)中的一種，用n表示各個具有1種性質(zhì)的集合 1 中的元素個數(shù)的和，n表示各個具有2種性質(zhì)的集合中元素個數(shù)的和，?… 2 n表示具有t種性質(zhì)的集合中元素的個數(shù)，則集合M中元素的個數(shù)m為: m=n -n +n-n+…土 n 1 2 3 4 t 最后一項當t為偶數(shù)時取“-”號，否則取“+”號。