容斥原理和鴿巢原理分析講解

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+6=16個(gè)，因?yàn)?，12，18在兩類(lèi)中重復(fù)計(jì)數(shù)，應(yīng)減去。故答案是：16-3=133.1 De Morgan定理容斥原理和鴿巢原理分析講解 3.1 De Morgan定理DeMorgan定理 論域U，補(bǔ)集,有(a)(b)容斥原理和鴿巢原理分析講解DeMogan定理的推廣： 設(shè)A1,A2, ,An是U的子集，則證明：只證(1). N=2時(shí)定理已證。 設(shè)定理對(duì)n是正確的，

2、即假定：3.1 De Morgan定理容斥原理和鴿巢原理分析講解即定理對(duì)n+1也是正確的。3.1 De Morgan定理則容斥原理和鴿巢原理分析講解即具有性質(zhì)A或B的元素的個(gè)數(shù)等于具有性質(zhì)A和B的元素個(gè)數(shù)。定理：3.2 容斥原理UBA容斥原理和鴿巢原理分析講解定理：3.2 容斥原理容斥原理和鴿巢原理分析講解ABC3.2 容斥原理容斥原理和鴿巢原理分析講解例： 一個(gè)學(xué)校只有三門(mén)課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門(mén)課的學(xué)生分別有170、130、120人；同時(shí)修數(shù)學(xué)、物理兩門(mén)課的學(xué)生45人；同時(shí)修數(shù)學(xué)、化學(xué)的20人；同時(shí)修物理化學(xué)的22人。同時(shí)修三門(mén)的3人。問(wèn)這學(xué)校共有多少學(xué)生？3.2 容斥原理容斥

3、原理和鴿巢原理分析講解令：M為修數(shù)學(xué)的學(xué)生集合； P 為修物理的學(xué)生集合； C 為修化學(xué)的學(xué)生集合；3.2 容斥原理容斥原理和鴿巢原理分析講解即學(xué)校學(xué)生數(shù)為336人。3.2 容斥原理容斥原理和鴿巢原理分析講解同理可推出：利用數(shù)學(xué)歸納法可得一般的定理：3.2 容斥原理容斥原理和鴿巢原理分析講解定理：設(shè)A1,A2, ,An是有限集合，則3.2 容斥原理容斥原理和鴿巢原理分析講解 證：用數(shù)學(xué)歸納法證明。 已知 n=2時(shí)有設(shè) n-1時(shí)成立，即有：3.2 容斥原理容斥原理和鴿巢原理分析講解3.2 容斥原理容斥原理和鴿巢原理分析講解3.2 容斥原理容斥原理和鴿巢原理分析講解3.2 容斥原理容斥原理和鴿巢原

4、理分析講解3.2 容斥原理容斥原理和鴿巢原理分析講解3.2 容斥原理容斥原理和鴿巢原理分析講解3.2 容斥原理容斥原理和鴿巢原理分析講解 其中N是集合U的元素個(gè)數(shù)，即不屬于A的元素個(gè)數(shù)等于集合的全體減去屬于A的元素的個(gè)數(shù)。 一般有：3.2 容斥原理又容斥原理和鴿巢原理分析講解3.2 容斥原理容斥原理和鴿巢原理分析講解例1 求a,b,c,d,e,f六個(gè)字母的全排列中不允許出現(xiàn)ace和df圖象的排列數(shù)。 解：設(shè)A為ace作為一個(gè)元素出現(xiàn)的排列集，B為 df作為一個(gè)元素出現(xiàn)的排列集， 為同時(shí)出現(xiàn)ace、df的排列數(shù)。3.3 容斥原理舉例容斥原理和鴿巢原理分析講解根據(jù)容斥原理，不出現(xiàn)ace和df的排列

5、數(shù)為：=6!- (5!+4!)+3!=582 3.3 容斥原理舉例容斥原理和鴿巢原理分析講解例2 求從1到500的整數(shù)中能被3或5除盡的數(shù)的個(gè)數(shù)。 解： 令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合，B為被5除盡的數(shù)的集合3.3 容斥原理舉例容斥原理和鴿巢原理分析講解被3或5除盡的數(shù)的個(gè)數(shù)為例3 求由a,b,c,d四個(gè)字母構(gòu)成的位符號(hào)串中，a,b,c至少出現(xiàn)一次的符號(hào)串?dāng)?shù)目。3.3 容斥原理舉例容斥原理和鴿巢原理分析講解 解：令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，即3.3

6、 容斥原理舉例容斥原理和鴿巢原理分析講解 a，b，c至少出現(xiàn)一次的n位符號(hào)串集合即為3.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。3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理

