容斥原理與鴿籠

1第七講

容斥原理與鴿籠原理《圖論與組合優(yōu)化》2一.引言●容斥原理是組合數(shù)學(xué)中的一個(gè)重要原理,它在計(jì)數(shù)問題中占有很重要地位.●容斥原理所研究的問題是與若干有限集的交、并或差有關(guān)的計(jì)數(shù).●在實(shí)際工作中,有時(shí)要計(jì)算具有某種性質(zhì)的元素個(gè)數(shù).例:

某單位舉辦一個(gè)外語(yǔ)培訓(xùn)班,開設(shè)英語(yǔ),法語(yǔ)兩門課.3●設(shè)U為該單位所有人集合,A,B分別為學(xué)英語(yǔ),法語(yǔ)人的集合,如圖所示.●學(xué)兩門外語(yǔ)的人數(shù)為|A∩B|,只學(xué)一門外語(yǔ)的人數(shù)為|A∪B|-|A∩B|,沒參加學(xué)習(xí)的人數(shù)為|U|-|A∪B|.4在一些計(jì)數(shù)問題中,經(jīng)常遇到間接計(jì)算一個(gè)集合中具有某種性質(zhì)的元素個(gè)數(shù)比起直接計(jì)算來(lái)得簡(jiǎn)單.

例:

計(jì)算1到700之間不能被7整除的整數(shù)個(gè)數(shù).直接計(jì)算相當(dāng)麻煩,間接計(jì)算非常容易.先計(jì)算1到700之間能被7整除的整數(shù)個(gè)數(shù)=700/7=100,所以1到700之間不能被7整除的整數(shù)個(gè)數(shù)=700-100=600.

5因此,當(dāng)直接求解受阻或無(wú)法達(dá)到目的時(shí),應(yīng)考慮間接求解方法.所謂“曲徑通幽”,說(shuō)的就是這個(gè)道理.上面舉的間接計(jì)數(shù)的例子是利用了如下原理：如果A是集合S的子集,則A中的元素個(gè)數(shù)等于S中的元素個(gè)數(shù)減去不在A中的元素個(gè)數(shù),這個(gè)原理可寫成6●我們的目的并不僅僅是討論這樣一個(gè)簡(jiǎn)單的原理,而是討論這個(gè)原理的一個(gè)重要推廣,稱之為容斥原理,并且將它運(yùn)用到若干問題上去,其中包括：

錯(cuò)位排列、有限制的排列、禁位排列和棋陣多項(xiàng)式等.7DeMorgan定理:

設(shè)A,B為全集U的任意兩個(gè)子集,則DeMorgan定理的推廣:

設(shè)A1,A2,,An為U的子集,則二.容斥原理81.兩個(gè)集合的容斥原理

設(shè)A和B是分別具有性質(zhì)P1和P2的元素的集合,則例6.1求1到500之間能被5或7整除的正整數(shù)個(gè)數(shù).解設(shè)A為被5整除的整數(shù)集合,B為被7整除的整數(shù)集合,用[x]表示x的整數(shù)部分,則有9同時(shí)被5和7整除的整數(shù)個(gè)數(shù)故能被5或7整除的整數(shù)個(gè)數(shù)102.三個(gè)集合上的容斥原理設(shè)A,B,C為任意三個(gè)集合,則有3.n個(gè)集合上的容斥原理:

設(shè)A1,A2,…,An是有限集合,則有114.

容斥原理的余集形式12例求在1到10000的整數(shù)中不能被4,5,6整除的數(shù)的個(gè)數(shù).解：令A(yù)i(i=4,5,6)表示1到10000的整數(shù)中能被i整除的數(shù)的全體，則13例子：把6個(gè)不同的球放入3個(gè)不同的盒子，且不允許空盒.有多少種方法？14三.容斥原理的應(yīng)用實(shí)例1.錯(cuò)排問題上一講利用遞歸關(guān)系討論了錯(cuò)排問題.現(xiàn)在利用容斥原理再次討論這個(gè)問題.可以看出容斥原理解決這個(gè)問題更容易,而且利用容斥原理很容易理解錯(cuò)排數(shù)列通項(xiàng)公式的組合意義.我們?cè)僦厣暌幌?排列i1i2…in是排列12…n的一個(gè)錯(cuò)排當(dāng)且僅當(dāng)i1≠1,i2≠2,…,in≠n.15我們?cè)?2…n全部不同錯(cuò)排的數(shù)目記為Dn.當(dāng)時(shí)得到的結(jié)論如下.可以用容斥原理證明:

設(shè)S={1,2,3,…,n},S0為S的所有n!個(gè)排列的集合.令A(yù)j表示排列12…n中使j位置上的元素恰好是j的排列的集合,j=1,2,…,n.則排列12…n的所有錯(cuò)位排列組成集合:16|Aj|=(n-1)!,j=1,2,3,…,n.|Ai∩Aj|=(n-2)!,i,j=1,2,3,…,n,但i≠j.對(duì)于任意整數(shù)k且1≤k≤n,則有因?yàn)閧1,2,3,…,n}的k組合為C(n,k)個(gè),應(yīng)用容斥原理得到:1718例小王要為公司審閱7本書，于是他雇了7個(gè)人來(lái)審閱它們。他希望每本書有兩個(gè)審閱者，于是在第一個(gè)星期，他給每人一本書來(lái)審閱，接著在第二個(gè)星期開始重新分配。一共有多少種方式可以完成這兩次分配，使得每本書有兩個(gè)不同的審閱者？解滿足要求的分配方式有7!D7=(7!)2(1-1+(1/2!)-(1/3!)+…+(1/7!))19解5!D5=(5!)

(1-1+(1/2!)-(1/3!)+(1/4!)-(1/5!))202.有限制的排列所謂有限制的排列,顧名思義,就是對(duì)排列加上某種或某些限制.例6.2

求字母a,b,c,d,e,f和g具有下列性質(zhì)的排列個(gè)數(shù)：在這些排列中,模式ace和df都不出現(xiàn).解設(shè)A1,A2分別為出現(xiàn)模式ace和模式df的排列的集合,則有

|A1|=5!(=ace,A1為,b,d,f,g的排列);|A2|=6!(=df,A2為,a,b,c,e,g的排列);21|A1∩A2|=4!(A1∩A2為,,b,g的全部排列).

由容斥原理,模式ace和模式df都不出現(xiàn)的排列個(gè)數(shù)為:223.相對(duì)禁位排列在錯(cuò)排問題中,每個(gè)元素不許出現(xiàn)在原來(lái)的位置,這是一種絕對(duì)的禁位排列.還有一類是相對(duì)禁位排列.例6.3

有5個(gè)學(xué)生每天要排成一列去散步.除第一個(gè)學(xué)生之外,每個(gè)學(xué)生前面都有一個(gè)學(xué)生.

每天都是同一個(gè)人在自己前面走顯得單調(diào),第2天他們決定改變排隊(duì)次序,使得每個(gè)同學(xué)前面的人與第1天不同.問有多少種不同的排隊(duì)方式?23分析:

如果把第1天排隊(duì)的同學(xué)按次序編號(hào)為1,2,3,4,5.我們所要求的排列為其中不出現(xiàn)模式12,23,34,45的全部排列.31425是一個(gè)符合要求的排列,而25341不符合要求.因?yàn)槌霈F(xiàn)的34模式.這個(gè)問題可以利用容斥原理來(lái)解決.設(shè)Ai表示出現(xiàn)i(i+1)模式的全體排列,i=1,2,3,4.符合要求的排列是這些模式都不出現(xiàn).用Q5來(lái)表示符合要求的排列總數(shù).24容易計(jì)算出:

|Ai|=4!,i=1,2,3,4.|A1∩A2|中排列含有模式123,其中排列的總數(shù)={123,4,5}排列總數(shù).所以,

