1、第三章 容斥原理與鴿巢原理1第三章 容斥原理與鴿巢原理ABAB容斥原理Inclusion and Exclusion Principle計數(shù)時重疊部分不能被重復(fù)計算若 |A| = m , |B| = n , AB = , 則 |AB| = m + n 。容斥的計數(shù)思想是:先不考慮重疊的情況，把包含于某內(nèi)容中的所有對象的數(shù)目先計算出來；然后再把計數(shù)時重復(fù)計算的數(shù)目排斥出去；使得計算的結(jié)果既無遺漏又無重復(fù)。 23.1 容斥原理引論例 1，20中2或3的倍數(shù)的個數(shù)解 2的倍數(shù)是：2，4，6，8，10，12，14，16，18，20。 10個3的倍數(shù)是：3，6，9，12，15，18。 6個但答案不是10

2、+6=16 個，因?yàn)?，12，18在兩類中重復(fù)計數(shù)，應(yīng)減去。故答案是：16-3=133若A和B是集合U的子集，補(bǔ)集complement德摩根De Morgan定理(a)(b)3.1 容斥原理引論UBA4證：(a)的證明。設(shè) ,則 相當(dāng)于 和 同時成立，亦即 (1)反之，若故(2)由（1）和（2）得(b)的證明和(a)類似，從略.(a)53.1 容斥原理引論DeMogan定理的推廣：設(shè)A1,A2, . An是U的子集,證:采用數(shù)學(xué)歸納法正確即定理對n+1也是正確的。63.2 容斥原理最簡單的計數(shù)問題是求有限集合A和B的并的元素數(shù)目。(1)證若AB=，則 | AB |= |A| + |B| A |