7、和鴿巢原理分析講解 注意：27并非就是不超過(guò)120的素?cái)?shù)個(gè)數(shù)，因?yàn)檫@里排除了2，3，5，7四個(gè)數(shù)，又包含了1這個(gè)非素?cái)?shù)。2，3，5，7本身是素?cái)?shù)。故所求的不超過(guò)120的素?cái)?shù)個(gè)數(shù)為： 27+4-1=303.3 容斥原理舉例容斥原理和鴿巢原理分析講解 例5 用26個(gè)英文字母作不允許重復(fù)的全排列，要求排除dog，god，gum，depth，thing字樣的出現(xiàn)，求滿(mǎn)足這些條件的排列數(shù)。 解：所有排列中，令：3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例A1為出現(xiàn)dog的排列的全體;A2為出現(xiàn)god的排列的全體;A3為出現(xiàn)gum的排列的全體;A4為出現(xiàn)depth的排列的全體.A5為

8、出現(xiàn)thing的排列的全體.容斥原理和鴿巢原理分析講解 出現(xiàn)dog字樣的排列，相當(dāng)于把dog作為一個(gè)單元參加排列，故類(lèi)似有： 由于god,dog不可能在一個(gè)排列中同 時(shí)出現(xiàn)，故：類(lèi)似：3.3 容斥原理舉例容斥原理和鴿巢原理分析講解 由于gum,dog可以在dogum字樣中同時(shí)出現(xiàn)，故有： 類(lèi)似有g(shù)od和depth可以在godepth字樣中同時(shí)出現(xiàn)，故 god和thing可以在thingod字樣中同時(shí)出現(xiàn)，從而 3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理和鴿巢原理分析講解 由于god、depth、thing不可以同時(shí)出現(xiàn)，故有： 其余多于3個(gè)集合的交集都為空集。3

9、.3 容斥原理舉例容斥原理和鴿巢原理分析講解 故滿(mǎn)足要求的排列數(shù)為： 3.3 容斥原理舉例容斥原理和鴿巢原理分析講解例6 求完全由n個(gè)布爾變量確定的布爾函數(shù)的個(gè)數(shù)。 解：設(shè)f(x1,x2, ,xn)中不出現(xiàn)xi的布爾函數(shù)為Ai (i=1,2, ,n) 由于n個(gè)布爾變量 的不同的真值表數(shù)目與 位2進(jìn)制數(shù)數(shù)目相同，故為 個(gè)。根據(jù)容斥原理，滿(mǎn)足條件的函數(shù)數(shù)目為：3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例若n=2，則容斥原理和鴿巢原理分析講解x1、x2均出現(xiàn)的10個(gè)布爾函數(shù)為：x1x2，x1x2，x1x2， x1x2，x1x2，x1x2，x1x2， x1x2，(x1x2)(x1

10、x2)， (x1x2)(x1x2)3.3 容斥原理舉例容斥原理和鴿巢原理分析講解例7：錯(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)，因而有：3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理和鴿巢原理分析講解每個(gè)元素都不在原來(lái)位置的排列數(shù)為3.3 容斥原理舉例容斥原理和鴿巢原理分析講解 例8. 數(shù)1,2,9的全排列中,求偶數(shù)在原來(lái)位置上,其余都不在原來(lái)位置的錯(cuò)排數(shù)目。 解：實(shí)際上是1,3,5,7,9五個(gè)數(shù)的錯(cuò)排問(wèn)題，總數(shù)為：3.3 容斥原理舉例容

