5、組合數(shù)學(xué)之容斥原理

1、1,《組合數(shù)學(xué)》,第六講,,,,容斥原理,2,一. 引言,●容斥原理是組合數(shù)學(xué)中的一個(gè)重要 原理,它在計(jì)數(shù)問題中占有很重要地位. ●容斥原理所研究的問題是與若干有 限集的交、并或差有關(guān)的計(jì)數(shù). ●在實(shí)際工作中, 有時(shí)要計(jì)算具有某種 性質(zhì)的元素個(gè)數(shù). 例: 某單位舉辦一個(gè)外語培訓(xùn)班, 開設(shè)英語, 法語兩門課.,3,,●設(shè)U為該單位所有人集合, A,B分別為 學(xué)英語, 法語人的集合, 如圖所示.,●學(xué)

2、兩門外語的人數(shù)為|A?B|, 只學(xué)一門外語的人數(shù)為|A?B|-|A?B|, 沒參加學(xué)習(xí)的人數(shù)為|U|-|A?B|.,4,在一些計(jì)數(shù)問題中, 經(jīng)常遇到間接計(jì)算一個(gè)集合中具有某種性質(zhì)的元素個(gè)數(shù)比起直接計(jì)算來得簡單. 例: 計(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

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

4、、禁位排列和棋陣多項(xiàng)式等.,,7,DeMorgan定理: 設(shè)A, B為全集U的任意兩個(gè)子集, 則,DeMorgan定理的推廣: 設(shè)A1,A2,?,An為U的子集, 則,二. 容斥原理,,,,,8,1. 兩個(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,

5、同時(shí)被5和7整除的整數(shù)個(gè)數(shù),,,故能被5或7整除的整數(shù)個(gè)數(shù),,,10,,,2. 三個(gè)集合上的容斥原理設(shè)A, B, C為任意三個(gè)集合, 則有,,3. n個(gè)集合上的容斥原理: 設(shè)A1,A2,?,An是有限集合, 則有,,11,4. 容斥原理的余集形式,,12,例求在1到10000的整數(shù)中不能被4,5,6整除的數(shù)的個(gè)數(shù).,解：令A(yù)i(i=4,5,6)表示1到10000的整數(shù)中能被i整 除的數(shù)的個(gè)數(shù)，則,13,例

6、 n個(gè)不同的球分放m個(gè)不同的盒子里，每盒不空，求分放總數(shù)f(n,m).,解：以X記所有無約束條件的放球方法 記Ai為第i盒空的放法全體，則,14,第二類Stirling數(shù)的展開式,第二類Stirling數(shù)：把 n個(gè)有區(qū)別的球放到k個(gè)相同的盒子中, 要求無空盒, 其方案數(shù)為S(n,k).,則 f(n, k)=k!S(n, k),所以,15,*夫妻圍坐問題：n對夫妻圍坐在一圓桌邊，圓桌邊有2n個(gè)座位，則滿足男

7、女相間，夫妻不相鄰的入座方法數(shù)為：,（座位不編號(hào)）,（座位編號(hào)）,16,證明：首先讓女賓入座，每兩個(gè)女賓之間留下一個(gè)空位，其入座方法數(shù)為(n-1)!，然后讓男賓入座，其入座方法數(shù)記為Un，把女賓依順時(shí)針方向自1至n編號(hào)，第i號(hào)女賓的丈夫編為第i號(hào)，為i號(hào)男賓；i號(hào)女賓的左手空位編號(hào)為i號(hào)座位。令,A1：1號(hào)男賓坐在n號(hào)座位,A2i-1：i號(hào)男賓坐在i-1號(hào)座位；i=2,3,…,n,A2i：i號(hào)男賓坐在i號(hào)座位；i=1,2,…

8、,n,17,|Ai|=(n-1)!,因此，如i1,i2,…,ik在園排列(1,2,…,2n,1)中若有相鄰者，則Ai1∩Ai2∩…∩Aik=Φ，否則,18,所以,從(1,2,…,2n,1)中取k個(gè)，兩兩不相鄰的取法個(gè)數(shù)為,19,三. 容斥原理的應(yīng)用實(shí)例1. 錯(cuò)排問題上一講利用遞歸關(guān)系討論了錯(cuò)排問題. 現(xiàn)在利用容斥原理再次討論這個(gè)問題.可以看出容斥原理解決這個(gè)問題更容易, 而且利用容斥原理很容易理解錯(cuò)排數(shù)列通項(xiàng)公式的組合意義.

9、我們再重申一下, 排列i1i2?in是排列12?n的一個(gè)錯(cuò)排當(dāng)且僅當(dāng)i1?1, i2?2, ?, in?n.,20,我們曾把12…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ò)位排列組成集合:,,21,?Aj?=(n-1)

10、!, j=1,2,3,?,n.?Ai?Aj?=(n-2)!, i,j=1,2,3,?,n, 但i?j. 對于任意整數(shù)k且1?k?n, 則有,因?yàn)閧1,2,3,?,n}的k組合為C(n,k)個(gè), 應(yīng)用容斥原理得到:,,22,,23,例 小王要為公司審閱7本書，于是他雇了7個(gè)人來審閱它們。他希望每本書有兩個(gè)審閱者，于是在第一個(gè)星期，他給每人一本書來審閱，接著在第二個(gè)星期開始重新分配。一共有多少種方式可以完成這兩次分配，使