|A1∩A2|=(5-2)!=3!類似有:|Ai∩Ai+1|=(5-2)=3!,i=2,3.25|Ai∩Aj|(j>i+1)中的排列包含有i(i+1),j(j+1),這樣總數(shù)等于這兩個(gè)模式和其余5-4=1個(gè)數(shù)的排列數(shù)目=3!

類似的分析可以得到:|Ai∩Aj

∩Ak|=(5-3)!=2!,|A1∩A2

∩A3∩A4|=(5-4)!=1.26這個(gè)問題可推廣到一般情形:274.歐拉函數(shù)歐拉函數(shù)

表示小于n且與n互素的正整數(shù)的個(gè)數(shù).可利用容斥原理給出其計(jì)算公式.可設(shè)n可分解為不同的素?cái)?shù)p1,p2,…,pk之積：

令A(yù)i表示N={1,2,…,n}中能被pi整除的數(shù)的集合,i=1,2,…,k.則|Ai|=n/pi,i=1,2,…,k.

由于當(dāng)i≠j

時(shí)pi≠pj,故28295.棋盤多項(xiàng)式*棋盤布局問題:

設(shè)有一個(gè)棋盤C,如果能把k個(gè)棋子布在棋盤上,使得每行每列至多有一個(gè)棋子,也就是說(shuō)當(dāng)一個(gè)棋子置于棋盤的某一格時(shí),這一格子所在的行和列都不能再布其他任何棋子.這樣的一個(gè)布局則稱為棋盤C的一個(gè)k-布局,用rk(C)表示棋盤C不同k-布局的總數(shù).30(2)需要注意的問題:棋盤C不一定是規(guī)則的,如果C有m行,n列,則C可以看作是m×n標(biāo)準(zhǔn)棋盤的一個(gè)殘棋盤.rk(C)=0當(dāng)且僅當(dāng)C不存在k-布局.比如當(dāng)k>min{m,n}時(shí)候,rk(C)=0.由于棋盤的布局?jǐn)?shù)關(guān)于棋盤的轉(zhuǎn)置是不變的,從理論上來(lái)講,可以假定所討論的棋盤恒滿足m≥n.約定r0(C)=1.31例6.3設(shè)C是一個(gè)5×5棋盤,那么C的一個(gè)5-布局相當(dāng)于{1,2,3,4,5}的一個(gè)排列.如下圖所示的布局:第1行的棋子在第4列,第2行的棋子在第1列,第3行的棋子在第3列,第4行的棋子在第5列,第5行的棋子在第2列,故所對(duì)應(yīng)的排列:41352.

32顯然r5(C)=5!.由此可見,規(guī)則的棋盤布局問題應(yīng)該是容易解決的,總可以化為無(wú)重復(fù)排列問題.但是任意形狀的殘棋盤的布局問題比較復(fù)雜.例如下面形狀的棋盤:可以建立棋盤的矩陣表示,用(0,1)矩陣來(lái)表示一個(gè)棋盤.方法如下:33設(shè)C是一個(gè)m行,n列但形狀任意的棋盤,則C可看作是m×n完整棋盤的一個(gè)殘棋盤.可以用一個(gè)m×n階的(0,1)矩陣來(lái)表示.有格子的位置元素為1,無(wú)格子的地方元素為0,這樣所得到的矩陣稱為棋盤C的關(guān)聯(lián)矩陣,記為A(C).關(guān)聯(lián)矩陣為34棋盤與關(guān)聯(lián)矩陣互相唯一確定.如果把位于同一行或同一列的元素稱為“共線”,則棋盤C的一個(gè)k-布局對(duì)應(yīng)其關(guān)聯(lián)A的k個(gè)兩兩不共線的非零元素組(實(shí)質(zhì)上就是k個(gè)不共線的1).這樣rk(C)=關(guān)聯(lián)矩陣A中非零且兩兩不共線的k-元組的個(gè)數(shù).

下面看一些特殊情況:r1(1,1)=2:35但r2(1,1)=0.(3)棋盤多項(xiàng)式(母函數(shù)):

