排容原理

組合數學的計數技巧,重複數算的數目要扣除

排容原理(inclusion-exclusion principle)又稱容斥原理,在組合數學裏,其說明若, ..., 有限集,則

三個集的情況

其中表示基數。例如在兩個集的情況時,我們可以通過將相加,再減去其交集的基數,而得到其併集的基數。

描述

編輯

兩個集合的容斥原理  

編輯

n(A∪B)=n(A)+n(B) -n(A∩B)

三個集合的容斥原理

編輯

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

n個集合的容斥原理

編輯

      要計算幾個集合併集的大小,我們要先將所有單個集合的大小計算出來,然後減去所有兩個集合相交的部分,再加回所有三個集合相交的部分,再減去所有四個集合相交的部分,依此類推,一直計算到所有集合相交的部分。

最終得到公式:

 

又可寫成

 

 

概率論中的容斥原理

編輯

概率論中,對於概率空間 中的事件A1,……,An,當n = 2時容斥原理的公式為:

 

n = 3時,公式為:

 

一般地:

 

也可以寫成:

 

對於一般的測度空間(S,Σ,μ)和有限測度的可測子集A1,……,An,上面的恆等式也成立,如果把概率測度 換為測度μ

特殊情況

編輯

如果在容斥原理的概率形式中,交集AI的概率只與I中元素的個數有關,也就是說,對於{1, ..., n}中的每一個k,都存在一個ak,使得:

 ,對於每一個 

則以上的公式可以簡化為:

 

這是由於二項式係數 的組合解釋。

類似地,如果對有限集合A1,……,An的併集的元素個數感興趣,且對於{1, ..., n}中的每一個k,交集

 

的元素個數都相同,例如ak = |AI|,與{1, ..., n}的k元素子集I無關,則:

 

在一般的測度空間(S,Σ,μ)和有限測度的可測子集A1,……,An的情況中,也可以進行類似的簡化。

容斥原理的證明

編輯

欲證明容斥原理,我們首先要驗證以下的關於指示函數的等式:

 

至少有兩種方法來證明這個等式:

第一種方法 我們只需證明對於A1,……,An的併集中的每一個x,等式都成立。假設x正好屬於m個集合(1 ≤ m ≤ n),不妨設它們為A1,……,Am。則x處的等式化為:

 

m元素集合中的k元素子集的個數,是二項式係數  的組合解釋。由於  ,我們有:

 

把所有的項移到等式的左端,我們便得到(1 – 1)m的二項式展開式,因此可以看出,(*)對x成立。

第二種方法A表示集合A1,……,An的併集。於是:

 

這是因為對於不在A內的x,兩邊都等於零,而如果x屬於其中一個集合,例如Am,則對應的第m個因子為零。把右端的乘積展開來,便可得到等式(*)。

歸納法證明

編輯

設:S1= n (A1)+n (A2)+n (A3) +…...+n (An)

S2= n(A1∩A2)+ n(A1∩A3) …...+ n(A1∩An)+ n(A2∩A3)+ …...+n(An-1∩An)

S3= n(A1∩A2∩A3)+ ……+ n(An-2∩An-1∩An)……

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

求證:A=n(A1∪A2∪A3∪A4……∪An)= S1-S2+ S3+……+(-1)n-1Sn

證明:當n=2時,A=n(A1∪A2)=n(A1)+n(A2) -n(A1∩ A2)= S1-S2

假設:當n=k(k>=2)時,A=n (A1∪A2∪A3∪A4……∪Ak)= S1-S2+ S3+……+(-1)k-1Sk 等式成立。

當n=k+1時,

A= n( (A1∪A2∪A3∪A4……∪Ak) ∪Ak+1)

= n (A1∪A2∪A3∪A4……∪Ak)+n(Ak+1)-n((A1∪A2∪A3∪A4……∪Ak) ∩Ak+1)

= n (A1∪A2∪A3∪A4……∪Ak) +n(Ak+1)-n((A1∩Ak+1) ∪(A2∩Ak+1) ∪(A3∩Ak+1) ∪ …∪(Ak∩Ak+1))

∵ 當n=k時,等式成立

∴A= n (A1∪A2∪A3∪A4……∪Ak) +n(Ak+1)-(n (A1∩Ak+1)+ n (A2∩Ak+1)+ ……+n(Ak∩Ak+1)-n(A1∩A2∩Ak+1)-n(A1A3∩Ak+1) -……- n(Ak-1∩Ak∩Ak+1)+ ……+(-1)k.n(A1∩A2∩A3∩∪……∩Ak+1)

   = S1-S2+ S3+……+(-1)k-1Sk+n(Ak+1)-(n (A1∩Ak+1)+ n (A2∩Ak+1)+ ……+n(Ak∩Ak+1)-n(A1∩A2∩Ak+1)-n(A1∩A3∩Ak+1) -……- n(Ak-1∩Ak∩Ak+1)+ ……+(-1)k.n(A1∩A2∩A3∩∪……∩Ak+1)

    = S1-S2+ S3+……+(-1)kSk+1

綜上所述,當n>=2時,n (A1∪A2∪A3∪A4……∪An)

= n (A1)+n (A2)+n (A3) ……+ n (An)-n(A1∩A2)- n(A1∩A3) ……- n(A1∩An)- n(A2∩A3)- ……-n(An-1∩An)+n(A1∩A2∩A3)+ n(A1∩A2∩A3)+ ……+ n(An-2∩An-1∩An)- ……+……+(-1)n-1.n(A1∩A2∩A3∩……∩An)[1]

其它形式

編輯

有時容斥原理用以下的形式來表述:如果

 

那麼:

 

在這種形式中可以看出,它是A的所有子集的偏序集合指標代數莫比烏斯反演公式

應用

編輯

在許多情況下,容斥原理都可以給出精確的公式(特別是用埃拉托斯特尼篩法計算素數的個數時),但是用處不大,這是因為它裡面含有的項太多。即使每一個單獨的項都可以準確地估計,誤差累積起來仍然意味着容斥原理不能直接應用。在數論中,這個困難由維戈·布朗解決。開始時進展很慢,但他的想法逐漸被其他數學家所應用,於是便產生了許多各種各樣的篩法。這些方法是嘗試找出被「篩選」的集合的上界,而不是一個確切的公式。

錯排

編輯

容斥原理的一個著名的應用,是計算一個有限集合的所有亂序排列的數目。一個集合A錯排,是從AA的沒有不動點的雙射。通過容斥原理,我們可以證明,如果A含有n個元素,則亂序排列的數目為[n! / e],其中[x]表示最接近x的整數。

這也稱為n子階乘,記為!n。可以推出,如果所有的雙射都有相同的概率,則當n增大時,一個隨機雙射是錯排的概率迅速趨近於1/e

交集的計算

編輯

容斥原理與德·摩根定理結合起來,也可以用於計算集合的交集中元素的數目。設 表示Ak關於全集A補集,使得對於每一個k,都有 。於是,我們有:

 

這樣便把計算交集的問題化為計算併集的問題。

參見

編輯

拓展閱讀

編輯

參考文獻

編輯
  1. ^ 容斥原理的猜测与证明_ty1108_新浪博客. blog.sina.com.cn. [2018-02-06]. (原始內容存檔於2019-08-22). 

本條目含有來自PlanetMathprinciple of inclusion-exclusion》的內容,版權遵守知識共享協議:署名-相同方式共享協議