組合數(shù)學(xué)第三章容斥原理與鴿巢原理

1、關(guān)于組合數(shù)學(xué)第三章容斥原理和鴿巢原理第一張，PPT共一百五十頁，創(chuàng)作于2022年6月 3的倍數(shù)是：3，6，9，12，15， 18。 6個但答案不是10+6=16 個，因為6，12，18在兩類中重復(fù)計數(shù)，應(yīng)減去。故答案是：16-3=133.2 容斥原理第二張，PPT共一百五十頁，創(chuàng)作于2022年6月 容斥原理研究有限集合的交或并的計數(shù)。DeMorgan定理 論域U，補(bǔ)集,有3.2 容斥原理(a)(b)第三張，PPT共一百五十頁，創(chuàng)作于2022年6月證：(a)的證明。設(shè) ,則 相當(dāng)于 和同時成立，亦即 (1)3.2 容斥原理第四張，PPT共一百五十頁，創(chuàng)作于2022年6月反之，若故(2)由（1）和

2、（2）得(b)的證明和（a)類似，從略.3.2 容斥原理第五張，PPT共一百五十頁，創(chuàng)作于2022年6月DeMogan定理的推廣：設(shè) 證明：只證(a). N=2時定理已證。設(shè)定理對n是正確的，即假定：3.2 容斥原理第六張，PPT共一百五十頁，創(chuàng)作于2022年6月正確即定理對n+1也是正確的。3.2 容斥原理第七張，PPT共一百五十頁，創(chuàng)作于2022年6月2 容斥原理 最簡單的計數(shù)問題是求有限集合A和B的并的元素數(shù)目。顯然有即具有性質(zhì)A或B的元素的個數(shù)等于具(1)定理：3.2 容斥原理第八張，PPT共一百五十頁，創(chuàng)作于2022年6月有性質(zhì)A和B的元素個數(shù)。UBA3.2 容斥原理第九張，PPT共

