容斥原理

容斥原理

計算結果既無遺漏又無重複的計數方法
在計數時,必須注意無一重複,無一遺漏。[1]為了使重疊部分不被重複計算,人們研究出一種新的計數方法,這種方法的基本思想是:先不考慮重疊的情況,把包含于某内容中的所有對象的數目先計算出來,然後再把計數時重複計算的數目排斥出去,使得計算的結果既無遺漏又無重複,這種計數的方法稱為容斥原理。[2]
  • 中文名:容斥原理
  • 外文名:Principle of inclusion-exclusion
  • 别名:
  • 表達式:
  • 提出者:
  • 适用領域:
  • 别稱:排容原理
  • 應用學科:組合數學、計算機
  • 拼音:rong chi yuan li

公式

也可表示為設S為有限集,則兩個集合的容斥關系公式: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。

嚴格證明

對于容斥原理我們可以利用數學歸納法證明:

證明:當時,等式成立(證明略)。

假設時結論成立,則當時,

所以當時,結論仍成立。因此對任意,均可使所證等式成立。

解釋

如果被計數的事物有A、B兩類,那麼,A類B類元素個數總和= 屬于A類元素個數+ 屬于B類元素個數—既是A類又是B類的元素個數。(A∪B = A+B - A∩B)。

例1、一次期末考試,某班有15人數學得滿分,有12人語文得滿分,并且有4人語、數都是滿分,那麼這個班至少有一門得滿分的同學有多少人?

分析。

依題意,被計數的事物有語、數得滿分兩類,“數學得滿分”稱為“A類元素”,“語文得滿分”稱為“B類元素”,“語、數都是滿分”稱為“既是A類又是B類的元素”,“至少有一門得滿分的同學”稱為“A類和B類元素個數”的總和。

答案:

15+12-4=23。

上一篇:一筆畫問題

下一篇:金絲鐵線

相關詞條

相關搜索

其它詞條