11、斥原理和鴿巢原理分析講解 例9. 在8個(gè)字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個(gè)字母不在原來(lái)上的錯(cuò)排數(shù)目。 解: 8個(gè)字母的全排列中，令分別表A,C,E,G在原來(lái)位置上的排列，則錯(cuò)排數(shù)：3.3 容斥原理舉例容斥原理和鴿巢原理分析講解3.3 容斥原理舉例容斥原理和鴿巢原理分析講解例10. 求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ù)目為：3.3 容斥原理舉例容斥原理和鴿巢原理分析講解 故8個(gè)字母的全排列中有4個(gè)不在原來(lái)位置上的排列數(shù)應(yīng)為：C(8,

12、4)9=6303.3 容斥原理舉例容斥原理和鴿巢原理分析講解1. 有限制排列3.4 棋盤(pán)多項(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；6!4!2! 7!1!3!2! 容斥原理和鴿巢原理分析講解3.4 棋盤(pán)多項(xiàng)式和有限制排列 設(shè)出現(xiàn)zz的排列的集合記為A3， |A3|= =280； |A1A2|= =12； |A1A3|= =20； |A2A3|= =30； |A1A2A3|=3!=6； 全排列的個(gè)數(shù)為： =1260；

13、所以： |A1A2A3|=1260(60+105+280) +(12+20+30)6 = 871 4!3!8!4!2!5!3!6!4!9!2!3!4!容斥原理和鴿巢原理分析講解2. 棋子多項(xiàng)式 n個(gè)不同元素的一個(gè)全排列可看做n個(gè)相同的棋子在nn的棋盤(pán)上的一個(gè)布局。布局滿(mǎn)足同一行（列）中有且僅有一個(gè)棋子。xxxxx 如圖所示的布局對(duì)應(yīng)于排列41352。3.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解 可以把棋盤(pán)的形狀推廣到任意形狀： 布子規(guī)定稱(chēng)為無(wú)對(duì)攻規(guī)則，棋子相當(dāng)于象棋中的車(chē)。 令r k(C)表示k個(gè)棋子布到棋盤(pán)C上的方案數(shù)。如：3.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解

14、r1( )=1，r1( )=2，r1( )=2，r2( )=0，r2( )=1。 為了形象化起見(jiàn), ( )中的圖像便是棋盤(pán)的形狀。3.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解定義 設(shè)C為一棋盤(pán)，稱(chēng)R(C)= rk(C) xk為C的棋盤(pán)多項(xiàng)式。 規(guī)定 r0(C)=1，包括C=時(shí)。 設(shè)Ci是棋盤(pán)C的某一指定格子所在的行與列都去掉后所得的棋盤(pán)；Ce是僅去掉該格子后的棋盤(pán)。 在上面定義下，顯然有 rk(C)=rk1(Ci)rk(Ce)，k=03.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解 即對(duì)任一指定的格子，要么布子，所得的方案數(shù)為 rk1(Ci)； 要么不布子，方案數(shù)為 rk(

15、Ce)。設(shè)C有n個(gè)格子，則 r1(C)n r1(C)r0(Ci) + r1(Ce)， r1(Ce)n1 r0(Ci)1 故規(guī)定 r0(C)1是合理的3.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解 即對(duì)任一指定的格子，要么布子，所得的方案數(shù)為 rk1(Ci)； 要么不布子，方案數(shù)為 rk(Ce)。從而R(C)= rk(C) xk rk1(Ci)+ rk(Ce)xk = x rk(Ci)xk + rk(Ce)xk xR(Ci) + R(C e) k=0k=0k=0k=03.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解例如： R( )=1+ x；R( )= xR( )+ R( )=

16、 x+ (1+ x)=1+2x； R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x23.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解 如果C由相互分離的C1，C2組成，即C的任一格子所在的行和列中都沒(méi)有C2的格子。則有： rk(C) = ri(C1) rki(C2) i=0k故R(C) = ( ri(C1) rki(C2) ) xk = ( ri(C1) xi) ( rj(C2) xj )j=0nnkni=0i=0k=0 R(C) = R(C1) R(C2)3.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解 利用(3)和(4)，可以把

17、一個(gè)比較復(fù)雜的棋盤(pán)逐步分解成相對(duì)比較簡(jiǎn)單的棋盤(pán)，從而得到其棋盤(pán)多項(xiàng)式。例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x33.4 棋盤(pán)多項(xiàng)式和有限制排列容斥原理和鴿巢原理分析講解例設(shè)對(duì)于排列P=P1 P2 P3 P4，規(guī)定P1，P、， P2、， P42。 1 2 3 4P1P2P3P412 4 314 3223431 214 這樣的排列對(duì)應(yīng)于有禁區(qū)的布子。如右圖有影線(xiàn)的格子表示禁區(qū)。3.5 有禁區(qū)的排列容斥原理和鴿巢原理分析講解定理設(shè) ri 為 i個(gè)棋子布入

18、禁區(qū)的方案數(shù)，i =1,2,3,n。有禁區(qū)的布子方案數(shù)(即禁區(qū)內(nèi)不布子的方案數(shù))為 r0 n! r1(n1)! r2(n2)!(1)nrn(1)k rk ( nk)! k=0n證令P1P2Pn是n個(gè)棋子布入nn棋盤(pán)的排列,即Pi是第i個(gè)棋子在第i行的位置, Ai 是棋子Pi3.5 有禁區(qū)的排列容斥原理和鴿巢原理分析講解落入禁區(qū),其他棋子任意布的方案集，i =1, 2, 3, ,n。一個(gè)棋子落入禁區(qū),其余n-1個(gè)棋子進(jìn)行無(wú)條件的排列,故至少有一個(gè)棋子落入禁區(qū)的方案數(shù)為r1(n-1)!,兩個(gè)棋子落入禁區(qū),其余n-2個(gè)棋子進(jìn)行無(wú)條件的排列,故至少有兩個(gè)棋子落入禁區(qū)的方案數(shù)為r2(n-2)!,依次類(lèi)推

19、,n個(gè)棋子無(wú)一落入禁區(qū)的排列數(shù)為:A1A2An=n!+ (1)k rk ( nk)!k=0 n3.5 有禁區(qū)的排列容斥原理和鴿巢原理分析講解上例方案數(shù)為 4!6(41)!11(42)!7(43)! 1(4)!4例1, 2, 3, 4四位工人，A, B, C, D 四項(xiàng)任務(wù)。條件如下: 1不干B; 2不干B、C; 不干C、D; 4不干D。問(wèn)有多少種可行方案？3.5 有禁區(qū)的排列容斥原理和鴿巢原理分析講解解由題意，可得如下棋盤(pán)：其中有影線(xiàn)的格子表示禁區(qū)。A B C D1 2 3 4 R( )=1+6x+10 x2+4x3 方案數(shù)=4!6(41)!+10(42)!4(43)! +0(44)!=43.

20、5 有禁區(qū)的排列容斥原理和鴿巢原理分析講解例三論錯(cuò)排問(wèn)題 錯(cuò)排問(wèn)題對(duì)應(yīng)的是nn的棋盤(pán)的主對(duì)角線(xiàn)上的格子是禁區(qū)的布子問(wèn)題。C = 錯(cuò)排的方案數(shù):3.5 有禁區(qū)的排列容斥原理和鴿巢原理分析講解3.6廣義的容斥原理例： 若將.2中的例子改為“單修一門(mén)數(shù)學(xué)的學(xué)生有多少？”“只修一門(mén)課的學(xué)生有多少”“只修兩門(mén)課的學(xué)生有多少？”則相應(yīng)的答案表示如下：MPC；MPC+MPC+MPCMPC+MPC+MPC容斥原理和鴿巢原理分析講解3.6廣義的容斥原理只修一門(mén)數(shù)學(xué)：只修一門(mén)物理：只修一門(mén)化學(xué)：容斥原理和鴿巢原理分析講解3.6廣義的容斥原理所以，只修一門(mén)課程：容斥原理和鴿巢原理分析講解3.6廣義的容斥原理修數(shù)學(xué)和

21、物理兩門(mén)課：類(lèi)似地：容斥原理和鴿巢原理分析講解3.6廣義的容斥原理一般地：容斥原理和鴿巢原理分析講解所以，可得：3.6廣義的容斥原理容斥原理和鴿巢原理分析講解3.6廣義的容斥原理還可以推得：容斥原理和鴿巢原理分析講解3.6廣義的容斥原理所以有：容斥原理和鴿巢原理分析講解3.6廣義的容斥原理定理：在集合S中,設(shè)A1,A2, ,An是n種性質(zhì)的子集,(m)表示剛好只有其中m個(gè)性質(zhì)的元素個(gè)數(shù),(m)表示至少有m個(gè)性質(zhì)的元素個(gè)數(shù),則容斥原理和鴿巢原理分析講解3.6廣義的容斥原理以m=2,n=4為例：容斥原理和鴿巢原理分析講解3.6廣義的容斥原理以m=3,n=4為例：容斥原理和鴿巢原理分析講解例：某校有

22、12個(gè)教師,已知教數(shù)學(xué)的有位,教物理的有位,教化學(xué)的位;數(shù)、理位,數(shù)、化位,理、化位;數(shù)理化位。問(wèn)教其他課的有幾位？只教一門(mén)的有幾位？只好教兩門(mén)的有幾位？解令教數(shù)學(xué)的教師屬于A1，教物理的屬于A2，教化學(xué)的屬于A3。則(0)12，(1) | A1 |+| A2|+| A3 |8+6+519;(2) | A1A2|+ | A1A3|+| A2A3|12；(3) | A1A2A3|3； 3.7廣義的容斥原理的應(yīng)用容斥原理和鴿巢原理分析講解故教其他課的老師數(shù)為：(0)(0)(1) +(2)(3)恰好一門(mén)的教師數(shù)：(1)(1)2(2) +3(3)=4恰好教兩門(mén)的老師數(shù)為：(2)(2)3(3) =33.

23、7廣義的容斥原理的應(yīng)用容斥原理和鴿巢原理分析講解3.8 第二類(lèi)Stirling數(shù)的展開(kāi)式第二類(lèi)Stirling數(shù)，S(n,m)是將n個(gè)有標(biāo)志的球放進(jìn)m個(gè)無(wú)區(qū)別的盒子而無(wú)一空盒的方案數(shù)，也是將n個(gè)數(shù)拆分成正好m個(gè)數(shù)的和的方案數(shù)?？紤]n個(gè)有標(biāo)志的球放進(jìn)m個(gè)有區(qū)別的盒子，無(wú)一空盒的方案數(shù)，令：Ai表示第i盒為空盒的子集，i=1,2, ,m.n個(gè)有標(biāo)志的球，m個(gè)有區(qū)別的盒，無(wú)一空盒的事件全體為S.容斥原理和鴿巢原理分析講解3.8 第二類(lèi)Stirling數(shù)的展開(kāi)式容斥原理和鴿巢原理分析講解3.8 第二類(lèi)Stirling數(shù)的展開(kāi)式n個(gè)有標(biāo)志的球放進(jìn)m個(gè)有區(qū)別的盒子，無(wú)一空盒的方案數(shù)：容斥原理和鴿巢原理分析