3、一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理證若AB=，則 | AB |= |A| + |B| A | A ( BB) | | (AB)(AB)| | AB | + | AB | ( 1 )同理| B | | BA | + | BA | ( 2 )| AB |(A( BB)(B(AA)|(AB)(AB)(BA)(BA)| AB| + |AB | + | BA| ( 3 )第十張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理( 3 ) ( 1 ) ( 2 ) 得| AB | A | B | AB| + |AB | + | BA| ( | AB | + | AB | ) ( | B

4、A | + | BA | ) | AB | | AB | A | + | B | AB |第十一張，PPT共一百五十頁，創(chuàng)作于2022年6月定理：(2)3.2 容斥原理第十二張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理第十三張，PPT共一百五十頁，創(chuàng)作于2022年6月ABC3.2 容斥原理第十四張，PPT共一百五十頁，創(chuàng)作于2022年6月 例 一個學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時修數(shù)學(xué)、化學(xué)的20人；同時修物理化學(xué)的22人。同時修三門的3人。問這學(xué)校共有多少學(xué)生？3.2 容斥原理第十

5、五張，PPT共一百五十頁，創(chuàng)作于2022年6月令：M為修數(shù)學(xué)的學(xué)生集合； P 為修物理的學(xué)生集合； C 為修化學(xué)的學(xué)生集合；3.2 容斥原理第十六張，PPT共一百五十頁，創(chuàng)作于2022年6月即學(xué)校學(xué)生數(shù)為336人。3.2 容斥原理第十七張，PPT共一百五十頁，創(chuàng)作于2022年6月同理可推出：利用數(shù)學(xué)歸納法可得一般的定理：3.2 容斥原理第十八張，PPT共一百五十頁，創(chuàng)作于2022年6月 定理設(shè)(n,k)是1,n的所有k-子集的集合, 則 |Ai | = (1)k-1 | Ai |證對n用歸納法。n=2時，等式成立。 假設(shè)對n - 1，等式成立。對于n有 3.2 容斥原理ni=1k=1n I(n

6、,k)iI第十九張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理 I(n-1,k) I(n-1,k)iI第二十張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理 I(n,k) I(n-1,k-1) I(n-1,k)此定理也可表示為：第二十一張，PPT共一百五十頁，創(chuàng)作于2022年6月定理：設(shè)是有限集合，則(4)3.2 容斥原理第二十二張，PPT共一百五十頁，創(chuàng)作于2022年6月 證：用數(shù)學(xué)歸納法證明。已知 n=2時有設(shè) n-1時成立，即有：3.2 容斥原理3.2 容斥原理第二十三張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理第二十四張，PPT共一百五十頁，創(chuàng)

7、作于2022年6月3.2 容斥原理第二十五張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理第二十六張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理第二十七張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理第二十八張，PPT共一百五十頁，創(chuàng)作于2022年6月3.2 容斥原理第二十九張，PPT共一百五十頁，創(chuàng)作于2022年6月其中N是集合U的元素個數(shù)，即不屬于A的元素個數(shù)等于集合的全體減去屬于A的元素的個數(shù)。一般有：3.2 容斥原理第三十張，PPT共一百五十頁，創(chuàng)作于2022年6月(5)容斥原理指的就是（4）和（5）式。3.2 容斥原理第三十一張，PPT共一百五十

8、頁，創(chuàng)作于2022年6月3 例 例1 求a,b,c,d,e,f六個字母的全排列中不允許出現(xiàn)ace和df圖象的排列數(shù)。 解：設(shè)A為ace作為一個元素出現(xiàn)的排列集，B為 df作為一個元素出現(xiàn)的排列集， 為同時出現(xiàn)ace、df的排列數(shù)。3.3 例第三十二張，PPT共一百五十頁，創(chuàng)作于2022年6月根據(jù)容斥原理，不出現(xiàn)ace和df的排列數(shù)為：=6!- (5!+4!)+3!=582 3.3 例第三十三張，PPT共一百五十頁，創(chuàng)作于2022年6月 例2 求從1到500的整數(shù)中能被3或5除盡的數(shù)的個數(shù)。 解： 令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合，B為被5除盡的數(shù)的集合3.3 例第三十四張，PPT共

9、一百五十頁，創(chuàng)作于2022年6月被3或5除盡的數(shù)的個數(shù)為 例3 求由a,b,c,d四個字母構(gòu)成的位符號串中，a,b,c,d至少出現(xiàn)一次的符號串?dāng)?shù)目。3.3 例第三十五張，PPT共一百五十頁，創(chuàng)作于2022年6月 解：令A(yù)、B、C分別為n位符號串中不出現(xiàn)a，b，c符號的集合。 由于n位符號串中每一位都可取a，b，c，d四種符號中的一個，故不允許出現(xiàn)a的n位符號串的個數(shù)應(yīng)是3.3 例第三十六張，PPT共一百五十頁，創(chuàng)作于2022年6月 a，b，c至少出現(xiàn)一次的n位符號串集合即為3.3 例第三十七張，PPT共一百五十頁，創(chuàng)作于2022年6月 例4。求不超過120的素數(shù)個數(shù)。 因 ，故不超過120的合

10、數(shù)必然是2、3、5、7的倍數(shù)，而且不超過120的合數(shù)的因子不可能都超過11。 設(shè) 為不超過120的數(shù) 的倍數(shù)集， =2，3，5，7。3.3 例第三十八張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第三十九張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第四十張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第四十一張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第四十二張，PPT共一百五十頁，創(chuàng)作于2022年6月 注意：27并非就是不超過120的素數(shù)個數(shù)，因為這里排除了2，3，5，7著四個數(shù)，又包含了1這個非素數(shù)。2，3，5，7本身是素數(shù)。故所求的不超過120的素數(shù)個數(shù)

11、為： 27+4-1=303.3 例第四十三張，PPT共一百五十頁，創(chuàng)作于2022年6月 例5。用26個英文字母作不允許重復(fù)的全排列，要求排除dog，god，gum，depth，thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。 解：所有排列中，令：3.3 例第四十四張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第四十五張，PPT共一百五十頁，創(chuàng)作于2022年6月 出現(xiàn)dog字樣的排列，相當(dāng)于把dog作為一個單元參加排列，故類似有： 由于god,dog不可能在一個排列中同 時出現(xiàn)，故： 類似：3.3 例第四十六張，PPT共一百五十頁，創(chuàng)作于2022年6月 由于gum,dog可以在dogum字

