容斥定理的應(yīng)用 組合數(shù)學(xué)的內(nèi)容
card(A∪B)=card（A）+card（B）-card（A∩B）
card（A∪B∪C）=card（A）+card（B）+card（C）-card（A∩B）-card（A∩C）-card（B∩C）+card（A∩B∩C）
card（A∪B∪C∪D）=card（A）+card（B）+card（C）+card（D）-card（A∩B）-card（A∩C）-card（B∩C）-card（A∩D）+card（A∩B∩C）+card（A∩B∩D）+card（B∩C∩D）-card（A∩B∩C∩D）
更一般的容斥定理：
n(A1∪A2∪...∪Am)=∑n(Ai)1≤i≤m－∑n(Ai∩Aj)1≤i≤j≤m＋∑n(Ai∩Aj∩Ak)－…＋(-1)m-1n(A1∩A2…∩Am)1≤I,j,k≤m
注：m-1是-1的指數(shù)
這種公式的形式是很復(fù)雜的
重在理解
理解了就很好用了
甚至不用背就可以自己寫出公式來
解題的時(shí)候就得心應(yīng)手
不過這個(gè)公式已經(jīng)超出了高中的范疇了
高中最多也就討論m=3的情形
用語言表達(dá)似乎很困難
就是說求幾個(gè)集合的并集可以先把他們統(tǒng)統(tǒng)加起來
但是這樣做有些地方就多加了
那么就要減掉一些 （由公式來判斷什么需要減去）
但是這樣做有些地方就多減了
那么就要加上一些 （由公式來判斷什么需要加上）
.
如此重復(fù)繼續(xù)下去
最后得到的結(jié)果就是這幾個(gè)集合的并集
舉個(gè)例子吧
集合 a1 ,a2 ,a3
a1={ 1 ,2 ,3 ,4 }
a2={ 2 ,3 ,4 ,5 }
a3={ 3 ,4 ,5 ,1 }
求三個(gè)集合的并集
按照這個(gè)公式
∑n(Ai)1≤i≤m = a1 + a2 + a3 = { 1 ,2 ,3 ,4 ,2 ,3 ,4 ,5 ,3 ,4 ,5 ,1 }
∑n(Ai∩Aj)1≤i≤j≤m = (a1∩a2 + a2∩a3 + a3∩a1) = { 2 ,3 ,4 } +{ 3 ,4 ,5 } + { 3 ,4 ,1}
∑n(Ai∩Aj∩Ak)1≤i≤j≤m = (a1∩a2∩a3) = { 3 ,4 }
代入公式
三個(gè)集合的并集= a1 + a2 + a3 - (a1∩a2 + a2∩a3 + a3∩a1) + (a1∩a2∩a3) = { 1 ,2 ,3 ,4 ,2 ,3 ,4 ,5 ,3 ,4 ,5 ,1 } - ( { 2 ,3 ,4 } +{ 3 ,4 ,5 } + { 3 ,4 ,1 } ) + ( { 3 ,4 } ) = { 1 ,2 ,3 ,4 ,5 }
希望對(duì)你有所幫助