24、講解3.8 第二類(lèi)Stirling數(shù)的展開(kāi)式第二類(lèi)Stirling數(shù)，S(n,m)是將n個(gè)有標(biāo)志的球放進(jìn)m個(gè)無(wú)區(qū)別的盒子而無(wú)一空盒的方案數(shù)，所以：推論1：推論2：由于S(m,m)=1容斥原理和鴿巢原理分析講解問(wèn)題: 歐拉函數(shù) (n)是求小于n且與n互素的數(shù)的個(gè)數(shù)。 解：若n分解為素?cái)?shù)的乘積 設(shè)1到n的n個(gè)數(shù)中為Pi 倍數(shù)的數(shù)的集合為: Ai ( i=1,2, ,n)則有3.9 歐拉函數(shù)(n)容斥原理和鴿巢原理分析講解3.9 歐拉函數(shù)(n)容斥原理和鴿巢原理分析講解3.9 歐拉函數(shù)(n)容斥原理和鴿巢原理分析講解 即比60小且與60無(wú)公因子的數(shù)有16個(gè)：7，11，13，17，19，23，29，3

25、1，37，41，43，47，49，53，59，此外尚有一個(gè)1。3.9 歐拉函數(shù)(n)容斥原理和鴿巢原理分析講解3.10n對(duì)夫妻問(wèn)題例n 對(duì)夫妻圍坐問(wèn)題 設(shè) n 對(duì)夫妻圍圈而坐，男女相間，每個(gè)男人都不和他的妻子相鄰，有多少種可能的方案？解：（1）n個(gè)人圍桌而坐的方案數(shù)應(yīng)為( n1 )!n對(duì)夫妻圍桌而坐的方案數(shù)：2n(n-1)! 令：Ai表示第i對(duì)夫妻相鄰而坐的集合，i=1,2, ,n, 夫妻不相鄰的方案數(shù)為：容斥原理和鴿巢原理分析講解3.10n對(duì)夫妻問(wèn)題（2）2n個(gè)人圍桌而坐的方案數(shù)應(yīng)為( 2n1 )!|Ai|相當(dāng)于將第i對(duì)夫妻作為一個(gè)對(duì)象圍桌而坐后換位，故：容斥原理和鴿巢原理分析講解3.10n

