容斥原理4.1引言4.2容斥原理4.3應用4.4限制排列與棋盤多項式4.5反演公式

容斥原理又稱為“入與出原理”、“包含排斥原理”或“交互分類原理”.它是組合學中的一個基本計數理論.當用加法法則解決一些集合的計數問題時,一般要求將計數的集合劃分為若干個互不相交的子集,且這些子集都比較容易計數.然而,實際中又有很多計數問題要找到容易計數且又兩兩不相交的子集并非易事.但往往能夠知道某一集合的若干相交子集的計數,進而把所要求的集合中的元素個數計算出來.這一計數方法就是下面所要介紹的容斥原理.

4.1引言

關于集合的運算,有:

集合的運算,滿足下列運算定律:

當集合A中的元素為有限個時,稱A為有限集合,其元素個數記為|A|,亦稱為A的勢.關于|A|,有如下簡單性質:

(1)若集合A、B不相交,即AB=?,則|A+B|=|A|+|B|;

(2)若A?B,則|A-B|=|A|-|B|.

4.2容斥原理

引理4.2.1設A,B為有限集合,則有

證顯然,對于A+B中的元素a,在等式左邊恰被統計一次,而在等式右邊被統計的次數,可分為如下三種情形來考慮:

(1)a∈A,但a?B,則a也恰被統計一次;

(2)a?A,但a∈B,同樣恰被統計一次;

(3)a∈A且a∈B,那么必有a∈AB,從而a被統計1+1-1=1次.

所以,a在等式兩邊被統計的次數是相同的,引理4.2.1得證.

定理4.2.1(容斥原理)設A1,A2,…,An為有限集合,則

證用數學歸納法證明.

(1)當n=2時,由引理4.2.1知,結論成立.

(2)設對n-1,結論正確.即

(3)那么,對于n,有

定理4.2.3(一般公式)

一般公式也稱為約當(Jordan)公式.

證類似于定理4.2.2的證法二,只要算出S中每個恰好具有k個性質的元素,在式(4.2.6)的右端被統計一次,而對性質少于k或大于k的元素,則統計了0次,就證明了一般公式的正確性.設S中元素a具有j種性質,分三種情況予以討論:

(1)j<k,a具有的性質不到k種,顯然a沒有被統計上,因為式(4.2.6)中qk+r統計的是至少具有k+r種性質的元素(r=0,1,…,n-k);

(2)j=k,則a在q-中只出現一次,且當i>k時,a在q-中同樣不可能被統計;

在所討論的問題中,如果性質P1,P2,…,Pn是對稱的,即具有k個性質的事物的個數不依賴于這k個性質的選取,總是等于同一個數值,則稱這個值為公共數,記作Rk,例如:

容斥原理用法總結在應用容斥原理求解計數問題時,可按下列步驟進行:

(1)根據問題的實際情況,構造一個有限集S={e1,e2,…,et}和一個性質集P={P1,P2,…,Pn},Ai是S中具有性質Pi的所有元素組成的子集,問題的關鍵是構造的性質集P,要使得|A1A2…Ak|容易計算出來(k=1,2,…,n).

(2)當統計S中恰好具有k種特征的元素的個數時,將問題轉化為求S中恰好具有P中k個性質的元素個數N[k](k=0,1,2,…,n),可利用逐步淘汰原理或一般公式,即式(4.2.5)或(4.2.6).

(3)當統計S中至少具有P中一種性質的元素個數L[1]時,利用容斥原理,即式(4.2.2),或由L[1]=|S|-N[0]求得.

(4)注意|S|=N[0]+N[1]+N[2]+…+N[n],故可由此式求得S中至少具有k種特征的元素個數L[k].如k=2時,有

4.3應用

4.3.1排列組合問題

【例4.3.2】(錯排問題)本問題在研究遞推關系時已經討論過,但若利用容斥原理,則可很容易地得出同一結果.n個元素依次給以標號1,2,…,n,進行全排列,求每個元素都不在自己原來位置上的排列數.

【例4.3.3】保位問題(亦稱不動點問題或相遇問題)將原始自然排列1,2,…,n重新作成各種排列,求恰有m個元素在其原來自身位置的排列數(記作Dn[m]).

4.3.2初等數論問題

【例4.3.4】求不超過120的素數個數.

4.3.3集合的劃分

將集合劃分為若干個非空部分后,部分與部分之間可以毫無區分,也可以標上號以示區別.前者稱為無序劃分,后者稱為有序劃分.

【例4.3.6】將一個n元集劃分成r個非空子集,并且給每個子集分別標上號:1,2,…,r.試證由此得到的全部劃分方案數為

4.3.4其它應用

【例4.3.7】求完全由n個布爾變量確定的布爾函數的個數.解分析:當n=2時,兩個自變量x,y共有22=4種狀態:00,01,10,11.有24=16種不同函數,其取值情況見表4.3.1.

【例4.3.8】證明把n分成各部分不能被d所整除的剖分數等于把n劃分成每一部分不出現d次或d次以上的剖分數.

證以p(n)表示n的所有剖分數,易知n的含有數x的剖分數等于數n-x的剖分數p(n-x).因為n的任一含有x的剖分,去掉x之后,恰是n-x的一個剖分.反之,n-x的一個剖分加上x之后,恰是n的一個剖分.推廣為一般情形,n的含有x,y,z,…的剖分數等于數n-x-y-z-…的剖分數p(n-x-y-z-…).

所以,由逐步淘汰原理知

【例4.3.9】試求多重集S={5·a,5·b,∞·c}的r=11的組合數,要求組合中至少含有一個a.

解可先從S中取出一個a,然后再從a、b、c中選取10個元素,即得S的滿足條件的組合方案.因此,問題等價于求多重集{4·a,5·b,∞·c}的r=10的組合數.

