容斥原理初步

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

2、+6=16 個(gè)，因?yàn)?，12，18在兩類中重復(fù)計(jì)數(shù)，應(yīng)減去。故答案是：16-3=133若A和B是集合U的子集，補(bǔ)集complement德摩根De Morgan定理(a)(b)3.1 容斥原理引論UBA4證：(a)的證明。設(shè) ,則 相當(dāng)于 和 同時(shí)成立，亦即 (1)反之，若故(2)由（1）和（2）得(b)的證明和(a)類似，從略.(a)53.1 容斥原理引論DeMogan定理的推廣：設(shè)A1,A2, . An是U的子集,證:采用數(shù)學(xué)歸納法正確即定理對(duì)n+1也是正確的。63.2 容斥原理最簡(jiǎn)單的計(jì)數(shù)問(wèn)題是求有限集合A和B的并的元素?cái)?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)中每個(gè)子集再加上元素n； 不包含n的由C(n-1,k)組成；對(duì)n用歸納法。n=2時(shí)，等式成立。 假設(shè)對(duì)n - 1，等式成立。對(duì)于n有C(2,k) = 1 2 k=1時(shí) 1 2 k=2時(shí)C(3,k) = 1 2 3 k=1時(shí) 1 21 32 3 k=2時(shí) 1 2 3 k=3時(shí)k2C(3,2) = 1 32 31 211證由于最后一項(xiàng)第一項(xiàng)123.2 容斥原理此定理也可表示為：(4)133.2 容斥原理其中N是集合U的元素個(gè)數(shù)，即不屬于A的元素個(gè)數(shù)等于集合的全體減去屬于

5、A的元素的個(gè)數(shù)。一般有：(5)14Inclusion-Exclusion Principle計(jì)算不在 A1 也不在 A2中的元素個(gè)數(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計(jì)算不滿足任意屬性的元素.x不滿足任何屬性11-0-0+(-1)m0 = 1x只滿足1個(gè)屬性01-1-0 +(-1)m0 = 0 x只滿足n個(gè)屬性, 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兩邊相等，同樣計(jì)算不滿足任何屬性的元素個(gè)數(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 容斥原理例 一個(gè)

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

9、 |AB |=3!。 203.3 舉例 例2 求從1到500的整數(shù)中能被3或5除盡的數(shù)的個(gè)數(shù)。 解： 令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合， B為被5除盡的數(shù)的集合被3或5除盡的數(shù)的個(gè)數(shù)為213.3 舉例 例3 求由a,b,c,d四個(gè)字母構(gòu)成的n位符號(hào)串中，a,b,c都至少出現(xiàn)一次的符號(hào)串?dāng)?shù)目。 解：令A(yù)、B、C分別為n位符號(hào)串中不出現(xiàn)a，b，c符號(hào)的集合。由于n位符號(hào)串中每一位都可取a，b，c，d四種符號(hào)中的一個(gè)，故不允許出現(xiàn)a的n位符號(hào)串的個(gè)數(shù)應(yīng)是3n個(gè)，即： a，b，c至少出現(xiàn)一次的n位符號(hào)串集合即為223.3 舉例 例5。用26個(gè)英文字母作不允許重復(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個(gè)布爾變量確定的布爾函數(shù)的個(gè)數(shù)。f(x1,x2,xn)中n個(gè)布爾變量的不同的狀態(tài)數(shù)為2n每個(gè)狀態(tài)有0，1兩種取值，故f(x1,x2,xn)的布爾函數(shù)個(gè)數(shù)為 24例6。求完全由n個(gè)布爾變量確定的布爾函數(shù)的個(gè)數(shù)。解：設(shè) 布爾函數(shù)類為： 有1個(gè)變量不出現(xiàn)的布爾函數(shù)個(gè)數(shù)為有2個(gè)變量不出現(xiàn)的布爾函數(shù)個(gè)數(shù)為 有k個(gè)變量不出現(xiàn)的布爾函數(shù)個(gè)數(shù)為 根據(jù)容斥原理，滿足條件的函數(shù)數(shù)目為：f(x1,x2,xn)的布爾函數(shù)個(gè)數(shù)為253.3 舉例0 00 11 01 1f(x1,x2)f10000f20001f30010f40011f50100f60101f70110f80111f9100

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

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

15、我要死了,歐拉便停止了生命和計(jì)算。在計(jì)算機(jī)領(lǐng)域中廣泛使用的RSA公鑰密碼算法也正是以歐拉函數(shù)為基礎(chǔ)的。-拉普拉斯293.3 舉例 例7。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個(gè)數(shù)。解：若n分解為不同素?cái)?shù)的乘積 設(shè)1到n的n個(gè)數(shù)中為pi倍數(shù)的集合為Ai(8)=48 = 23，小于8且與8互素有1 3 5 7對(duì)于pipj, AiAj既是pi的倍數(shù)也是pj的倍數(shù)。30例7續(xù)。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個(gè)數(shù)。即比60小且與60無(wú)公因子的數(shù)有16個(gè)：7，11，13，17，19，23，29，31，37，41，43，47，49，53，59，此外還有一個(gè)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ù)目。解：對(duì)于x1+x2+xn=r的非負(fù)整數(shù)解的個(gè)數(shù)為C(n+r-1,r)沒(méi)有約束情況下的不定方程x1+x2+x3=15的非負(fù)整數(shù)解的個(gè)數(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ù)解個(gè)數(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ù)解個(gè)數(shù)相等?11+2+2=15 1=11 2=2 3=2 找不到對(duì)應(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ù)解個(gè)數(shù)相等363.3 舉例例8: 錯(cuò)排問(wèn)題: n個(gè)元素依次給以標(biāo)號(hào)1，2，n。n個(gè)元素的全排列中，求每個(gè)元素都不在自己原來(lái)位置上的排列數(shù)。設(shè)Ai為數(shù)i在第i位上的全體排列，i=1，2，n。因數(shù)字i不能動(dòng)，因而有：|Ai|=(n-1)! |AiAj |=(n-2)!每個(gè)元素都不在原來(lái)位置的排列數(shù)為37例9 在8個(gè)字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個(gè)字母不在原來(lái)位置上的排列數(shù)目。解：8個(gè)字母的全排列中，令A(yù)A,AC,AE,AG