26、對(duì)夫妻問(wèn)題故夫妻不相鄰而坐的方案數(shù)為：容斥原理和鴿巢原理分析講解.11Mbius反演定理 基本想法：an 易算, bn難算, an可用 bn表示, 利用反演, 將bn用an表示 1. 二項(xiàng)式反演引理:容斥原理和鴿巢原理分析講解.11Mbius反演定理 基本想法：an 易算, bn難算, an可用 bn表示, 利用反演, 將bn用an表示 1. 二項(xiàng)式反演引理:容斥原理和鴿巢原理分析講解.11Mbius反演定理 基本想法：an 易算, bn難算, an可用 bn表示, 利用反演, 將bn用an表示 Mbius反演定理：設(shè)f(n)和g(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，若則 反之亦然。其中：若d

27、=1若d=r個(gè)不同素?cái)?shù)之積其它（素?cái)?shù)積中含有相同素?cái)?shù)）容斥原理和鴿巢原理分析講解.11Mbius反演定理 輔助定理：對(duì)于任意正整數(shù)n恒有：證明：n=1時(shí)，定理成立。若其中，pi是互不相同的素?cái)?shù)。d|n可表示為： 容斥原理和鴿巢原理分析講解.11Mbius反演定理則d是從 個(gè) 中選 個(gè) ， 從 個(gè) 中選 個(gè) ， 從 個(gè) 中選 個(gè) ，而得到的結(jié)果。而重復(fù)取某個(gè) 時(shí)， ，令：容斥原理和鴿巢原理分析講解.11Mbius反演定理證明(Mbius反演定理)： 由f(n)的公式得：令由于容斥原理和鴿巢原理分析講解.11Mbius反演定理所以，反過(guò)來(lái)，容斥原理和鴿巢原理分析講解例圓排列問(wèn)題 設(shè) a1a2an

28、是一個(gè)圓排列，即 a2a3ana1 , ,ana1 an1，看作是相同的。為了加以區(qū)別，必要時(shí)把原先的排列稱(chēng)為線(xiàn)排列。一個(gè)圓排列在 n 個(gè)位置短開(kāi)形成的 n 個(gè)線(xiàn)排列在元素可重復(fù)的情況下，未必都不相同。例如，dn時(shí)，由不重復(fù)的a1a2 ad重復(fù) n d次構(gòu)成的圓排列。 .11Mbius反演定理容斥原理和鴿巢原理分析講解 ( a1a2 ad ) ( a1a2 ad ) n d 組 只能形成 d 個(gè)不同的線(xiàn)排列。若一個(gè)圓排列可由一個(gè)長(zhǎng)度為 k 的線(xiàn)排列重復(fù)若干次形成，則這樣的 k 中最小者成為該圓排列的周期。一個(gè)圓排列中元素的個(gè)數(shù)（重復(fù)出現(xiàn)的按其重復(fù)次數(shù)計(jì)）稱(chēng)為它的長(zhǎng)度。.11Mbius反演定理容