構造集合S'={∞·a,∞·b,∞·c}.從S'的r=10的組合中去掉那些有多于4個a,或多于5個b的組合,便得S的10組合.

【例4.3.11】用容斥原理證明下列組合等式:

4.4限制排列與棋盤多項式

4.4.1有限制的排列

所謂有限制的排列,是指排列中對元素的排列位置加以限制.這樣的限制分兩種情形:(1)相對位置:即某些元素不能相互連在一起,如前邊的例4.3.1及下邊的例.(2)絕對位置(也稱禁位排列):指相對于原始排列中的排列順序,再次打亂順序重排時,某些元素不在其原來的位置,最典型的如錯排.

【例4.4.1】在4個x,3個y,2個z的全排列中,求不出現xxxx、yyy、zz圖像的排列數.

解設A、B、C分別為出現圖像xxxx、yyy、zz的全體排列的組成的集合,那么,按照要求,在A中可以將xxxx視為一個整體,即一個元素再與3個y和2個z進行排列,所以

【例4.4.3】舉辦一個8人參加的舞會,其中有4位先生和4位女士.每人都戴著面具,且外觀上兩兩不同.如果將面具集中后,再隨意地分發給每人一個,試求:

(1)每位先生都拿到自己的面具,而女士無一人拿到自己面具的方案數;

(2)先生們沒有一位拿到自己面具的方案數;

(3)8人中,只有4位沒有領到自己面具的方案數.

解顯見,本例是一個局部錯排問題,也是禁位排列問題.設S為所有分發方案集.

(1)由條件易知是4個元素的錯排問題,所求方案數為

(2)由于先生們的面具無一到位,而女士們的面具可能到位也可能錯位,故不能簡單套用錯位排列的計算公式.

4.4.2棋盤多項式

n個元素的某一全排列可以看作是n個棋子在一個n×n棋盤上的一種特殊布局,其特殊性在于當一個棋子放到棋盤的某一格子時,則這個格子所在的其它行和列便不能再布放其它任何棋子.例如排列3241和圖4.4.1的布局相對應.圖4.4.1棋盤布局

例如:圖4.4.2棋盤舉例

定理4.4.1

證(1)就某一格子而言,無非有兩種可能,一是對該格子布有棋子,一是不布棋子,所有的布局依此可分為兩類.右端第一項rk-1(Ci)表示某格子放有棋子,而剩下的k-1個棋子布到Ci

棋盤上的方案數.第二項rk(Ce)表示該格子不布棋子,所有k個棋子布到棋盤Ce上的方案數.兩類布法,不能同時出現,由加法法則可知,式(4.4.3)成立.

(2)由R(C)的定義和式(4.4.3),有

利用式(4.4.4)和(4.4.6),可以把一個較復雜的棋盤逐步分解為一批較簡單的棋盤,從而比較容易地得到原棋盤的多項式.例如:

4.4.3有禁區的排列

定理4.4.2

證設n元排列a1a2…an,其中ai是第i號棋子落在第i行的位置,如2314657表示第1號棋子放在第1行的2號位置(即第2列),棋子2在第2行的3號位(第3列),棋子3在第3行的1號位(第1列),…….令Pi表示第i個棋子放入禁區的性質,集合Ai表示具有性質Pi的所有布局方案集.

【例4.4.4】設有4個元素的排列,其中要求第1個元素不能排在第1個位置,第2個元素不能在1、4號位置,元素3不能在2號位置,元素4不能在3號位置.問共有多少排列方案數.

解所提排列問題對應有禁區的棋盤C(見圖4.4.3(a)),其禁區A(見圖4.4.3(b))可分離為兩個小棋盤A1和A2(見圖4.4.3(c)).

顯見

這樣的實際問題很多,如工作安排(即匹配)問題:設有A、B、C、D四位工作人員,要完成x、y、z、w四項任務,但A不適合去做事情y,B不適合做事情y、z,C不適合做z、w,D不適合做w.讀者可以試計算,若要求每人完成一項各自所適宜的任務,共有多少種分配任務的方案?圖4.4.3有禁區的排列

【例4.4.5】(錯排問題)即第i個棋子不能排在第i行的第i個位置,問題可以看作在一個n×n的棋盤上,以對角線上的方格為禁區A的布局問題,求布局方案數.

解如圖4.4.4所示,陰影部分為禁區構成的棋盤A,由式(4.4.6)知

從而必有

因此,由公式(4.4.8)可得錯排的方案數為圖4.4.4錯排問題的棋盤布局

4.5反演公式

例如,前面已經用幾種方法解決了錯排的計數問題,現在,仍以此為例,給出另一種新的解決方法.已知n個相異元素的錯排數為Dn,其中有k個元素在其原來位置(保位),其余n-k個元素都不在原來位置(錯位)的“保位問題”的排列數為Dn[k]=Ckn·Dn-k(見例4.3.3).為了求解Dn,先建立關于Dk的方程(k=1,2,…,n).

n個元素的全排列可分為以下情況:

0個元素保位,n個元素錯位;

1個元素保位,n-1個元素錯位;

2個元素保位,n-2個元素錯位;

?

n個元素保位,0個元素錯位.

4.5.1第一反演公式

【例4.5.1】(錯排問題)

4.5.2墨比烏斯(M¨obius)反演公式

定義4.5.1M¨obius函數μ(n)定義為

定理4.5.2對任意正整數n,有

其中表示讓d取遍n的所有正因子而對μ(d)求和,包括因子1和n.其中符號d|n表示d能整除n.

【例4.5.3】利用M¨obius反演公式,將n用Euler函數φ(d)表示.因為

【例4.5.4】(可重圓排列問題)從m類相異元素中可重復地