12、樣中同時出現(xiàn)，故有： 類似有g(shù)od和depth可以在godepth字樣中同時出現(xiàn)，故 god和thing可以在thingod字樣中同時出現(xiàn)，從而 3.3 例第四十七張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第四十八張，PPT共一百五十頁，創(chuàng)作于2022年6月 由于god、depth、thing不可以同時出現(xiàn)，故有： 其余多于3個集合的交集都為空集。3.3 例第四十九張，PPT共一百五十頁，創(chuàng)作于2022年6月 故滿足要求的排列數(shù)為： 3.3 例第五十張，PPT共一百五十頁，創(chuàng)作于2022年6月 例6。求完全由n個布爾變量確定的布而函數(shù)的個數(shù)。 解：設(shè) 布爾函數(shù)類為： 由于n個布爾變

13、量 的不同的真值表數(shù)目與 位2進(jìn)制數(shù)數(shù)目相同，故為 個。根據(jù)容斥原理，滿足條件的函數(shù)數(shù)目為：3.3 例第五十一張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第五十二張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例這10個布爾函數(shù)為：x1x2，x1x2，x1x2， x1x2，x1x2，x1x2，x1x2， x1x2，(x1x2)(x1x2)， (x1x2)(x1x2)第五十三張，PPT共一百五十頁，創(chuàng)作于2022年6月 例7。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個數(shù)。 解：若n分解為素數(shù)的乘積 設(shè)1到n的n個數(shù)中為 倍數(shù)的集合為則有3.3 例第五十四張，PPT共一百五十頁，創(chuàng)作

14、于2022年6月3.3 例第五十五張，PPT共一百五十頁，創(chuàng)作于2022年6月3.3 例第五十六張，PPT共一百五十頁，創(chuàng)作于2022年6月即比60小且與60無公因子的數(shù)有16個：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一個1。3.3 例第五十七張，PPT共一百五十頁，創(chuàng)作于2022年6月 4 錯排問題 n個元素依次給以標(biāo)號1，2，n。N個元素的全排列中，求每個元素都不在自己原來位置上的排列數(shù)。 設(shè) 為數(shù) 在第 位上的全體排列， =1，2，n。因數(shù)字 不能動，因而有：3.3 例第五十八張，PPT共一百五十頁，創(chuàng)作于2022年6月3.4 錯

15、排問題第五十九張，PPT共一百五十頁，創(chuàng)作于2022年6月每個元素都不在原來位置的排列數(shù)為3.4 錯排問題第六十張，PPT共一百五十頁，創(chuàng)作于2022年6月 例1。數(shù)1，2，9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置的錯排數(shù)目。 解：實際上是1，3，5，7，9五個數(shù)的錯排問題，總數(shù)為：3.4 錯排問題第六十一張，PPT共一百五十頁，創(chuàng)作于2022年6月 例2. 在8個字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個字母不在原來上的錯排數(shù)目。 8個字母的全排列中，令分別表A,C,E,G在原來位置上的排列，則錯排數(shù)為：3.4 錯排問題第六十二張，PPT共一百五十頁，創(chuàng)

16、作于2022年6月3.4 錯排問題第六十三張，PPT共一百五十頁，創(chuàng)作于2022年6月 例3。求8個字母A,B,C,D,E,F,G,H的全排列中只有4個不在原來位置的排列數(shù)。 解：8個字母中只有4個不在原來位置上，其余4個字母保持不動，相當(dāng)于4個元素的錯排，其數(shù)目為3.4 錯排問題第六十四張，PPT共一百五十頁，創(chuàng)作于2022年6月 故8個字母的全排列中有4個不在原來位置上的排列數(shù)應(yīng)為：C(8,4)9=6303.4 錯排問題第六十五張，PPT共一百五十頁，創(chuàng)作于2022年6月5 棋盤多項式和有限制排列1. 有限制排列3.5 棋盤多項式和有限制排列 例4個x ，3個y，2個z的全排列中，求不出現(xiàn)

17、xxxx，yyy，zz圖象的排列。 解設(shè)出現(xiàn)xxxx的排列的集合記為A1， |A1|= =60; 設(shè)出現(xiàn)yyy的排列的集合記為A2， | A2|= =105；6!1!3!2! 4!2! 7!第六十六張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列 設(shè)出現(xiàn)zz的排列的集合記為A3， | A3|= =280； |A1A2|= =12； |A1A3|= =20； |A2A3|= =30； |A1A2A3|=3!=6； 全排列的個數(shù)為： =1260；所以： |A1A2A3|=1260(60+105+280) +(12+20+30)6 =871 4!3!8!4!2!5!3!6!