3、 A ( BB) | | (AB)(AB)| | AB | + | AB | ( 1 )同理| B | | BA | + | BA | ( 2 )| AB |(A( BB)(B(AA)|(AB)(AB)(BA)(BA)| AB| + |AB | + | BA| ( 3 )(3)-(2)-(1) 得到| AB | A | B | AB| + |AB | + | BA| ( | AB | + | AB | )( | BA | + | BA | ) | AB | AB | A | + | B | AB |73.2 容斥原理定理：(2)83.2 容斥原理93.2 容斥原理進(jìn)一步可推出：10定理設(shè)C(n

4、,k)是1,n的所有k-子集的集合, 則證: 分析C(n,k)，可根據(jù)包含不包含n劃分成兩部分 包含n的可看做C(n-1,k-1)中每個子集再加上元素n； 不包含n的由C(n-1,k)組成；對n用歸納法。n=2時，等式成立。 假設(shè)對n - 1，等式成立。對于n有C(2,k) = 1 2 k=1時 1 2 k=2時C(3,k) = 1 2 3 k=1時 1 21 32 3 k=2時 1 2 3 k=3時k2C(3,2) = 1 32 31 211證由于最后一項(xiàng)第一項(xiàng)123.2 容斥原理此定理也可表示為：(4)133.2 容斥原理其中N是集合U的元素個數(shù)，即不屬于A的元素個數(shù)等于集合的全體減去屬于

5、A的元素的個數(shù)。一般有：(5)14Inclusion-Exclusion Principle計算不在 A1 也不在 A2中的元素個數(shù)若x不屬于A1 或A211-0-0+0 = 1若x 屬于A1 但不屬于A201-1-0+0 = 0若x 屬于A2 但不屬于A101-0-1+0 = 0若x 屬于A2 且屬于A101-1-1+1 = 0兩邊相等15計算不滿足任意屬性的元素.x不滿足任何屬性11-0-0+(-1)m0 = 1x只滿足1個屬性01-1-0 +(-1)m0 = 0 x只滿足n個屬性, nm0C(n,0)-C(n,1)+C(n,2)+(-1)mC(n,m)= C(n,0)-C(n,1)+C(

6、n,2)+(-1)nC(n,n) +0 +0=0兩邊相等，同樣計算不滿足任何屬性的元素個數(shù)(x+y)m =C(m,0)xm+ C(m,1)xm-1y+C(m,m)ymIf x=1, y=-10 = C(m,0)- C(m,1) +(-1)mC(m,m)163.2 容斥原理容斥原理指的就是（4）和（5）式。(4) (5)17Inclusionexclusion principle This concept is attributed toAbraham de Moivre(1718) It first appears in a paper ofDaniel da Silva(1854) Late

7、r in a paper byJ. J. Sylvester(1883) One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusionexclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem. 18193.2 容斥原理例 一個

8、學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時修數(shù)學(xué)、化學(xué)的20人；同時修物理化學(xué)的22人。同時修三門的3人。問這學(xué)校共有多少學(xué)生？令：M為修數(shù)學(xué)的學(xué)生集合；P 為修物理的學(xué)生集合； C 為修化學(xué)的學(xué)生集合；即學(xué)校學(xué)生數(shù)為336人。193.3 舉例 例1 求a,b,c,d,e,f六個字母的全排列中不允許出現(xiàn)ace和df圖象的排列數(shù)。解：6個字母全排列： |S| = 6!設(shè)A為ace作為一個元素出現(xiàn)的排列集: |A|=4!， B為 df作為一個元素出現(xiàn)的排列集: |B|=5!， AB為同時出現(xiàn)ace、df的排列數(shù):

9、 |AB |=3!。 203.3 舉例 例2 求從1到500的整數(shù)中能被3或5除盡的數(shù)的個數(shù)。 解： 令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合， B為被5除盡的數(shù)的集合被3或5除盡的數(shù)的個數(shù)為213.3 舉例 例3 求由a,b,c,d四個字母構(gòu)成的n位符號串中，a,b,c都至少出現(xiàn)一次的符號串?dāng)?shù)目。 解：令A(yù)、B、C分別為n位符號串中不出現(xiàn)a，b，c符號的集合。由于n位符號串中每一位都可取a，b，c，d四種符號中的一個，故不允許出現(xiàn)a的n位符號串的個數(shù)應(yīng)是3n個，即： a，b，c至少出現(xiàn)一次的n位符號串集合即為223.3 舉例 例5。用26個英文字母作不允許重復(fù)的全排列，要求排除dog，g

10、od，gum，depth，thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。 解：令A(yù)1為出現(xiàn)dog，| A1 |=24！ 令A(yù)2為出現(xiàn)god，| A2 |=24！ 令A(yù)3為出現(xiàn)gum，| A3 |=24！ 令A(yù)4為出現(xiàn)depth，| A4 |=22！ 令A(yù)5為出現(xiàn)thing，| A5 |=22！| A1A2| = 0, A1A3, dogum: | A1A3| = 22!, A2A4, godepth: | A2A4| = 20!, A2A5, thingod: | A2A5| = 20!, A3A4, gum*depth或者gum*depth : | A3A4| = 20！A3A5, thin

11、gum: | A3A5| = 20！A4A5, depthing: | A4A5| = 19!, A1A3 A4,dogumdepth 0; A2A4 A5, godepthing 0;A3A4 A5, depthingum | A3A4 A5 | = 17！所求的排列數(shù)為 26!-(3*24!+2*22!)+(22!+4*20!+19!)-(17!)233.3 舉例0 00 11 01 1f(x1,x2)f10000f20001f30010f40011f50100f60101f70110f80111f91000f101001f111010f121011f131100f141101f15111