29、斥原理和鴿巢原理分析講解 設(shè)集合1 , 2 , , m中元素形成的長(zhǎng)度與周期都是 d 的圓排列的個(gè)數(shù)為M(d)。 設(shè) n 是一給定的正整數(shù)。 若 d n ，每個(gè)長(zhǎng)度與周期都是 d的圓排列可在 d 個(gè)位置上斷開(kāi)，重復(fù) n / d 次形成d個(gè)長(zhǎng)度為 n 的可重排列。因此有 d M( d ) = mn 由Mbus反演定理 n M(n) = ( d ) m故M( n ) = ( d ) mdndndnndnd.11Mbius反演定理容斥原理和鴿巢原理分析講解設(shè)長(zhǎng)度為 n 的圓排列的個(gè)數(shù)為T(mén)( n )，則T( n ) M( d ) dn例m = 1 , 2 ，n = 7 則 M ( 7 ) = ( 27

30、2 ) = 18 T ( 7 ) = M( d ) = M (1 ) + M ( 7) = 20 d717.11Mbius反演定理容斥原理和鴿巢原理分析講解.12 鴿巢原理 鴿巢原理是組合數(shù)學(xué)中最簡(jiǎn)單也是最基本的原理，也叫抽屜原理。即 “若有n個(gè)鴿子巢，n+1個(gè)鴿子，則至少有一個(gè)巢內(nèi)有至少有兩個(gè)鴿子。”例367人中至少有人的生日相同。例10雙手套中任取11只，其中至少有兩只 是完整配對(duì)的。例參加一會(huì)議的人中至少有人認(rèn)識(shí)的別的參加者的人數(shù)相等。容斥原理和鴿巢原理分析講解例從1到2n的正整數(shù)中任取n+1個(gè)，則這n+1個(gè)數(shù)中，至少有一對(duì)數(shù)，其中一個(gè)是另一個(gè)的倍數(shù)。證設(shè)n+1個(gè)數(shù)是 a1 , a2 ,

31、 , an+1。每個(gè)數(shù)去掉一切2的因子，直至剩下一個(gè)奇數(shù)為止。組成序列 r1 , r2, , , rn+1。這n+1個(gè)數(shù)仍在1 , 2n中，且都是奇數(shù)。而1 , 2n中只有n個(gè)奇數(shù) 。故必有 ri = rj = r , 則 ai = 2i r, aj = 2j r若ij ，則 ai 是 aj 的倍數(shù)。.12 鴿巢原理容斥原理和鴿巢原理分析講解 例設(shè) a1 , a2 , , am是正整數(shù)序列，則至 少存在k和 t , 1kt m，使得和 ak + ak+1 + + at 是m的倍數(shù)。證設(shè)Sk = ai , Sh rh mod m 0rhm-1h = 1 , 2 , , m . 若存在t, St0

32、 mod m 則命題成立否則，1rhm-1但h = 1 , 2 , , m由鴿巢原理，故存在 rk = rh , 即Sk Sh，不妨設(shè) h k則 ShSk = ak+1 + ak+2 + + ah 0 mod m i=1k.13 鴿巢原理舉例容斥原理和鴿巢原理分析講解例 設(shè) a1 , a2 , a3為任意個(gè)整數(shù)，b1b2b3為a1 , a2 , a3的任一排列，則 a1b1 , a2b2 , a3b3中至少有一個(gè)是偶數(shù)證由鴿巢原理， a1 , a2 , a3必有兩個(gè)同奇偶設(shè)這個(gè)數(shù)被除的余數(shù)為 xxy，于是b1 , b2 , b3中被除的余數(shù)有個(gè)x，一個(gè)y這樣a1b1 , a2b2 , a3b3

33、被除的余數(shù)必有一個(gè)為.13 鴿巢原理舉例容斥原理和鴿巢原理分析講解例 設(shè)a1 , a2 , , a100是由 1和組成的序列 , 已知從其任一數(shù)開(kāi)始的順序10個(gè)數(shù)的和不超過(guò)16即 ai + ai+1 + + ai+9 16，1 i 91 則至少存在 h 和 k ，k h，使得 ah + ah+1 + + ak = 39 證令Sj = ai，j =1 , 2 , ,100顯然 S1S2hSkSh =39 即 ah + ah+1 + + ak = 39 .13 鴿巢原理舉例容斥原理和鴿巢原理分析講解鴿巢原理二設(shè)至少kn+1只鴿子分配在n個(gè)鴿巢里,則至少存在一個(gè)鴿巢中有至少k+1只鴿子。 上一小節(jié)的