11、得每本書有兩個(gè)不同的審閱者？,解 滿足要求的分配方式有,7!D7=(7!)2(1-1+(1/2!)-(1/3!)+…+(1/7!)),24,2. 有限制的排列 所謂有限制的排列, 顧名思義, 就是對排列加上某種或某些限制. 例6.2 求字母a,b,c,d,e,f和g具有下列性質(zhì)的排列個(gè)數(shù)：在這些排列中, 模式ace和df都不出現(xiàn). 解 設(shè)A1, A2分別為出現(xiàn)模式ace和模式df的排列的集合, 則有 |A1|

12、=5! (?=ace, A1為?, b,d,f,g的排列); |A2|=6! (?= df, A2為?, a,b,c,e,g的排列);,25,|A1?A2|=4! ( A1?A2為 ?, ?, b, g的全部排列). 由容斥原理, 模式ace和模式df都不出現(xiàn)的排列個(gè)數(shù)為:,,26,3. 相對禁位排列在錯(cuò)排問題中,每個(gè)元素不許出現(xiàn)在原來的位置, 這是一種絕對的禁位排列. 還有一類是相對禁位排列.例6.3

13、 有5個(gè)學(xué)生每天要排成一列去散步. 除第一個(gè)學(xué)生之外, 每個(gè)學(xué)生前面都有一個(gè)學(xué)生. 每天都是同一個(gè)人在自己前面走顯得單調(diào),第2天他們決定改變排隊(duì)次序, 使得每個(gè)同學(xué)前面的人與第1天不同. 問有多少種不同的排隊(duì)方式?,,,27,分析: 如果把第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模

14、式. 這個(gè)問題可以利用容斥原理來解決.設(shè)Ai表示出現(xiàn)i(i+1)模式的全體排列, i=1,2,3,4. 符合要求的排列是這些模式都不出現(xiàn). 用Q5來表示符合要求的排列總數(shù).,,28,容易計(jì)算出: |Ai|=4!, i=1,2,3,4.|A1?A2|中排列含有模式123, 其中排列的總數(shù)={123,4,5}排列總數(shù). 所以, |A1?A2| =(5-2)!=3

15、!類似有: |Ai?Ai+1|=(5-2)=3!, i=2,3.,,,,29,|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.,,,,,30,

16、這個(gè)問題可推廣到一般情形:,,31,4. 歐拉函數(shù)歐拉函數(shù)?(n)表示小于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, 故,,32,,,,33,5. 棋盤多項(xiàng)式*棋盤布局問題: 設(shè)有一個(gè)棋

17、盤C, 如果能把k個(gè)棋子布在棋盤上, 使得每行每列至多有一個(gè)棋子, 也就是說當(dāng)一個(gè)棋子置于棋盤的某一格時(shí), 這一格子所在的行和列都不能再布其他任何棋子. 這樣的一個(gè)布局則稱為棋盤C的一個(gè)k-布局, 用rk(C)表示棋盤C不同k-布局的總數(shù).,34,(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,

18、n}時(shí)候, rk(C)=0.由于棋盤的布局?jǐn)?shù)關(guān)于棋盤的轉(zhuǎn)置是不變的, 從理論上來講, 可以假定所討論的棋盤恒滿足m?n. 約定r0(C)=1.,35,例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列, 故所對應(yīng)的排列: 41352.,,36,顯然r5(

19、C)=5!. 由此可見, 規(guī)則的棋盤布局問題應(yīng)該是容易解決的, 總可以化為無重復(fù)排列問題. 但是任意形狀的殘棋盤的布局問題比較復(fù)雜. 例如下面形狀的棋盤:,,,,,,,,,,,,,可以建立棋盤的矩陣表示, 用(0,1)矩陣來表示一個(gè)棋盤. 方法如下:,37,設(shè)C是一個(gè)m行, n列但形狀任意的棋盤, 則C可看作是m?n完整棋盤的一個(gè)殘棋盤.可以用一個(gè)m?n階的(0,1)矩陣來表示. 有格子的位置元素為1, 無格子的地方元素為0,