18、4!9!2!3!4!第六十七張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列2棋子多項式 n個不同元素的一個全排列可看做n個相同的棋子在nn的棋盤上的一個布局。布局滿足同一行（列）中有且僅有一個棋子xxxxx 如圖所示的布局對應(yīng)于排列41352。第六十八張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列 可以把棋盤的形狀推廣到任意形狀： 布子規(guī)定稱為無對攻規(guī)則，棋子相當(dāng)于 象棋中的車。 令r k（C）表示k個棋子布到棋盤C上的方案數(shù)。如：第六十九張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列r1( )=1，r1( )

19、=2，r1( )=2，r2( )=0，r2( )=1。為了形象化起見，（ ）中的圖象便是棋盤的形狀。第七十張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列定義設(shè)C為一棋盤，稱R(C)= rk(C) xk為C的棋盤多項式。規(guī)定 r0(C)=1，包括C=時。設(shè)Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤。在上面定義下，顯然有rk(C)=rk1(Ci)rk(Ce)，k=0第七十一張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列即對任一指定的格子，要么布子，所得的方案數(shù)為 rk1(Ci)；要么不布子，方案數(shù)為

20、rk(Ce)。設(shè)C有n個格子，則 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故規(guī)定 r0(C)1是合理的第七十二張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列即對任一指定的格子，要么布子，所得的方案數(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) (3)k=0k=0k=0k=0第七十三張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列例如：R(

21、 )=1+ x；R( )= xR( )+ R( )= x+ (1+ x)=1+2x；R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2第七十四張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列 如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒有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) (4

22、)第七十五張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列利用（）和（），可以把一個比較復(fù)雜的棋盤逐步分解成相對比較簡單的棋盤，從而得到其棋盤多項式。例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3第七十六張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列有禁區(qū)的排列例設(shè)對于排列P=P1 P2 P3 P4，規(guī)定P1，P、， P2、， P42。 1 2 3 4P1P2P3P412 4 314 3223431