34、鴿巢原理一是這一原理的特殊情況，即k=1時(shí)的情況。.14 鴿巢原理的推廣容斥原理和鴿巢原理分析講解推論m只鴿子進(jìn)n個(gè)巢，至少有一個(gè)巢里有不少于 只鴿子推論n(m1) + 1只鴿子進(jìn)n個(gè)巢，至少有一個(gè)巢內(nèi)至少有m只鴿子推論若m1 , m2 , , mn是正整數(shù)，且 r1,則 m1, , mn至少有一個(gè)數(shù)不小于r。m1 + +mn n.14 鴿巢原理的推廣容斥原理和鴿巢原理分析講解定理若序列S = a1 , a2 , , an2+1中的各數(shù)是不等的則 S中至少可選出一組由n+1個(gè)元素組成的或?yàn)閱握{(diào)增或?yàn)閱握{(diào)減的子序列。證由S中的每個(gè) ai 向后選取最長(zhǎng)單調(diào)增子序列，設(shè)其長(zhǎng)度為li (i=1,2,

35、,n2+1) ，從而得序列L = l1 , l2 , , lk ,若存在 lkn+1, 則結(jié)論成立.14 鴿巢原理的推廣容斥原理和鴿巢原理分析講解否則所有的 li 1 , n,其中必有 個(gè)相等設(shè)li1 = li2 = = lin= lin+1 不妨設(shè) i1i2 ai2 ain+1 ，即有一長(zhǎng)度為n+1的遞減子序列否則不妨設(shè)ai1 li2 ，矛盾.14 鴿巢原理的推廣容斥原理和鴿巢原理分析講解例將 1 , 67 劃分為個(gè)子集，必有一個(gè)子集中有一數(shù)是同子集中的另兩數(shù)之差證用反證法設(shè)此命題不真即存在劃分P1P2P3P4 1,67 ,Pi中不存在一個(gè)數(shù)是Pi中兩數(shù)之差，i=1,2,3,4，因 ,故有一

36、子集，其中至少有17個(gè)數(shù)，設(shè)這17個(gè)數(shù)從小到大為a1 , , a17 不妨設(shè) A=a1 , , a17 。令bi1= aia1，i = 2，17。.14 鴿巢原理的推廣容斥原理和鴿巢原理分析講解設(shè)Bb1 , , b16，bi 1 , 67 。由反證法假設(shè)BP1 = 。因而 B( P2 P3 P4 )。 因?yàn)?，不妨設(shè)b1 , , b6 P2 ， 令Ci1=bib1，i = 2， ，6 設(shè)C C1 , , C5 ，C 1 , 67 由反證法假設(shè)C( P1P2 ) = ，故有 C(P3P4 )因?yàn)?，不妨設(shè)C1 , C2 , C3 P3.14 鴿巢原理的推廣容斥原理和鴿巢原理分析講解.14 鴿巢原

37、理的推廣令di1= CiC1，i = 2 , 3設(shè)D d1 , d2 , D 1 , 67。由反證法假設(shè) D( P1P2P3 )= ，因而 D P4由反證法假設(shè) d2d1 P1P2P3 且d2d1 P4 ，故 d2d1 1 , 67 ，但顯然 d2d1 1 , 67 ，矛盾。容斥原理和鴿巢原理分析講解.15Ramsey問(wèn)題Ramsey問(wèn)題 Ramsey問(wèn)題可以看成是鴿巢原理的推廣下面舉例說(shuō)明Ramsey問(wèn)題例6 個(gè)人中至少存在人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)證這個(gè)問(wèn)題與K6的邊著色存在同色三角形等價(jià)假定用紅藍(lán)著色容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題 設(shè)K6的頂點(diǎn)集為v1 , v2 ,

38、, v6 ，dr(v)表示與頂點(diǎn) v 關(guān)聯(lián)的紅色邊的條數(shù)，db(v)表示與 v 關(guān)聯(lián)的藍(lán)色邊的條數(shù)在K6 中，有dr(v) db(v)，由鴿巢原理可知，至少有條邊同色現(xiàn)將證明過(guò)程用判斷樹(shù)表示如下：容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題dr(v1)3?db(v1)3設(shè)(v1v2) (v1v3) (v1v4)為紅邊設(shè)(v1v2) (v1v3) (v1v4)為藍(lán)邊v2v3v4是紅 ?v2v3v4是藍(lán) ?設(shè)( v2v3 )是藍(lán)邊設(shè)( v2v3 )是紅邊v1v2v3是藍(lán)v1v2v3是紅YNNNYY容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題若干推論(a) K6的邊用紅藍(lán)任意著色，則