12、0f161111例6。求完全由n個布爾變量確定的布爾函數(shù)的個數(shù)。f(x1,x2,xn)中n個布爾變量的不同的狀態(tài)數(shù)為2n每個狀態(tài)有0，1兩種取值，故f(x1,x2,xn)的布爾函數(shù)個數(shù)為 24例6。求完全由n個布爾變量確定的布爾函數(shù)的個數(shù)。解：設(shè) 布爾函數(shù)類為： 有1個變量不出現(xiàn)的布爾函數(shù)個數(shù)為有2個變量不出現(xiàn)的布爾函數(shù)個數(shù)為 有k個變量不出現(xiàn)的布爾函數(shù)個數(shù)為 根據(jù)容斥原理，滿足條件的函數(shù)數(shù)目為：f(x1,x2,xn)的布爾函數(shù)個數(shù)為253.3 舉例0 00 11 01 1f(x1,x2)f10000f20001f30010f40011f50100f60101f70110f80111f9100

13、0f101001f111010f121011f131100f141101f151110f161111例6。求完全由n個布爾變量確定的布爾函數(shù)的個數(shù)。f(x1,x2,xn)中n個布爾變量的不同的狀態(tài)數(shù)為2n每個狀態(tài)有0，1兩種取值，故f(x1,x2,xn)的布爾函數(shù)個數(shù)為 26273.3 舉例例4。求不超過120的素數(shù)個數(shù)。因112=121，故不超過120的合數(shù)必然是2、3、5、7的倍數(shù)，而且不超過120的合數(shù)的因子不可能都超過11。 設(shè)Ai為不超過120的數(shù) i的倍數(shù)集， i=2，3，5，7。2728注意：因?yàn)?7個數(shù)中排除了2，3，5，7四個素數(shù)，又包含了1這個非素數(shù)。故所求的不超過120的

14、素數(shù)個數(shù)為： 27+4-1=3028 例7。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個數(shù)。分析的化身歐拉進(jìn)行計算看起來毫不費(fèi)勁兒，就像人進(jìn)行呼吸，像鷹在風(fēng)中盤旋一樣。他是歷史上最多產(chǎn)的數(shù)學(xué)家。彼得堡學(xué)院為了整理他的著作整整花了47年。歐拉確實(shí)常常在兩次叫他吃晚飯的半小時左右的時間里趕出一篇數(shù)學(xué)論文歐拉是史上發(fā)表論文數(shù)第二多的數(shù)學(xué)家，全集共計75卷；他的紀(jì)錄一直到了20世紀(jì)才被保羅埃爾德什打破 “讀歐拉的著作吧，在任何意義上，他都是我們的大師” 人生波折：失明，火災(zāi)1783年9月18日，他77歲的時候，歐拉寫出了他對天王星軌道的計算。他在喝著茶跟孩子玩的時候，中風(fēng)發(fā)作。手中煙斗掉了，只說出一句話

15、我要死了,歐拉便停止了生命和計算。在計算機(jī)領(lǐng)域中廣泛使用的RSA公鑰密碼算法也正是以歐拉函數(shù)為基礎(chǔ)的。-拉普拉斯293.3 舉例 例7。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個數(shù)。解：若n分解為不同素數(shù)的乘積 設(shè)1到n的n個數(shù)中為pi倍數(shù)的集合為Ai(8)=48 = 23，小于8且與8互素有1 3 5 7對于pipj, AiAj既是pi的倍數(shù)也是pj的倍數(shù)。30例7續(xù)。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個數(shù)。即比60小且與60無公因子的數(shù)有16個：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外還有一個1。(8)=8(1-1/2) = 4 8

16、 = 23，小于8且與8互素有1 3 5 731例 求不定方程x1+x2+x3=15,求整數(shù)解的數(shù)目。其中附加約束為0 x1 5, 0 x2 6； 0 x3 7,32例 求不定方程x1+x2+x3=15,附加約束為0 x1 5, 0 x2 6； 0 x3 7,求整數(shù)解的數(shù)目。解：對于x1+x2+xn=r的非負(fù)整數(shù)解的個數(shù)為C(n+r-1,r)沒有約束情況下的不定方程x1+x2+x3=15的非負(fù)整數(shù)解的個數(shù)為C(15+3-1,15)= C(17,2)設(shè)A1為x16的解， y1+6+x2+x3=15|A1|= C(9+3-1,9)= C(11,2)設(shè)A2為x27的解， x1+y2+7+x3=15|