23、 214這樣的排列對應(yīng)于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。第七十七張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列定理設(shè) ri 為 I個棋子布入禁區(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證設(shè)Ai 為第i個棋子布入禁區(qū)，其他棋子任意布的方案集，i =1 , 2 , 3, ,n。第七十八張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列則所有棋子都不布入禁區(qū)的方案數(shù)為A1A2Ann！ (1)kAiI(n ,

24、k)niIk=0而 Ai正是k個棋子布入禁區(qū)，其他n - k個棋子任意布的方案數(shù)。由假設(shè)可知等于rk(nk)！(注意：布入禁區(qū)的棋子也要遵守?zé)o對攻規(guī)則）.所以A1A2An=n!+ (1)k rk ( nk)!I(n , k)iIk=0 n第七十九張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列上例方案數(shù)為 4!6(41)!11(42)!7(43)! 1(4)!4例，四位工人，A，B，C，D四項任務(wù)。條件如下：不干B；不干B、C；不干C、D；不干D。問有多少種可行方案？第八十張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列解由題意，可得如下棋盤

25、： 其中有影線的格子表示禁區(qū)。A B C D1 2 3 4 R( )=1+6x+10 x2+4x3 方案數(shù)=4!6(41)!+10(42)!4(43)! +0(44)!=4第八十一張，PPT共一百五十頁，創(chuàng)作于2022年6月3.5 棋盤多項式和有限制排列例三論錯排問題錯排問題對應(yīng)的是nn的棋盤的主對角線上的格子是禁區(qū)的布子問題。C = R( C ) = ( 1 + x )n = ( ) xk 令rk = ( ) nk=0 n k n k故R(C)中的xn : n! + (1)k ( ) (nk)! = n! (1)k =Pnk=1 n nk=0 k! 1 k n第八十二張，PPT共一百五十頁，

26、創(chuàng)作于2022年6月3.6一般公式 3.6一般公式若將.2中的例子改為“單修一門數(shù)學(xué)的學(xué)生有多少？”“只修一門課的學(xué)生有多少”“只修兩門課的學(xué)生有多少？”則相應(yīng)的答案表示如下：MPC；MPC+MPC+MPCMPC+MPC+MPC第八十三張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式設(shè)有與性質(zhì), 2 , , n相關(guān)的元素N個，Ai為有第 i 種性質(zhì)的元素的集合.i=1,2,nPk為至少有k種性質(zhì)的元素的元次；qk為恰有k種性質(zhì)的元素的個數(shù)。P0 = N，P1 = | A1 | + | A2 | + + | An |，P2 = | A1A2 |+ | A1A3 |+ + | An -

27、1An |Pk = | Aij |qk =| ( Ai) ( Aj)| I(n ,k)i I I(n ,k)i Ij I第八十四張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式定理qk = (1)i( )Pk+i k+i ii=0n-k證設(shè)某一元素恰有k種性質(zhì)，則其對Pk的某一項的貢獻(xiàn)為，而對Pk+1，Pk+2 , ,Pn的貢獻(xiàn)都是。若某一元的性質(zhì)少于k種則其對Pk，Pk+1，Pn的貢獻(xiàn)都是。若恰有k + j種性質(zhì)，則其對Pk的貢獻(xiàn)是( ),對Pk+i的貢獻(xiàn)是（）k + j k k + jk + i第八十五張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式而 (1)i ( )

28、 ( ) = (1)i ( ) ( ) = (1)i ( ) ( ) = ( ) (1)i ( ) = ( ) 0 = 0即某恰有k + j種性質(zhì)的元素對上式右邊的總的貢獻(xiàn)為。k + jk + ik + i ii = 0 ji = 0 jk + jk + ik + i ki = 0 jk + j i j kk + j k j ik + j k第八十六張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式前例中只修一門課的學(xué)生為： | MPC | + | MPC | + | MPC |= q1= (1)j - 1 ( ) Pj= P1 2P2 + 3P3j1j =1 3 在一般公式中，若令

29、P0 = N， q0 = | A1A2An |，就得到原來的容斥原理。第八十七張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式證根據(jù)定義 qk =| ( Ai) ( Aj)|qk由Pk+j的代數(shù)和組成，符號 (1)j ，計算Pk+j的重復(fù)度：k + j個集的交的絕對值的項的總個數(shù)為( ) ( ) , 共 ( )種。每一項的重復(fù)度為 ( ) ( ) ( ) = ( ) 從而Pk+j的重復(fù)度也是 ( ) I(n ,k)i Ij Inkk + jk + jk + jk + jjnknknnnkjkk第八十八張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式qk = (1)j ( )

30、Pk+j = (1)j k ( ) Pjk + jkkjj =0n kkn證對N做歸納。N = 1時，設(shè)此元有m種性質(zhì)，m n ,不妨設(shè)A1 =A2= =Am= a1 。顯然Pj = ( )，若 jm，則 Pj = 0；由定義，得 qk=jm1 k = m0 k m 第八十九張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式右端 (1)i( )Pk+i (1)i( ) ( ) (1)i( ) ( ) = k+i ii=0nkk+i k m k+ii=0nk m k m - k i i=0nk1 k =m0 km假設(shè)對于 N1，等式成立。對于N，設(shè)新增元有m種性質(zhì)，對于N個元的PjPj(

31、 )，qkjm1 k =m0 km第九十張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式右端 (1)i ( )Pk+i (1)i ( ) Pk+ i + ( ) (1)i ( )Pk+i + (1)i ( )( ) qk + 等式成立k + i ki=0nkk + i kk + i mk + i ki=0nkk + i ki=0nkk + i mnk i = 01 k =m0 km第九十一張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式例某校有個教師，已知教數(shù)學(xué)的有位，教物理的有位，教化學(xué)的位；數(shù)、理位，數(shù)、化位，理、化位；數(shù)理化位。問教其他課的有幾位？只教一門的有幾位？只

32、好教兩門的有幾位？解令教數(shù)學(xué)的教師屬于A1，教物理的屬于A2，教化學(xué)的屬于A3。則P0，P1| A1 |+| A2|+| A3 |8+6+5;P2| A1A2|+ | A1A3|+| A2A3|12；P3| A1A2A3|3； 第九十二張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式故教其他課的老師數(shù)為：q0P0 P1 +P2P3恰好一門的教師數(shù)：q1P12P2 + 3P34恰好教兩門的老師數(shù)為：q2P23P33第九十三張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式例n 對夫妻圍坐問題設(shè) n 對夫妻圍圈而坐，男女相間，每個男人都不和他的妻子相鄰，有多少種可能的方案？解不妨

33、設(shè) n 個女人先圍成一圈，方案數(shù)為( n1 )! 。對任一這樣的給定方案，順時針給每個女人以編號1 , 2 , , n。設(shè)第i號與第 i + 1號女人之間的位置為第 i 號位置，1 i n1。第 n 號女人與第1 號之第九十四張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式間的位置為第 n 號位置。設(shè)第 i 號女人的丈夫的編號也為第 i 號，1 i n。讓 n 個男人坐到上述編號的 n 個位置上。設(shè) ai是坐在第 i 號位置上的男人，則 ai i ，i + 1， i n1；ann，1。這樣的限制也即要求在下面3行n列的排列中 nn n1 a1 a2 a3 an1 an第九十五張，PP

34、T共一百五十頁，創(chuàng)作于2022年6月3.6一般公式每列中都無相同元素。滿足這樣的限制的排列 a1a2 an稱為二重錯排。設(shè)二重錯排的個數(shù)為Un，原問題所求的方案數(shù)就是Un ( n1)！。設(shè)Ai為 ai = I 或 I + 1 (1 I n1 )，an = n 或1的排列 a1 a2 an的集合。則Ai= 2 (n1)! ，關(guān)鍵是計算 |Ai|I ( n , k)iI第九十六張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式也就是從( 1 , 2 ) ( 2 , 3 ) ( n, n ) ( n , 1)這n對數(shù)的k 對中各取一數(shù)，且互不相同的取法的計數(shù)。這相當(dāng)于從1 , 2 , 2 ,

35、 3 ,3 ,4, ,n1, n1, n , n , 1中取 k 個互不相鄰數(shù)的組合的計數(shù)，但首尾的不能同時取?；叵霟o重復(fù)不相鄰組合的計數(shù)： C( n , r ) = C ( nr + 1 , r ) ,這里所求的是( )( )= ( ) 2nk+1 k2n4( k2)+1 k22nk k 2n2nk第九十七張，PPT共一百五十頁，創(chuàng)作于2022年6月3.6一般公式 Un =(1)k ( )(nk)! = Ai 2n2nk2nk ki 1 , n 第九十八張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演基本想法：an 易算，bn難算，an可用bn表示，利用反演，將bn用an表示二項式反演

36、引理第九十九張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演證第一百張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演定理證第一百零一張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演推論證在定理中bk處用(1)k bk代入，即可例n! = ( ) Dnk，Dn=bn，令nk = l ，則 n! = ( ) DlDn = (1)n-k ( )k! = n! (1)n-k = n nknknk 1(nk)!k=0k=0k=0nnn(1)k k!第一百零二張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演Mbus反演定義設(shè) n Z+ 1，若 n = 1;( n ) = 0，若n

37、= p11 p22 pkk 存在i1 (1)k ，若n = p1p2pk 如 ( 30) = ( 235 ) = (1)3 ( 12) = 0；第一百零三張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演定理設(shè)n Z+ 則 ( d ) = 1，若n = 1；0，若n 1；d | n證若n =1， ( d ) = ( 1 ) = 1,成立若 n1，設(shè)n = p11 p22 pkk ，n = p1p2pk ( d ) = ( d ) = ( pi ) +(1) =1 + ( ) (1)j = (11)k = 0d | nd | nd | nj=1kiII(k, j)kjj=1k第一百零四張，P

38、PT共一百五十頁，創(chuàng)作于2022年6月.11反演推論(n) = n (d ) dd | n證n = n = n 1 + (1)j ( pi )1 = n (1 ) = (n) (d ) dd | n (d ) dd | n1pij =1i =1kkI (k , j )i I第一百零五張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演定理( Mbus反演定理 )設(shè) f ( n )和g ( n )是定義在正整數(shù)集合上的兩個函數(shù) f ( n ) = g (d ) = g ( ) (M1 ) g( n ) = (d) f ( ) = ( )f (d) (M2) ndndd | nd | nd |

39、nd | n則( M1 ) ( M2 ) nd第一百零六張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演證“”設(shè)( M1 )成立。(d) f ( ) = (d) g ( d1 )= (d) g ( d1 ) = (d) g( d1 ) = (d) g ( d1 ) = g(d1 ) (d) = (d) = = g( n )d | nd | nd | ndd1 | nd1 | nnd1d | nd1d | d1 | nndd1 | ndd1 | ndnd1d | 1，d1 = n0，d1 n第一百零七張，PPT共一百五十頁，創(chuàng)作于2022年6月.11反演“”：設(shè)（M2）成立。 g (d )

40、 = g (d )= ( d ) f ( d1 ) =( d ) f ( d1 )= f ( d1 ) ( d ) = ( d ) = ( d ) = f ( n )d | nd | nd | nndd1 | nd1d | nd1d | nd1d | d1 | ndd1 | n1，d1 = n0，d1 h，使得 ah + ah+1 + + ak = 39 證令Sj = ai，j =1 , 2 , ,100顯然S1S2hSkSh =39 即 ah + ah+1 + + ak = 39 第一百一十八張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二鴿巢原理二m1 , m2 , , mn都

41、是正整數(shù)，并有m1 + m2 + +mnn + 1個鴿子住進(jìn)n個鴿巢，則至少對某個 i 有第 i 個巢中至少有mi個鴿子，i = 1 , 2 , , n上一小節(jié)的鴿巢原理一是這一原理的特殊情況，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1如若不然，則對任一 i， 都有第 i 個巢中的鴿子數(shù)mi1則第一百一十九張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二鴿子總數(shù) m1 + m2 + +mnn ，與假設(shè)相矛盾推論m只鴿子進(jìn)n個巢，至少有一個巢里有 |只鴿子nm推論n(m1) + 1只鴿子進(jìn)n個巢，至少有一個巢內(nèi)至少有m只鴿子推論若m1

42、 , m2 , , mn是正整數(shù)，且 r1,則 m1, , mn至少有一個不小于rm1 + +mn n第一百二十張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二例設(shè)A= a1a2a20是10個0和10個1 組成的進(jìn)制數(shù)B=b1b2b20是任意的進(jìn)制數(shù)C = b1b2b20 b1b2b20 = C1C2C40，則存在某個i ，1 i 20，使得CiCi+1Ci+19與a1a2a20至少有10位對應(yīng)相等. . . . .ABC第 i 格第 i +19格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20第一百二十一張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿

43、巢原理之二證在C = C1C2C40中，當(dāng) i 遍歷1 , 2 , ,20時，每一個bj歷遍 a1 , a2 , , a20因A中有10個0和10個1，每一個bj都有10位次對應(yīng)相等從而當(dāng) i歷遍1 , , 20時，共有10 20=200位次對應(yīng)相等故對每個 i平均有200 20 = 10位相等，因而對某個 i 至少有10位對應(yīng)相等第一百二十二張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二定理若序列S = a1 , a2 , , amn+1中的各數(shù)是不等的m , n 是正整數(shù)，則 S有一長度為m+1的嚴(yán)格增子序列或長度為n+1的減子序列，而且 S有一長度為m+1的減子序列或長度為

44、n+1的增子序列證由S中的每個 ai 向后選取最長增子序列，設(shè)其長度為li ，從而得序列L = l1 , l2 , , lmn+1 若存在 lkm+1則結(jié)論成立第一百二十三張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二否則所有的 li 1 , m，其中必有 | = n+1個相等設(shè)li1 = li2 = = lin= lin+1 不妨設(shè) i1i2 ai2 ain+1 ，即有一長度為n+1的減子列否則不妨設(shè)ai1 li2 ，矛盾mn+1 m第一百二十四張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二證從ai 向后取最長增子列及減子列，設(shè)其長度分別為 li ，li .若任意

45、 i ，都有l(wèi)i 1，m, li，n,不超過mn種對則存在 j k，( lj , lj ) = ( lk , lk )若aj lk，若aj ak，則 lj lk ，矛盾第一百二十五張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二例將 1 , 65 劃分為個子集，必有一個子集中有一數(shù)是同子集中的兩數(shù)之差證用反證法設(shè)次命題不真即存在劃分P1 P2 P3P4 1，65 ，Pi中不存在一個數(shù)是Pi中兩數(shù)之差，i=1,2,3,4因 = 17，故有一子集，其中至少有17個數(shù)，設(shè)這17個數(shù)從小到大為a1 , , a17 不妨設(shè) A=a1 , , a17 P1。令bi1= aia1，i = 2，1

46、7。65 4第一百二十六張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二設(shè)Bb1 , , b16，B 1 , 65 。由反證法假設(shè)BP1 = 。因而 B ( P2 P3 P4 )。 因為 6，不妨設(shè)b1 , , b6 P2 ， 令Ci1=bib1，I = 2， ，6設(shè)C C1 , , C5 ，C 1 , 65 由反證法假設(shè)C( P1P2 ) =，故有 C (P3P4 )因為 3，不妨設(shè)C1 , C2 , C3 P316 352第一百二十七張，PPT共一百五十頁，創(chuàng)作于2022年6月.8鴿巢原理之二令di1= CiC1，I = 2 , 3設(shè)D d1 , d2 , D 1 , 65。由

47、反證法假設(shè) D( P1P2P3 )=，因而 D P4。由反證法假設(shè) d2d1 P1P2P3 且d2d1 P4 ，故 d2d1 1 , 65 ，但顯然 d2d1 1 , 65 ，矛盾。第一百二十八張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題Ramsey問題 Ramsey問題可以看成是鴿巢原理的推廣下面舉例說明Ramsey問題例6 個人中至少存在人相互認(rèn)識或者相互不認(rèn)識證這個問題與K6的邊著色存在同色三角形等價假定用紅藍(lán)著色第一百二十九張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題設(shè)K6的頂點集為v1 , v2 , , v6 ，dr(v)表示與頂點 v 關(guān)

48、聯(lián)的紅色邊的條數(shù)，db(v)表示與 v 關(guān)聯(lián)的藍(lán)色邊的條數(shù)在K6 中，有dr(v) db(v)，由鴿巢原理可知，至少有條邊同色現(xiàn)將證明過程用判斷樹表示如下：第一百三十張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題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第一百三十一張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題若干推論( a )K6的邊用紅藍(lán)

49、任意著色，則至少有兩個同色的三角形證由前定理知，有同色三角形，不妨設(shè)v1v2v3是紅色三角形可由如下判斷樹證明第一百三十二張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題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è) (

50、v5v6)為紅邊yyyyyynnnnn第一百三十三張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題( b )K9 的邊紅藍(lán)兩色任意著色，則必有紅K4或藍(lán)色三角形(藍(lán)K4或紅色三角形)證設(shè)個頂點為 v1 , v2 , , v9對個頂點的完全圖的邊的紅、藍(lán)著色圖中，必然存在 vi ，使得 dr(vi)3 否則，紅邊數(shù) dr(vi) ，這是不可能的不妨設(shè) dr(v1)3，可得如下判斷樹證明結(jié)論1227 2第一百三十四張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題dr(v1)4?db(v1)6設(shè)(v1v2) (v1v3) (v1v4)(v1v5)是4紅邊設(shè)(v1v

51、2) (v1v7)是6條藍(lán)邊K4(v2v3v4v5)是藍(lán)K4 ?K6(v2v7)中有紅 ?設(shè)(v2v3)是紅邊v1v2v3是紅設(shè)v2v3v4是紅K4(v2v3v4v5)是藍(lán)K4YYYNNN第一百三十五張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題K9的邊紅、藍(lán)著色，必有紅色三角形或藍(lán)色K4同理可證 K9的紅、藍(lán)著色，必有藍(lán)色三角形或紅色K4 (紅 藍(lán)K4) (藍(lán) 紅K4)存在同色K4或紅及藍(lán) 同色K4 (紅 藍(lán) )第一百三十六張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題( c )K18的邊紅，藍(lán)著色，存在紅K4或藍(lán)K4 證設(shè)18個頂點為v1 , v2

52、, , v18 從v1引出的17條邊至少有條是同色的，不妨先假定為紅色從而可得下面的判斷樹證明命題第一百三十七張，PPT共一百五十頁，創(chuàng)作于2022年6月.9Ramsey 問題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第一百三十八張，PPT共一百五十頁，創(chuàng)作于2022年6月.10Ramsey數(shù)將上一節(jié)的問題一般化：給定一對正整數(shù)a、b，存在一個最小的正整數(shù) r ,對 r 個頂點的完全圖的邊任意紅、藍(lán)著色，存在 a 個頂點的紅邊完全圖或 b 個頂點的藍(lán)邊完全圖。記為 r ( a , b )。比如：r ( 3 , 3 )6，r ( 3 , 4