排容原理(Inclusion-Exclusion Principle


問題:一年甲班共有40個人,本次段考國文及格的有26人,英文及格的有24人,數學及格的有17人;國文和英文都及格的有17人,國文和數學都及格的有12人,英文和數學都及格的有11人;三科都及格的有10人。


如果問至少一科及格的有多少人?我們都知道可以用排容原理處理。


A表示國文及格的人所成的集合;
B
表示英文及格的人所成的集合;
C
表示數學及格的人所成的集合;那麼由題目知道


n(A)26n(B)24n(C)17
n(A∩B)
17n(A∩C)12n(B∩C)11
n(A∩B∩C)
10


排容原理:
n(A
BC)n(A)n(B)n(C)n(A∩B)n(A∩C)n(B∩C)n(A∩B∩C)


至少一科及格的人數為
26
24171712111037


也可以知道三科都不及格的有3人。


 


如果現在問說「恰好只有一科及格的人有多少?」可以用小學生就會的方法:


畫出文式圖,然後分成D1D8八個區塊,分別算出每個區塊的人數為
D7
10,得到D47D52D61
D1
7D26D34,當然D83


所求為D1D2D317


 


其實可以這麼看


D1n(A)D4D5D7
D2
n(B)D4D6
D7
D3
n(C)D5D6
D7
因此D1D2D3n(A)n(B)n(C)2 D42 D52 D63 D7


但是又有D4D7n(A∩B)D5D7n(A∩C)D6D7n(B∩C)


於是D1D2D3n(A)n(B)n(C)2×n(A∩B)2×n(A∩C)2×n(B∩C)3D7


D1D2D3n(A)n(B)n(C)2×n(A∩B)2×n(A∩C)2×n(B∩C)3×n(A∩B∩C)……………………………………


 


關於()式可以這麼解釋:
我們要算恰好只有一科及格的人,可以先將各科及格人數相加;但是兩科及格的人不需要算,他們被算了兩次,所以減去兩倍;但是三科都及格的人也不需要算,他們先被算了三次,又被減去六次,所以要加回三次才對。


這個式子,不就跟排容原理很像嗎?


重新定義符號:
給定n個集合A1A2……An,宇集合為U
S0
n(U)

S1Σi  n(Ai)
S2
Σij  n(Ai∩Aj)
S3
Σijk  n(Ai∩Aj∩Ak)


………………………………………



Sn
n(A1∩A2∩……∩An)

意思就是Sk表示所有k個集合的交集的元素個數總和。


又定義em表示恰好在m個集合中的元素個數(例如上面恰好只有一科及格的人數為e1),那麼排容原理就是


emSmC(m11)×Sm1C(m22)×Sm2C(m33)×Sm3……(1)nmC(nnm)×Sn


【證明】


計算U中每個元素在上式的左右兩邊被計算的次數相等。


<1>    如果x恰在m個集合中
在左式被算了一次;
在右式中,x會在Sm中但是不會在任何Sk(km)中,
所以也被算了一次。


<2>    如果x恰在mi個集合中
那麼它就不在em中,左式沒算到;
在右式中,它也不會在任何Sk(km)中,
所以也沒算到。


<3>    如果x恰在mj個集合中
那麼它就不在em中,左式沒算到;
在右式中,計算Sm時,會有C(mjm)個集合算到它;同樣的,
計算Sm1時,會有C(mjm+1) 個集合算到它;
也就是計算Smk時,會有C(mjm+k) 個集合算到它;
一直到計算Smj時,會有C(mjm+j) 個集合算到它;
以後計算Smkkj)就都沒有算到了。
於是在右式中,x被算了
C(m
jm)C(m11)×C(mjm+1)C(m22)×C(mjm+2)……
(1)kC(mkk)×C(mjm+k)……(1)jC(mjj)×C(mj
m+j)
接著先來變個戲法:

C(m
kk)×C(mjm+k)
[(mk)!/m!×k!]×[(mj)!/(jk)!×(m
k)!]
(mj)!/m!×k!×(j
k)!
[(mj)!/m!×j!]×[j!/k!×(j
k)!]
C(mjm)×C(j
k)
於是x被算的次數就是

C(m
jm)C(mjm)× C(j1)C(mjm)× C(j2)……
(1)kC(mjm) C(jk)……(1)jC(mjm)×C(j
j)
C(mjm)×[1C(j1)C(j2)……(1)k C(jk)……(1)j C(j
j)]
由二項式定理知道中括號裡面就是(1x)j的係數和,故為0

也就是x在右式中也沒算到。


由上討論得證排容原理。


 


以下給出三個集合的圖形,可以讓大家了解e0e1e2e3是怎麼回事。




e0S0S1S2S3


e1S12S23S3


e2S23S3


e3S3


 



 

arrow
arrow
    全站熱搜

    老王 發表在 痞客邦 留言(2) 人氣()