17、A2|= C(8+3-1,8)= C(10,2)設(shè)A3為x38的解，x1+x2+ y3+8=15|A3|= C(7+3-1,7)= C(9,2)A1A2: y1+6+y2+7+x3=15 |A1A2|= C(2+3-1,2)= C(4,2)A1A3: y1+6+x2+y3+8=15 |A1A3|= C(1+3-1,1)= C(3,1)A2A3: x1+y2+7+y3+8=15 |A2A3|= 1A1A2 A3 : y1+6+y2+7+y3+8=15; |A1A2 A3 |= 0|A1A2 A3|=C(17,2) C(11,2)-C(10,2)-C(9,2) +C(4,2)+C(3,1)+1=1

18、0333.7 容斥原理應(yīng)用舉例例 求不定方程x1+x2+x3=15,附加約束為0 x15, 0 x26； 0 x37,求整數(shù)解的數(shù)目。解2: 1=5-x1, 2=6-x2, 3=7-x31+ 2 + 3 =5-x1+6-x2+7-x3=18-(x1+x2+x3) = 3, 1+ 2 + 3 =3 1, 2, 30的非負(fù)整數(shù)解個數(shù)。C(3+3-1,3) = 10教材：例3-18，pp13834討論例:求不定方程x1+x2+x3=15,附加約束為0 x1 10, 0 x2 10； 0 x3 10,求整數(shù)解的數(shù)目1=10-x1, 2=10-x2, 3=10-x31+ 2 + 3 =10-x1+10-

19、x2+10-x3=15, 1, 2, 301+ 2 + 3 =15 1, 2, 30 x1+x2+x3=15 0 x1,x2,x3 10顯然不成立,所以原解法不具有通用性應(yīng)加上約束條件整數(shù)解個數(shù)相等?11+2+2=15 1=11 2=2 3=2 找不到對應(yīng)的x1,x2,x3 1=10-x1, 2=10-x2, 3=10-x3 0 1, 2, 3 1035討論x1+x2+x3=S0 x1 m1, 0 x2 m2； 0 x3 m31=m1-x1, 2=m2-x2, 3=m3-x31+ 2 + 3 =m1+m2+m3-S0 1 m1, 2 m2, 3 m3若m1+m2+m3-S min(m1,m2,

20、m3)則x1+x2+x3=S 0 x1 m1, 0 x2 m2； 0 x1 m31+ 2 + 3 =m1+m2+m3-S 1, 2, 30整數(shù)解個數(shù)相等363.3 舉例例8: 錯排問題: n個元素依次給以標(biāo)號1，2，n。n個元素的全排列中，求每個元素都不在自己原來位置上的排列數(shù)。設(shè)Ai為數(shù)i在第i位上的全體排列，i=1，2，n。因數(shù)字i不能動，因而有：|Ai|=(n-1)! |AiAj |=(n-2)!每個元素都不在原來位置的排列數(shù)為37例9 在8個字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個字母不在原來位置上的排列數(shù)目。解：8個字母的全排列中，令A(yù)A,AC,AE,AG

21、分別表A,C,E,G在原來位置上的排列，則錯排數(shù)為：38求8個字母A,B,C,D,E,F,G,H的全排列中只有4個不在原來位置的排列數(shù)。解：8個字母中只有4個不在原來位置上，其余4個字母保持不動，相當(dāng)于4個元素的錯排，其數(shù)目為 故8個字母的全排列中有4個不在原來位置上的排列數(shù)應(yīng)為：C(8,4)9=630393.4 棋盤多項(xiàng)式和有限制排列有限制排列例4個x ，3個y，2個z的全排列中，求不出現(xiàn)xxxx，yyy，zz圖象的排列。解設(shè)出現(xiàn)xxxx的排列的集合記為A1， |A1|= =60; 設(shè)出現(xiàn)yyy的排列的集合記為A2， | A2|= =105； 設(shè)出現(xiàn)zz的排列的集合記為A2， | A3|=