對(duì)于給定的棋盤C,稱多項(xiàng)式為棋盤C的棋盤多項(xiàng)式,其中:

n=min{C的行數(shù),C的列數(shù)}.

36設(shè)棋盤C在(i,j)位置有一個(gè)格子,用Cij表示把這個(gè)格子所在的行和列中的格子都去掉后余下的格子所構(gòu)成的棋盤,這時(shí)相應(yīng)的關(guān)聯(lián)矩陣A(Cij)相當(dāng)于A(C)中(i,j)-元素的余子陣.這時(shí)Cij的行數(shù)和列數(shù)都減少了1.設(shè)棋盤C在(i,j)位置有一個(gè)格子,用Dij表示把這個(gè)格子去掉余下的格子所構(gòu)成的棋盤,這時(shí)關(guān)聯(lián)矩陣A(Dij)相當(dāng)于把A(C)中(i,j)位置上的1變?yōu)?.37對(duì)棋盤進(jìn)行這樣的“手術(shù)”目的是把計(jì)算rk(C)的問題進(jìn)行降階.下面用具體例子演示一下手術(shù)過(guò)程:先用形象的棋盤形式:C:關(guān)于蘭色格子的手術(shù)有C11和D11如下:C11:D11:38虛線表示從原棋盤中去掉的部分.如果采用關(guān)聯(lián)矩陣:039假設(shè)選定了具體的格子(i,j),那么全部rk(C)個(gè)k-布局可以分成兩類:第一類:

其中包含(i,j)格,這類k-布局的總數(shù)=rk-1(Cij);第二類:

其中不包含(i,j)格,這類k-布局的總數(shù)=rk(Dij);由加法原理和棋盤多項(xiàng)式定義得到:

rk(C)=rk-1(Cij)+rk(Dij)(6.2)R(C)=xR(Cij)+R(Dij)(6.3)40例如,R(1)=r0(1)+r1(1)x=1+xR(1,1)=xR(0)+R(1)=x+(1+x)=1+2x利用(6.2),(6.3)可以把任何復(fù)雜的棋盤多項(xiàng)式的計(jì)算逐步分解為相對(duì)比較簡(jiǎn)單的棋盤的多項(xiàng)式計(jì)算.41看一些簡(jiǎn)單棋盤多項(xiàng)式的計(jì)算:4243一種結(jié)構(gòu)分離的棋盤棋盤多項(xiàng)式計(jì)算.若棋盤C是由互相分離的兩部分C1和C2組成,這里所說(shuō)的C1和C2兩棋盤互相分離,指的是它們沒有共同的行或列.一個(gè)棋盤為結(jié)構(gòu)分離棋盤當(dāng)且僅當(dāng)其其對(duì)應(yīng)的關(guān)聯(lián)矩陣為如下形式:

44這時(shí)C的棋盤多項(xiàng)式的計(jì)算可以化為其兩個(gè)分離塊C1,C2棋盤多項(xiàng)式計(jì)算:所以:R(C)=R(C1)R(C2).(6.4)456.禁位排列*所謂“禁位排列”,是指在一個(gè)排列中禁止某些元素占據(jù)某些位置.錯(cuò)排是禁位排列的一種特殊情況.例6.4

有張、王、李、趙四位教師,有數(shù)學(xué)、物理、化學(xué)、英語(yǔ)四門課程.已知張不能教物理,王不能教物理和化學(xué),李不能教化學(xué)和英語(yǔ),趙不能教英語(yǔ).若使每位教師教各自承擔(dān)力所能及的一門課程,問有多少種安排方案？46下面是例6.4所對(duì)應(yīng)棋盤,行分別表示張,王,李,趙四位老師,列分別表示數(shù),理,化,英四門課程,問題就是決定不進(jìn)入陰影部分的4-布局的個(gè)數(shù):張王李趙數(shù)理化英47這就是一個(gè)禁位排列的問題.我們的目的是計(jì)算禁位排列的個(gè)數(shù).這個(gè)問題可以利用容斥原理化為棋盤布局問題來(lái)解決.我們討論一般情況.定理設(shè)有n個(gè)棋子布入n×n的棋盤,則有禁位的排列數(shù)為