39、至少有兩個(gè)同色的三角形。證由前定理知，有同色三角形，不妨設(shè)v1v2v3是紅色三角形可由如下判斷樹(shù)證明容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題v1v4v5是藍(lán)設(shè) (v4v5)為藍(lán)邊v4v5v6是紅?設(shè)(v1v4) (v1v5) (v1v6)為藍(lán)邊db(v1)3dr(v1)3?設(shè) (v1v4)為紅邊(v4v2) (v4v3) 為藍(lán)邊?設(shè) (v4v2)為紅邊db(v4)3?v1v2v4是紅dr(v4)3設(shè) (v4v5)為藍(lán)邊(v4v5) (v4v6) 為紅邊v2v3v5是紅?設(shè) (v2v5)為藍(lán)邊v2v4v5是藍(lán)v4v5v6是紅v1v5v6是藍(lán)?設(shè) (v5v6)為紅邊yyyyyynnnn

40、n容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題(b)K9 的邊紅藍(lán)兩色任意著色，則必有紅K4或藍(lán)色三角形(藍(lán)K4或紅色三角形)證設(shè)個(gè)頂點(diǎn)為 v1 , v2 , , v9對(duì)個(gè)頂點(diǎn)的完全圖的邊的紅、藍(lán)著色圖中，必然存在vi ，使得 dr(vi)3 否則，紅邊數(shù) dr(vi) ，這是不可能的。不妨設(shè) dr(v1)3，可得如下判斷樹(shù)證明結(jié)論。1227 2容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題dr(v1)4?db(v1)6設(shè)(v1v2) (v1v3) (v1v4)(v1v5)是4紅邊設(shè)(v1v2) (v1v7)是6條藍(lán)邊K4(v2v3v4v5)是藍(lán)K4 ?K6(v2v7)中有紅 ?

41、設(shè)(v2v3)是紅邊v1v2v3是紅設(shè)v2v3v4是藍(lán)K4(v2v3v4v5)是藍(lán)K4YYYNNN容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題K9的邊紅、藍(lán)著色，必有紅色三角形或藍(lán)色K4 同理可證 K9的紅、藍(lán)著色，必有藍(lán)色三角形或紅色K4 (紅 藍(lán)K4) (藍(lán) 紅K4) 存在同色K4或紅及藍(lán) 同色K4 (紅 藍(lán) )容斥原理和鴿巢原理分析講解.15 Ramsey 問(wèn)題(c) K18的邊紅，藍(lán)著色，存在紅K4或藍(lán)K4 。證設(shè)18個(gè)頂點(diǎn)為v1 , v2 , , v18 從v1引出的17條邊至少有條是同色的，不妨先假定為紅色從而可得下面的判斷樹(shù)證明命題容斥原理和鴿巢原理分析講解.15 Ram

42、sey 問(wèn)題dr(v1)9db(v1)9設(shè)(v1v2) (v1v10)是紅邊K9(v2 v10)中有同色K4或紅加藍(lán)K10( v1v2 v10)中有同色K4設(shè)(v1v2) (v1v10)是藍(lán)邊K9(v2 v10)中有同色K4或紅加藍(lán)K10( v1v2 v10)中有同色K4YN容斥原理和鴿巢原理分析講解5 Ramsey數(shù) 將上一節(jié)的問(wèn)題一般化：給定一對(duì)正整數(shù)a、b，存在一個(gè)最小的正整數(shù) r ,對(duì) r 個(gè)頂點(diǎn)的完全圖的邊任意紅、藍(lán)著色，存在 a 個(gè)頂點(diǎn)的紅邊完全圖或 b 個(gè)頂點(diǎn)的藍(lán)邊完全圖。記為 r ( a , b )。比如：r ( 3 , 3 )6，r ( 3 , 4 )9，r ( 4 , 4 )18Ramsey數(shù)的簡(jiǎn)單性質(zhì)容斥原理和鴿巢原理分析講解5 Ramsey數(shù)定理r(a,b)r(b,a)；r(a,2)a證 K r(a , b )的邊紅藍(lán)著色，有紅Ka或藍(lán)Kb將紅藍(lán)色對(duì)換，就有紅Kb或藍(lán)Ka 設(shè)r(a,b)r，Kr的邊任意紅藍(lán)著色紅藍(lán)互換后仍是Kr的邊的著色，由r(a,b)的定義，有紅Ka或藍(lán)Kb再紅藍(lán)對(duì)換恢復(fù)原圖有紅Kb或藍(lán)Ka 容斥原理和鴿巢原理分析講解5 Ramsey數(shù)例 K9的邊任意紅藍(lán)著色，有紅三角形或藍(lán)K4紅藍(lán)對(duì)換后，仍有紅三角形或藍(lán)K4，再對(duì)