20、 這樣所得到的矩陣稱為棋盤C的關(guān)聯(lián)矩陣, 記為A(C).,,,,,,,,,,,,,,關(guān)聯(lián)矩陣為,,38,棋盤與關(guān)聯(lián)矩陣互相唯一確定. 如果把位于同一行或同一列的元素稱為“共線”, 則棋盤C的一個(gè)k-布局對應(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:,,,,,,39,但 r2(1,1)=0.,,,(3)

21、 棋盤多項(xiàng)式(母函數(shù)): 對于給定的棋盤C, 稱多項(xiàng)式,,,為棋盤C的棋盤多項(xiàng)式, 其中: n=min{C的行數(shù), C的列數(shù)}.,40,設(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表示

22、把這個(gè)格子去掉余下的格子所構(gòu)成的棋盤, 這時(shí)關(guān)聯(lián)矩陣A(Dij)相當(dāng)于把A(C)中(i, j)位置上的1變?yōu)?.,,41,對棋盤進(jìn)行這樣的“手術(shù)”目的是把計(jì)算rk(C)的問題進(jìn)行降階. 下面用具體例子演示一下手術(shù)過程:先用形象的棋盤形式:,,C:,關(guān)于蘭色格子的手術(shù)有C11和D11如下:,,,,,,,,,,,,,,,,C11:,D11:,42,虛線表示從原棋盤中去掉的部分. 如果采用關(guān)聯(lián)矩陣:,,,,,,0,43,假設(shè)選定了具體

23、的格子(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.

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

25、矩陣為如下形式:,,,,46,這時(shí)C的棋盤多項(xiàng)式的計(jì)算可以化為其兩個(gè)分離塊C1, C2棋盤多項(xiàng)式計(jì)算:,,,所以: R(C)=R(C1)?R(C2). (6.4),47,看一些簡單棋盤多項(xiàng)式的計(jì)算:,,,48,,,49,6. 禁位排列所謂“禁位排列”, 是指在一個(gè)排列中禁止某些元素占據(jù)某些位置. 錯(cuò)排是禁位排列的一種特殊情況. 例6.4 有張、王、李、趙四位教師, 有數(shù)學(xué)、物理、化學(xué)、英語四門

26、課程. 已知張不能教物理, 王不能教物理和化學(xué), 李不能教化學(xué)和英語, 趙不能教英語. 若使每位教師教各自承擔(dān)力所能及的一門課程, 問有多少種安排方案？,50,這就是一個(gè)禁位排列的問題. 我們的目的是計(jì)算禁位排列的個(gè)數(shù).這個(gè)問題可以利用容斥原理化為棋盤布局問題來解決. 我們討論一般情況.定理 設(shè)有n個(gè)棋子布入n?n的棋盤, 則有禁位的排列數(shù)為 Qn=n!-r1?(n-1)!+r2?(n-2)!-? +

27、(-1)n-1 rn-1?1! +(-1)n rn?0! 其中ri為有i個(gè)棋子落入禁區(qū)的方案數(shù).,51,證. 設(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)!.

28、 依次類推. 由容斥原理, 可以得到:,52,由此可見, 計(jì)算禁位排列的關(guān)鍵問題是計(jì)算ri(i=1,2,…,n). 而ri(i=1,2,…,n)正好是禁位所組成的殘棋盤C的i-布局?jǐn)?shù)ri(C).這樣就可以利用棋盤多項(xiàng)式來計(jì)算.,,(6.5),53,下面是例6.4所對應(yīng)棋盤, 行分別表示張,王,李,趙四位老師, 列分別表示數(shù),理,化,英四門課程, 問題就是決定不進(jìn)入陰影部分的4-布局的個(gè)數(shù):,張,王,李,趙,數(shù),理,化,英,54,解

29、 這個(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.,55,例 有紅色和綠色的一對骰子，拋擲這對骰子6次，假設(shè)已知有序?qū)?1,

30、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)造棋盤如下，其中行表示紅色骰子上的輸出，列表示綠色骰子上的輸出,,,,,,,,,,,56,設(shè)Ai為拋擲骰子6次后，6個(gè)點(diǎn)數(shù)都出現(xiàn)在紅色骰子和綠色骰子上，但紅色骰子上的點(diǎn)數(shù)為i時(shí)，其對應(yīng)的綠色骰子上的點(diǎn)數(shù)為一個(gè)禁用數(shù)字。則,57,四. 課后學(xué)習(xí)任務(wù),預(yù)習(xí): 有關(guān)反演的內(nèi)容