Qn=n!-r1×(n-1)!+r2×(n-2)!-…

+(-1)n-1

rn-1×1!+(-1)n

rn×0!

其中ri為有i個(gè)棋子落入禁區(qū)的方案數(shù).

48證.

設(shè)Ai為第i個(gè)棋子落入禁區(qū)的排列的集合,i=1,2,…,n如果一個(gè)棋子落入禁區(qū)的方案數(shù)目為

r1,那么剩下的n-1個(gè)棋子可任意排列,所以:∑|Ai|=r1×(n-1)!.如果兩個(gè)棋子落入禁區(qū)的方案數(shù)目為

r2,那么剩下的n-2個(gè)棋子可任意排列,所以:∑|Ai∩Aj|=r2×(n-2)!.

依次類推.由容斥原理,可以得到:49由此可見,計(jì)算禁位排列的關(guān)鍵問題是計(jì)算ri(i=1,2,…,n).而ri(i=1,2,…,n)正好是禁位所組成的殘棋盤C的i-布局?jǐn)?shù)ri(C).這樣就可以利用棋盤多項(xiàng)式來(lái)計(jì)算.(6.5)50下面是例6.4所對(duì)應(yīng)棋盤,行分別表示張,王,李,趙四位老師,列分別表示數(shù),理,化,英四門課程,問題就是決定不進(jìn)入陰影部分的4-布局的個(gè)數(shù):張王李趙數(shù)理化英51解這個(gè)問題實(shí)際上是有禁位的排列,其禁區(qū)就是剛才圖中的陰影部分.由上面的計(jì)算知道圖6.5中的禁區(qū)棋盤多項(xiàng)式為1+6x+10x2+4x3

故有r1=6,r2=10,r3=4,r4=0.

因此,由公式(6.5),所求安排方案數(shù)為:Q4=4!-6×3!+10×2!-4=4.52例有紅色和綠色的一對(duì)骰子，拋擲這對(duì)骰子6次，假設(shè)已知有序?qū)?1,2),(2,1),(2,5),(3,4),(4,1),(4,5)和(6,6)不會(huì)出現(xiàn)，求6次拋擲后，紅色和綠色骰子都擲出所有6個(gè)點(diǎn)數(shù)的拋擲種數(shù)a。解：構(gòu)造棋盤如下，其中行表示紅色骰子上的輸出，列表示綠色骰子上的輸出4353設(shè)Ai為拋擲骰子6次后，6個(gè)點(diǎn)數(shù)都出現(xiàn)在紅色骰子和綠色骰子上，但紅色骰子上的點(diǎn)數(shù)為i時(shí)，其對(duì)應(yīng)的綠色骰子上的點(diǎn)數(shù)為一個(gè)禁用數(shù)字。則54II.鴿巢原理定理1

若有n+1只鴿子飛回n個(gè)鴿巢,則至少有兩只鴿子飛入了同一個(gè)鴿巢.這個(gè)原理的證明非常容易,只要使用反證法馬上就可以得到結(jié)論.這個(gè)原理也可以表述為:

如果把n+1件東西放入n個(gè)盒子中,則至少有一個(gè)盒子里面有不少于兩件的東西.

55鴿巢原理不能用來(lái)尋找究竟是哪個(gè)盒子含有兩件或更多件東西.該原理只能證明某種安排或某種現(xiàn)象存在,而并未指出怎樣構(gòu)造這種安排或怎樣尋找這種現(xiàn)象出現(xiàn)的場(chǎng)合.從鴿巢原理出發(fā),對(duì)于許多實(shí)際問題,我們可以導(dǎo)出非常有趣的結(jié)果.利用鴿巢原理解決實(shí)際問題的關(guān)鍵是要看出這是一個(gè)鴿巢問題,建立“鴿巢”，尋找“鴿子”.56例1.