22、=280； |A1A2|= =12； |A1A3|= =20； |A2A3|= =30； |A1A2A3|=3!=6； 全排列的個數(shù)為： 9!/(4!*3!*2!) =1260；所以： |A1A2A3|=1260(60+105+280)+(12+20+30)6 =871403.4 棋盤多項(xiàng)式和有限制排列棋盤多項(xiàng)式n個不同元素的一個全排列可看做n個相同的棋子在nn的棋盤上的一個布局。布局滿足同一行（列）中有且僅有一個棋子non-attacking rooks xxxxx 如圖所示的布局對應(yīng)于排列41352。1 2 3 4 5P1P2P3P4P5413.4 棋盤多項(xiàng)式和有限制排列 可以把棋盤的形狀

23、推廣到任意形狀：r1( )=1，r1( )=2，r1( )=2，r2( )=0，r2( )=1。令r k（C）表示k個棋子布到棋盤C上的方案數(shù)。如：423.4 棋盤多項(xiàng)式和有限制排列定義 設(shè)C為一棋盤，稱R(C)= rk(C) xk為C的棋盤多項(xiàng)式。規(guī)定 r0(C)=1，包括C=時。k=0 n性質(zhì)1:設(shè)Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤，則 rk(C)=rk1(Ci)rk(Ce)對任一指定的格子，要么布子，方案數(shù)為 rk-1(Ci)；要么不布子，方案數(shù)為 rk(Ce)。*CiCe433.4 棋盤多項(xiàng)式和有限制排列 r0(C)1 ?設(shè)C有n個格子

24、，則 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故規(guī)定 r0(C)1是合理的443.4 棋盤多項(xiàng)式和有限制排列該性質(zhì)擴(kuò)展到棋盤多項(xiàng)式，從而nk=0R(C)= rk(C) xknk=1 rk1(Ci)+ rk(Ce)xkn-1k=0nk=0 = x rk(Ci)xk + rk(Ce)xk xR(Ci) + R(C e) (3)453.4 棋盤多項(xiàng)式和有限制排列例如：R( )= xR( )+ R( )R( )=1+ x；R( )= x R( ) + R( ) =x+ (1+ x)=1+2x； = x(1 + x )+1 + x =1+ 2x +x2463

25、.4 棋盤多項(xiàng)式和有限制排列性質(zhì)2:如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒有C2的格子。則有： rk(C) = ri(C1) rki(C2) i=0k故R(C) = ( ri(C1) rki(C2) ) xk kni=0k=0 R(C) = R(C1) R(C2) (4)j=0nni=0 = ( ri(C1) xi) ( rj(C2) xj )473.4 棋盤多項(xiàng)式和有限制排列利用（）和（），可以把一個比較復(fù)雜的棋盤逐步分解成相對比較簡單的棋盤，從而得到其棋盤多項(xiàng)式。例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3*483.5 棋盤多項(xiàng)式和有限制排列有禁區(qū)的排列例設(shè)對于排列P=P1 P2 P3 P4，規(guī)定P1，P、， P2、， P42。 1 2 3 4P1P2P3P4這樣的排列對應(yīng)于有禁區(qū)的布子。如圖中有影線的格子表示禁區(qū)。493.5 棋盤多項(xiàng)式和有限制排列定理設(shè) ri 為 i個棋子布入禁區(qū)的方案數(shù)，i =1,2,3,n。有禁區(qū)的布子方案數(shù)（即禁區(qū)內(nèi)不布子的方案數(shù)）為 n! r1(n1)! r2(n2)