21、分別表A,C,E,G在原來(lái)位置上的排列，則錯(cuò)排數(shù)為：38求8個(gè)字母A,B,C,D,E,F,G,H的全排列中只有4個(gè)不在原來(lái)位置的排列數(shù)。解：8個(gè)字母中只有4個(gè)不在原來(lái)位置上，其余4個(gè)字母保持不動(dòng)，相當(dāng)于4個(gè)元素的錯(cuò)排，其數(shù)目為 故8個(gè)字母的全排列中有4個(gè)不在原來(lái)位置上的排列數(shù)應(yīng)為：C(8,4)9=630393.4 棋盤多項(xiàng)式和有限制排列有限制排列例4個(gè)x ，3個(gè)y，2個(gè)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； 全排列的個(gè)數(shù)為： 9!/(4!*3!*2!) =1260；所以： |A1A2A3|=1260(60+105+280)+(12+20+30)6 =871403.4 棋盤多項(xiàng)式和有限制排列棋盤多項(xiàng)式n個(gè)不同元素的一個(gè)全排列可看做n個(gè)相同的棋子在nn的棋盤上的一個(gè)布局。布局滿足同一行（列）中有且僅有一個(gè)棋子non-attacking rooks xxxxx 如圖所示的布局對(duì)應(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個(gè)棋子布到棋盤C上的方案數(shù)。如：423.4 棋盤多項(xiàng)式和有限制排列定義 設(shè)C為一棋盤，稱R(C)= rk(C) xk為C的棋盤多項(xiàng)式。規(guī)定 r0(C)=1，包括C=時(shí)。k=0 n性質(zhì)1:設(shè)Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤，則 rk(C)=rk1(Ci)rk(Ce)對(duì)任一指定的格子，要么布子，方案數(shù)為 rk-1(Ci)；要么不布子，方案數(shù)為 rk(Ce)。*CiCe433.4 棋盤多項(xiàng)式和有限制排列 r0(C)1 ?設(shè)C有n個(gè)格子

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的任一格子所在的行和列中都沒(méi)有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)式和有限制排列利用（）和（），可以把一個(gè)比較復(fù)雜的棋盤逐步分解成相對(duì)比較簡(jiǎn)單的棋盤，從而得到其棋盤多項(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è)對(duì)于排列P=P1 P2 P3 P4，規(guī)定P1，P、， P2、， P42。 1 2 3 4P1P2P3P4這樣的排列對(duì)應(yīng)于有禁區(qū)的布子。如圖中有影線的格子表示禁區(qū)。493.5 棋盤多項(xiàng)式和有限制排列定理設(shè) ri 為 i個(gè)棋子布入禁區(qū)的方案數(shù)，i =1,2,3,n。有禁區(qū)的布子方案數(shù)（即禁區(qū)內(nèi)不布子的方案數(shù)）為 n! r1(n1)! r2(n2)