如果有13個(gè)人，則其中必然有兩個(gè)人出生在同一個(gè)月.例2.

如果鞋架上放10雙鞋,從中任意取11只,其中至少有兩只恰好是配對(duì)的.例3.

從整數(shù)1,2,…,100中任選51個(gè)數(shù),證明在所選的數(shù)中間必然存在兩個(gè)整數(shù),其中之一可以被另一個(gè)整除.證明對(duì)于任何一個(gè)整數(shù)x,總可以把x寫成x=2n×a形式,其中a是奇數(shù),n≥0.

571到100之間一共有50個(gè)奇數(shù),由所選的51個(gè)數(shù)利用上述方式可以得到51個(gè)奇數(shù),其中必然有兩個(gè)相同,設(shè)這兩個(gè)數(shù)為:x=2ra,y=2sa,如果rs,那么x|y;

如果r>s,

那么y|x.

本例中:鴿子=去掉2因子得到的奇數(shù);

鴿巢=1到100之間奇數(shù).這個(gè)例子可以推廣到從1,2,…,2n中任意取n+1個(gè)數(shù),其中必然存在兩個(gè)數(shù),其中一個(gè)整除另外一個(gè),證法類似.58例4.

在一個(gè)邊長(zhǎng)為1的正三角形中任意取5個(gè)點(diǎn),必然有兩個(gè)點(diǎn)之間距離不超過(guò)1/2.在邊長(zhǎng)為1的正六邊形中,任意選取7個(gè)點(diǎn),必然有兩個(gè)點(diǎn)之間的距離不超過(guò)1.只要通過(guò)畫圖,找出相應(yīng)的鴿子和鴿巢就可以解決問題.利用鴿巢原理解決問題的關(guān)鍵在于:

辨認(rèn)問題,建立鴿巢,尋找鴿子.59例5

在{1,2,…,2n}中任取n+2個(gè)數(shù)，其中必有兩個(gè)數(shù)，其和為2n。解：鴿子為集合中的元素，鴿巢為例6

任取11個(gè)正整數(shù)，其中必有兩個(gè)數(shù)，其差被10整除。解：鴿巢為60例7

一人參加某類競(jìng)賽，要求在11周內(nèi)每天至少安排賽一次，每周比賽不能超過(guò)12次，證明：無(wú)論如何安排，必存在相繼的若干天中比賽21次。證明：設(shè)第i天賽ai次，Si為前i天比賽的總次數(shù)，即且而所以存在k和l(k<l)，使得Sl=Sk+21于是Sl-Sk=ak+1+…+al=21即相繼的若干天中比賽了21次。61III.一般形式鴿巢原理定理2

設(shè)m1,m2,…,mn均為正整數(shù),如果有m1+m2+…+mn-n+1只鴿子飛回n個(gè)鴿巢,則或者第1個(gè)鴿巢至少有m1只鴿子,或者第2個(gè)鴿巢至少有m2只鴿子,…,或者第n個(gè)鴿巢至少有mn只鴿證明用反證法.假若第1鴿巢少于m1只鴿子,第2鴿巢少于m2個(gè)鴿子,…,第n鴿巢少于mn只鴿子,則鴿子總數(shù)至多為:(m1-1)+(m2-1)+…+(mn-1)=m1+m2+…+mn-n,這比假定的鴿子數(shù)少了一個(gè),矛盾.

62從定理2可得出以下推論：推論1

如果m1=m2=…=mn=r,即若將n(r-1)+1個(gè)球放入n個(gè)盒子中,則至少有一個(gè)盒子含有不少于r個(gè)球.推論2

如果n個(gè)正整數(shù)m1,m2,…,mn的平均數(shù)(m1+m2+…+mn)/n>r-1,則m1,m2,…,mn中至少有一個(gè)正整數(shù)不會(huì)小于r.推論3

有m個(gè)球放入n個(gè)盒子,則至少有一個(gè)盒子中有不少于[(