1、關于組合數學第三章容斥原理和鴿巢原理第一頁，共150頁幻燈片 3的倍數是：3，6，9，12，15， 18。 6個 但答案不是10+6=16 個，因為6， 12，18在兩類中重復計數，應減 去。故答案是：16-3=133.2 容斥原理容斥原理第二頁，共150頁幻燈片 容斥原理容斥原理研究有限集合的研究有限集合的交或并交或并 的計數的計數。 DeMorgan定理定理 論域論域U，補集補集,有有3.2 容斥原理容斥原理(a)ABAB(b)ABAB第三頁，共150頁幻燈片證證：(a)的證明。設 ,則 相當于 和同時成立，亦即 BAxBAxBAxAxBxAABxAB(1)3.2 容斥原理容斥原理第四頁，

2、共150頁幻燈片反之，若xABxAxB, 即和故.xAxBxAB和亦即xxBAAB (2)由（1）和（2）得xBAABx(b)的證明和（的證明和（a)類似，從略類似，從略.3.2 容斥原理容斥原理第五頁，共150頁幻燈片DeMogan定理的推廣：設1,2,.,nA AAU是 的子集212.nnAAAAA1則 (a)A212.nnAAAAA1(b)A 證明證明：只證(a). N=2時定理已證。設定理對n是正確的，即假定：3.2 容斥原理容斥原理第六頁，共150頁幻燈片212.nnAAAAA1A正確2112121111.(.)(.nnnnnnnnAAAAAAAAAAAAAA1則 A即定理對n+1也

3、是正確的。3.2 容斥原理容斥原理第七頁，共150頁幻燈片2 容斥原理容斥原理 最簡單的計數問題是求有限集合A和B的并的元素數目。顯然有即具有性質A或B的元素的個數等于具ABABAB(1)定理定理：3.2 容斥原理容斥原理第八頁，共150頁幻燈片有性質A和B的元素個數。UBAAB3.2 容斥原理容斥原理第九頁，共150頁幻燈片3.2 容斥原理容斥原理證證若AB=，則 | AB |= |A| + |B| A | A ( BB) | | (AB)(AB)| | AB | + | AB | ( 1 )同理| B | | BA | + | BA | ( 2 )| AB |(A( BB)(B(AA)|(

4、AB)(AB)(BA)(BA)| AB| + |AB | + | BA| ( 3 )第十頁，共150頁幻燈片3.2 容斥原理容斥原理( 3 ) ( 1 ) ( 2 ) 得| AB | A | B | AB| + |AB | + | BA| ( | AB | + | AB | ) ( | BA | + | BA | ) | AB | | AB | A | + | B | AB |第十一頁，共150頁幻燈片定理：定理：(2)ABCABCABBCABC AC- ：()()ABCABCABCABC證明3.2 容斥原理容斥原理第十二頁，共150頁幻燈片()()()()()ABCACBCABCABCABA

5、CBCABCABBCABC根據 C- A 3.2 容斥原理容斥原理第十三頁，共150頁幻燈片ABCACBCABABC3.2 容斥原理容斥原理第十四頁，共150頁幻燈片 例例 一個學校只有三門課程：數學、物理、化學。已知修這三門課的學生分別有170、130、120人；同時修數學、物理兩門課的學生45人；同時修數學、化學的20人；同時修物理化學的22人。同時修三門的3人。問這學校共有多少學生？3.2 容斥原理容斥原理第十五頁，共150頁幻燈片令：令：M為修數學的學生集合； P 為修物理的學生集合； C 為修化學的學生集合；170,130,120,4520,22,3PCMPMCPCMPCM3.2 容

6、斥原理容斥原理第十六頁，共150頁幻燈片170 130 12045 2022 3336MPCPCMP MMCPCMPCM 即學校學生數為336人。3.2 容斥原理容斥原理第十七頁，共150頁幻燈片同理可推出：ABCDABCDABBCADABCABDBCDABCD AC 利用數學歸納法可得一般的定理：3.2 容斥原理容斥原理第十八頁，共150頁幻燈片 定理定理設(n,k)是1,n的所有k-子集的集合, 則 |Ai | = (1)k-1 | Ai |證證對n用歸納法。n=2時，等式成立。 假設對n - 1，等式成立。對于n有 3.2 3.2 容斥原理容斥原理ni=1k=1n I(n,k)iI第十九

7、頁，共150頁幻燈片3.2 3.2 容斥原理容斥原理1i111111111111111A()( 1)( 1)()nniniinnininiinnininiinnkkininkki IAAAAAAAAAAAAAA I(n-1,k) I(n-1,k)iI第二十頁，共150頁幻燈片3.2 3.2 容斥原理容斥原理111121211( 1)( 1)( 1)nnkiinikiInkinkiInkikiIAAAAAA I(n,k) I(n-1,k-1) I(n-1,k)此定理也可表示為：第二十一頁，共150頁幻燈片定理：定理：設1,2,.,nA AA是有限集合，則1211112.( 1).nnniijii

8、jiknjnAAAAAAAAAAAnii=1 ji kj +A(4)3.2 容斥原理容斥原理第二十二頁，共150頁幻燈片 證：證：用數學歸納法證明。已知 n=2時有121212AAAAAA設 n-1時成立，即有：3.2 容斥原理容斥原理3.2 容斥原理容斥原理第二十三頁，共150頁幻燈片1211111121.( 1).nnniijiij ijknnAAAAAAAAAAAn-1ii=1 ji kjA+ 3.2 容斥原理容斥原理第二十四頁，共150頁幻燈片121121121121.(.).(.)nnnnnnnnAAAAAAAAAAAAAAAA 3.2 容斥原理容斥原理第二十五頁，共150頁幻燈片1

9、2112.)()().),nnnnnAAAAAAAAAn-1但 ( (A3.2 容斥原理容斥原理第二十六頁，共150頁幻燈片1211211211213(.)()().().nnnnnnnnnnnnAAAAAAAAAAAAAAAAAAAAAA 3.2 容斥原理容斥原理第二十七頁，共150頁幻燈片2112111112. ( 1).( 1).nnnnnnninijniij innAAAAAAAAAAAAAA 3.2 容斥原理容斥原理第二十八頁，共150頁幻燈片12111112.( 1).nnnniijiiinnjjkAAAAAAAAAAAA nii=1 ji kj A+ 3.2 容斥原理容斥原理第二

10、十九頁，共150頁幻燈片,NA又 A其中N是集合U的元素個數，即不屬于A的元素個數等于集合的全體減去屬于A的元素的個數。一般有：3.2 容斥原理容斥原理第三十頁，共150頁幻燈片121211112.( 1).nnnnniijiijjkninAAANAAAANAAAAAAAAnii=1 ji kj A- (5)容斥原理指的就是（4）和（5）式。3.2 容斥原理容斥原理第三十一頁，共150頁幻燈片3 例例 例例1 求a,b,c,d,e,f六個字母的全排列中不允許出現ace和df圖象的排列數。 解：解：設A為ace作為一個元素出現的排列集，B為 df作為一個元素出現的排列集， 為同時出現ace、df

11、的排列數。AB3.3 例例第三十二頁，共150頁幻燈片4!,5!,3!.ABAB根據容斥原理，不出現ace和df的排列數為：AB=6!- (5!+4!)+3!=582 3.3 例例第三十三頁，共150頁幻燈片 例例2 求從1到500的整數中能被3或5除盡的數的個數。 解：解： 令A為從1到500的整數中被3除盡的數的集合，B為被5除盡的數的集合500500166,100;355003315ABAB3.3 例例第三十四頁，共150頁幻燈片被3或5除盡的數的個數為166 10033233ABABAB 例例3 求由a,b,c,d四個字母構成的位符號串中，a,b,c,d至少出現一次的符號串數目。3.3

12、 例例第三十五頁，共150頁幻燈片 解：解：令A、B、C分別為n位符號串中不出現a，b，c符號的集合。 由于n位符號串中每一位都可取a，b，c，d四種符號中的一個，故不允許出現a的n位符號串的個數應是3n，即32nnBCABACCBA3.3 例例第三十六頁，共150頁幻燈片1ABC a，b，c至少出現一次的n位符號串集合即為ABC4()(33 243)1nnnnABCABACCBABCABC 3.3 例例第三十七頁，共150頁幻燈片 例例4。求不超過120的素數個數。 因 ，故不超過120的合數必然是2、3、5、7的倍數，而且不超過120的合數的因子不可能都超過11。 設 為不超過120的數

13、的倍數集， =2，3，5，7。211121iAii3.3 例例第三十八頁，共150頁幻燈片2357232527351201206040231201202417,571201202012,2 310120120881415AAAAAAAAAAAA，3.3 例例第三十九頁，共150頁幻燈片375723523725712012053213512042 3 512022 3 712012 5 7AAAAAAAAAAAAA ，3.3 例例第四十頁，共150頁幻燈片235723572325273537572352372573572357120AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

14、AAAA 3.3 例例第四十一頁，共150頁幻燈片120(604024 17)(20 128853)(42 1 1)27. 3.3 例例第四十二頁，共150頁幻燈片 注意：注意：27并非就是不超過120的素數個數，因為這里排除了2，3，5，7著四個數，又包含了1這個非素數。2，3，5，7本身是素數。故所求的不超過120的素數個數為： 27+4-1=303.3 例例第四十三頁，共150頁幻燈片 例例5。用26個英文字母作不允許重復的全排列，要求排除dog，god，gum，depth，thing字樣的出現，求滿足這些條件的排列數。 解：解：所有排列中，令：3.3 例例第四十四頁，共150頁幻燈片1

15、2345AdogAgodAgumAdepthAthing為出現的排列的全體；為出現的排列的全體；為出現的排列的全體；為出現的排列的全體；為出現的排列的全體；3.3 例例第四十五頁，共150頁幻燈片 出現dog字樣的排列，相當于把dog作為一個單元參加排列，故24!1A類似有：234524!，22!AAAA 由于god,dog不可能在一個排列中同 時出現，故： 120;AA 類似：類似：23140，0AAAA3.3 例例第四十六頁，共150頁幻燈片 由于gum,dog可以在dogum字樣中同時出現，故有：1322!AA 類似有god和depth可以在godepth字樣中同時出現，故2420!AA

16、 god和thing可以在thingod字樣中同時出現，從而 2520!AA 3.3 例例第四十七頁，共150頁幻燈片154534351231241251341351450，19!，20!，0，00，00，0AAAAAAAAAAAAAAAAAAAAAAAAAA3.3 例例第四十八頁，共150頁幻燈片2342350，0AAAAAA 由于god、depth、thing不可以同時出現，故有：2450AAA 34517!AAA 其余多于3個集合的交集都為空集。3.3 例例第四十九頁，共150頁幻燈片 故滿足要求的排列數為： 26! 3 24! 2 22! 22! 4 20! 19! 17!26! 3

17、24! 22! 4 20! 19! 17! 3.3 例例第五十頁，共150頁幻燈片 例例6。求完全由n個布爾變量確定的布而函數的個數。 解：解：設12( ,.,)nif x xxx中 不出現的 布爾函數類為： ，1,2,., .iniA 由于n個布爾變量 的不同的真值表數目與 位2進制數數目相同，故為 個。根據容斥原理，滿足條件的函數數目為：12,.,nx xx2n22n3.3 例例第五十一頁，共150頁幻燈片12221222.2( ,1)2( ,2)2.( 1)( , )2.( 1)( , )2nnnn knknAAAC nC nC n kC n n 22222，2(2,1)2(2,2)21

18、6 8210nACC 1時得 A 3.3 例例第五十二頁，共150頁幻燈片3.3 例例這10個布爾函數為：x1x2，x1x2，x1x2， x1x2，x1x2，x1x2，x1x2， x1x2，(x1x2)(x1x2)， (x1x2)(x1x2)第五十三頁，共150頁幻燈片 例例7。歐拉函數(n)是求小于n且與n互素的數的個數。 解：解：若n分解為素數的乘積1212.kaaaknppp 設1到n的n個數中為 倍數的集合為ip，1,2,., .ikiA則有則有3.3 例例第五十四頁，共150頁幻燈片1212.，1,2,., .， ,1,2,. ,.kaaakiiijijnppppnAikpnAAi

19、jk ijp p ?. 3.3 例例第五十五頁，共150頁幻燈片1212121311212.(.)(.)111(1)(1)(1)kknkkAAAnnnnnpppp pnnnp pp pp ppnppp(n)= 3.3 例例第五十六頁，共150頁幻燈片26023 5，111(60)60(1)(1)(1)16235n 例如則即比60小且與60無公因子的數有16個：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一個1。3.3 例例第五十七頁，共150頁幻燈片 4 錯排問題錯排問題 n個元素依次給以標號1，2，n。N個元素的全排列中，求每個元素都不在自

20、己原來位置上的排列數。 設 為數 在第 位上的全體排列， =1，2，n。因數字 不能動，因而有：iAiiii3.3 例例第五十八頁，共150頁幻燈片(1)!，1,2,.,iAnin(2)!,1,2,., ,ijAAnin ij同理 3.4 錯排問題錯排問題第五十九頁，共150頁幻燈片每個元素都不在原來位置的排列數為1211.!( ,1)(1)1!(1!( ,2)(2)1!2!( , )1!nAAAnC nnC nnnnC n n 3.4 錯排問題錯排問題第六十頁，共150頁幻燈片 例例1。數1，2，9的全排列中，求偶數在原來位置上，其余都不在原來位置的錯排數目。 解：解：實際上是1，3，5，7

21、，9五個數的錯排問題，總數為：5!(5,1)4!(5,2)3!(5,3)2!(5,4)1!1111(5,5)120()442624120CCCCC3.4 錯排問題錯排問題第六十一頁，共150頁幻燈片 例例2. 在8個字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個字母不在原來上的錯排數目。 8個字母的全排列中，令分別表A,C,E,G在原來位置上的排列，則錯排數為：1234,A A A A3.4 錯排問題錯排問題第六十二頁，共150頁幻燈片12348!(4,1)7!(4,2)6!(4,3)5!(4,4)4!24024AAAACCCC 3.4 錯排問題錯排問題第六十三頁，共15

22、0頁幻燈片 例例3。求8個字母A,B,C,D,E,F,G,H的全排列中只有4個不在原來位置的排列數。 解：解：8個字母中只有4個不在原來位置上，其余4個字母保持不動，相當于4個元素的錯排，其數目為3.4 錯排問題錯排問題第六十四頁，共150頁幻燈片1111!(1)1!2!3!4!11124(1 1)926244 故8個字母的全排列中有4個不在原來位置上的排列數應為：C(8,4)9=6303.4 錯排問題錯排問題第六十五頁，共150頁幻燈片5 棋盤多項式和有限制排列棋盤多項式和有限制排列1. 有限制排列有限制排列3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列 例例4個x ，3個y，2個z的

23、全排列中，求不出現xxxx，yyy，zz圖象的排列。 解解設出現xxxx的排列的集合記為A1， |A1|= =60; 設出現yyy的排列的集合記為A2， | A2|= =105；6!1!3!2! 4!2! 7!第六十六頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列 設出現zz的排列的集合記為A3， | A3|= =280； |A1A2|= =12； |A1A3|= =20； |A2A3|= =30； |A1A2A3|=3!=6； 全排列的個數為： =1260；所以： |A1A2A3|=1260(60+105+280) +(12+20+30)6 =871 4!3!8!4

24、!2!5!3!6!4!9!2!3!4!第六十七頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列2棋子多項式 n個不同元素的一個全排列可看做n個相同的棋子在nn的棋盤上的一個布局。布局滿足同一行（列）中有且僅有一個棋子xxxxx 如圖所示的布局對應于排列41352。第六十八頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列 可以把棋盤的形狀推廣到任意形狀： 布子規定稱為無對攻規則，棋子相當于 象棋中的車。 令r k（C）表示k個棋子布到棋盤C上的方案數。如：第六十九頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列r1( )=1

25、，r1( )=2，r1( )=2，r2( )=0，r2( )=1。為了形象化起見，（ ）中的圖象便是棋盤的形狀。第七十頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列定義定義設C為一棋盤，稱R(C)= rk(C) xk為C的棋盤多項式。規定 r0(C)=1，包括C=時。設Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤。在上面定義下，顯然有rk(C)=rk1(Ci)rk(Ce)，k=0第七十一頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列即對任一指定的格子，要么布子，所得的方案數為 rk1(Ci)；要么不布子

26、，方案數為 rk(Ce)。設C有n個格子，則 r1(C)nr1(C)r0(Ci) + r1(Ce)，r1(Ce)n1 r0(Ci)1故規定 r0(C)1是合理的第七十二頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列即對任一指定的格子，要么布子，所得的方案數為 rk1(Ci)；要么不布子，方案數為 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第七十三頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列例

27、如：R( )=1+ x；R( )= xR( )+ R( )= x+ (1+ x)=1+2x；R( )= x R( ) + R( ) = x(1 + x )+1 + x =1+ 2x +x2第七十四頁，共150頁幻燈片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)

28、 (4)第七十五頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列利用（）和（），可以把一個比較復雜的棋盤逐步分解成相對比較簡單的棋盤，從而得到其棋盤多項式。例例R ( ) = xR( )+R( ) = x(1+ x)2 +(1+2x)2 =1+ 5x +6x2 + x3*R( ) = xR( ) + R( ) = 1+6x +10 x2 +4x3第七十六頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列有禁區的排列例設對于排列P=P1 P2 P3 P4，規定P1，P、， P2、， P42。 1 2 3 4P1P2P3P412 4 314 32234

29、31 214這樣的排列對應于有禁區的布子。如右圖有影線的格子表示禁區。第七十七頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列定理定理設 ri 為 I個棋子布入禁區的方案數，i =1,2,3,n。有禁區的布子方案數（即禁區內不布子的方案數）為 r0 n! r1(n1)! r2(n2)!(1)nrn(1)k rk ( nk)! k=0n證證設Ai 為第i個棋子布入禁區，其他棋子任意布的方案集，i =1 , 2 , 3, ,n。第七十八頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列則所有棋子都不布入禁區的方案數為A1A2Ann！ (1)kAiI(n

30、 , k)niIk=0而 Ai正是k個棋子布入禁區，其他n - k個棋子任意布的方案數。由假設可知等于rk(nk)！(注意：布入禁區的棋子也要遵守無對攻規則）.所以A1A2An=n!+ (1)k rk ( nk)!I(n , k)iIk=0 n第七十九頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列上例方案數為 4!6(41)!11(42)!7(43)! 1(4)!4例例，四位工人，A，B，C，D四項任務。條件如下：不干B；不干B、C；不干C、D；不干D。問有多少種可行方案？第八十頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列解由題意，可得如下

31、棋盤： 其中有影線的格子表示禁區。A B C D1 2 3 4 R( )=1+6x+10 x2+4x3 方案數=4!6(41)!+10(42)!4(43)! +0(44)!=4第八十一頁，共150頁幻燈片3.5 棋盤多項式和有限制排列棋盤多項式和有限制排列例例三論錯排問題錯排問題對應的是nn的棋盤的主對角線上的格子是禁區的布子問題。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第八十二頁，共150頁幻燈片

32、3.6一般公式一般公式 3.6一般公式若將.2中的例子改為“單修一門數學的學生有多少？”“只修一門課的學生有多少”“只修兩門課的學生有多少？”則相應的答案表示如下：MPC；MPC+MPC+MPCMPC+MPC+MPC第八十三頁，共150頁幻燈片3.6一般公式一般公式設有與性質, 2 , , n相關的元素N個，Ai為有第 i 種性質的元素的集合.i=1,2,nPk為至少有k種性質的元素的元次；qk為恰有k種性質的元素的個數。P0 = N，P1 = | A1 | + | A2 | + + | An |，P2 = | A1A2 |+ | A1A3 |+ + | An - 1An |Pk = | Ai

33、j |qk =| ( Ai) ( Aj)| I(n ,k)i I I(n ,k)i Ij I第八十四頁，共150頁幻燈片3.6一般公式一般公式定理qk = (1)i( )Pk+i k+i ii=0n-k證證設某一元素恰有k種性質，則其對Pk的某一項的貢獻為，而對Pk+1，Pk+2 , ,Pn的貢獻都是。若某一元的性質少于k種則其對Pk，Pk+1，Pn的貢獻都是。若恰有k + j種性質，則其對Pk的貢獻是( ),對Pk+i的貢獻是（）k + j k k + jk + i第八十五頁，共150頁幻燈片3.6一般公式一般公式而 (1)i ( ) ( ) = (1)i ( ) ( ) = (1)i (

34、) ( ) = ( ) (1)i ( ) = ( ) 0 = 0即某恰有k + j種性質的元素對上式右邊的總的貢獻為。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第八十六頁，共150頁幻燈片3.6一般公式一般公式前例中只修一門課的學生為： | MPC | + | MPC | + | MPC |= q1= (1)j - 1 ( ) Pj= P1 2P2 + 3P3j1j =1 3 在一般公式中，若令 P0 = N， q0 = | A1A2An |，就得到原來的容斥原理。第八

35、十七頁，共150頁幻燈片3.6一般公式一般公式證證根據定義 qk =| ( Ai) ( Aj)|qk由Pk+j的代數和組成，符號 (1)j ，計算Pk+j的重復度：k + j個集的交的絕對值的項的總個數為( ) ( ) , 共 ( )種。每一項的重復度為 ( ) ( ) ( ) = ( ) 從而Pk+j的重復度也是 ( ) I(n ,k)i Ij Inkk + jk + jk + jk + jjnknknnnkjkk第八十八頁，共150頁幻燈片3.6一般公式一般公式qk = (1)j ( )Pk+j = (1)j k ( ) Pjk + jkkjj =0n kkn證證對N做歸納。N = 1時，

36、設此元有m種性質，m n ,不妨設A1 =A2= =Am= a1 。顯然Pj = ( )，若 jm，則 Pj = 0；由定義，得 qk=jm1 k = m0 k m 第八十九頁，共150頁幻燈片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假設對于 N1，等式成立。對于N，設新增元有m種性質，對于N個元的PjPj( )，qkjm1 k =m0 km第九十頁，共150頁幻燈片3.6一般公式一般公式右端 (1)i ( )Pk+i (1

37、)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第九十一頁，共150頁幻燈片3.6一般公式一般公式例例某校有個教師，已知教數學的有位，教物理的有位，教化學的位；數、理位，數、化位，理、化位；數理化位。問教其他課的有幾位？只教一門的有幾位？只好教兩門的有幾位？解解令教數學的教師屬于A1，教物理的屬于A2，教化學的屬于A3。則P0，P1| A1 |+| A2|+| A3 |8+6+5;P2

38、| A1A2|+ | A1A3|+| A2A3|12；P3| A1A2A3|3； 第九十二頁，共150頁幻燈片3.6一般公式一般公式故教其他課的老師數為：q0P0 P1 +P2P3恰好一門的教師數：q1P12P2 + 3P34恰好教兩門的老師數為：q2P23P33第九十三頁，共150頁幻燈片3.6一般公式一般公式例例n 對夫妻圍坐問題設 n 對夫妻圍圈而坐，男女相間，每個男人都不和他的妻子相鄰，有多少種可能的方案？解解不妨設 n 個女人先圍成一圈，方案數為( n1 )! 。對任一這樣的給定方案，順時針給每個女人以編號1 , 2 , , n。設第i號與第 i + 1號女人之間的位置為第 i 號位

39、置，1 i n1。第 n 號女人與第1 號之第九十四頁，共150頁幻燈片3.6一般公式一般公式間的位置為第 n 號位置。設第 i 號女人的丈夫的編號也為第 i 號，1 i n。讓 n 個男人坐到上述編號的 n 個位置上。設 ai是坐在第 i 號位置上的男人，則 ai i ，i + 1， i n1；ann，1。這樣的限制也即要求在下面3行n列的排列中 nn n1 a1 a2 a3 an1 an第九十五頁，共150頁幻燈片3.6一般公式一般公式每列中都無相同元素。滿足這樣的限制的排列 a1a2 an稱為二重錯排。設二重錯排的個數為Un，原問題所求的方案數就是Un ( n1)！。設Ai為 ai =

40、I 或 I + 1 (1 I n1 )，an = n 或1的排列 a1 a2 an的集合。則Ai= 2 (n1)! ，關鍵是計算 |Ai|I ( n , k)iI第九十六頁，共150頁幻燈片3.6一般公式一般公式也就是從( 1 , 2 ) ( 2 , 3 ) ( n, n ) ( n , 1)這n對數的k 對中各取一數，且互不相同的取法的計數。這相當于從1 , 2 , 2 , 3 ,3 ,4, ,n1, n1, n , n , 1中取 k 個互不相鄰數的組合的計數，但首尾的不能同時取。回想無重復不相鄰組合的計數： C( n , r ) = C ( nr + 1 , r ) ,這里所求的是( )

41、( )= ( ) 2nk+1 k2n4( k2)+1 k22nk k 2n2nk第九十七頁，共150頁幻燈片3.6一般公式一般公式 Un =(1)k ( )(nk)! = Ai 2n2nk2nk ki 1 , n 第九十八頁，共150頁幻燈片.11反演反演基本想法：an 易算，bn難算，an可用bn表示，利用反演，將bn用an表示二項式反演二項式反演1(1)0，nmkkmnknkmmn ， m引理引理第九十九頁，共150頁幻燈片.11反演反演證證0(1)(1)10，nkmmnminnmmkmnnmmimnmn 左 邊，第一百頁，共150頁幻燈片.11反演反演定理定理00( 1)( 1)nnkk

42、nknkkknnabbakk 000000000( 1)( 1)( 1)( 1)( 1)( 1)( 1)nnnkklklkklnkkllklnkkllklnnkllnlknnkabkklnkbklnkbklnkbbkl 證證第一百零一頁，共150頁幻燈片.11反演反演00( 1)nnn knknkkknnabbakk推論證在定理中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!第一百零二頁，共15

43、0頁幻燈片.11反演反演Mbus反演定義設 n Z+ 1，若 n = 1;( n ) = 0，若n = p11 p22 pkk 存在i1 (1)k ，若n = p1p2pk 如 ( 30) = ( 235 ) = (1)3 ( 12) = 0；第一百零三頁，共150頁幻燈片.11反演反演定理定理設n Z+ 則 ( d ) = 1，若n = 1；0，若n 1；d | n證證若n =1， ( d ) = ( 1 ) = 1,成立若 n1，設n = p11 p22 pkk ，n = p1p2pk ( d ) = ( d ) = ( pi ) +(1) =1 + ( ) (1)j = (11)k =

44、0d | nd | nd | nj=1kiII(k, j)kjj=1k第一百零四頁，共150頁幻燈片.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第一百零五頁，共150頁幻燈片.11反演反演定理定理( Mbus反演定理 )設 f ( n )和g ( n )是定義在正整數集合上的兩個函數 f ( n ) = g (d ) = g ( ) (M1 ) g( n ) = (d) f ( ) = ( )f

45、 (d) (M2) ndndd | nd | nd | nd | n則( M1 ) ( M2 ) nd第一百零六頁，共150頁幻燈片.11反演反演證證“”設( 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第一百零七頁，共150頁幻燈片.11反演反演“”：設（M2）成

46、立。 g (d ) = 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 第一百一十八頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二鴿巢原理二鴿巢原理二m1 , m

47、2 , , mn都是正整數，并有m1 + m2 + +mnn + 1個鴿子住進n個鴿巢，則至少對某個 i 有第 i 個巢中至少有mi個鴿子，i = 1 , 2 , , n上一小節的鴿巢原理一是這一原理的特殊情況，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1如若不然，則對任一 i， 都有第 i 個巢中的鴿子數mi1則第一百一十九頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二鴿子總數 m1 + m2 + +mnn ，與假設相矛盾推論推論m只鴿子進n個巢，至少有一個巢里有 |只鴿子nm推論推論n(m1) + 1只鴿子進n個巢，至少有一個巢內至少有m只

48、鴿子推論推論若m1 , m2 , , mn是正整數，且 r1,則 m1, , mn至少有一個不小于rm1 + +mn n第一百二十頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二例例設A= a1a2a20是10個0和10個1 組成的進制數B=b1b2b20是任意的進制數C = b1b2b20 b1b2b20 = C1C2C40，則存在某個i ，1 i 20，使得CiCi+1Ci+19與a1a2a20至少有10位對應相等. . . . .ABC第 i 格第 i +19格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20第一百二十一頁，共150頁幻燈片.8鴿巢原理之二鴿巢原

49、理之二證證在C = C1C2C40中，當 i 遍歷1 , 2 , ,20時，每一個bj歷遍 a1 , a2 , , a20因A中有10個0和10個1，每一個bj都有10位次對應相等從而當 i歷遍1 , , 20時，共有10 20=200位次對應相等故對每個 i平均有200 20 = 10位相等，因而對某個 i 至少有10位對應相等第一百二十二頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二定理定理若序列S = a1 , a2 , , amn+1中的各數是不等的m , n 是正整數，則 S有一長度為m+1的嚴格增子序列或長度為n+1的減子序列，而且 S有一長度為m+1的減子序列或長度為n+1的增

50、子序列證證由S中的每個 ai 向后選取最長增子序列，設其長度為li ，從而得序列L = l1 , l2 , , lmn+1 若存在 lkm+1則結論成立第一百二十三頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二否則所有的 li 1 , m，其中必有 | = n+1個相等設li1 = li2 = = lin= lin+1 不妨設 i1i2 ai2 ain+1 ，即有一長度為n+1的減子列否則不妨設ai1 li2 ，矛盾mn+1 m第一百二十四頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二證證從ai 向后取最長增子列及減子列，設其長度分別為 li ，li .若任意 i ，都有li 1，m, l

51、i，n,不超過mn種對則存在 j k，( lj , lj ) = ( lk , lk )若aj lk，若aj ak，則 lj lk ，矛盾第一百二十五頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二例例將 1 , 65 劃分為個子集，必有一個子集中有一數是同子集中的兩數之差證用反證法設次命題不真即存在劃分P1 P2 P3P4 1，65 ，Pi中不存在一個數是Pi中兩數之差，i=1,2,3,4因 = 17，故有一子集，其中至少有17個數，設這17個數從小到大為a1 , , a17 不妨設 A=a1 , , a17 P1。令bi1= aia1，i = 2，17。65 4第一百二十六頁，共150頁幻

52、燈片.8鴿巢原理之二鴿巢原理之二設Bb1 , , b16，B 1 , 65 。由反證法假設BP1 = 。因而 B ( P2 P3 P4 )。 因為 6，不妨設b1 , , b6 P2 ， 令Ci1=bib1，I = 2， ，6設C C1 , , C5 ，C 1 , 65 由反證法假設C( P1P2 ) =，故有 C (P3P4 )因為 3，不妨設C1 , C2 , C3 P316 352第一百二十七頁，共150頁幻燈片.8鴿巢原理之二鴿巢原理之二令di1= CiC1，I = 2 , 3設D d1 , d2 , D 1 , 65。由反證法假設 D( P1P2P3 )=，因而 D P4。由反證法假

53、設 d2d1 P1P2P3 且d2d1 P4 ，故 d2d1 1 , 65 ，但顯然 d2d1 1 , 65 ，矛盾。第一百二十八頁，共150頁幻燈片.9Ramsey 問題問題RamseyRamsey問題問題 Ramsey問題可以看成是鴿巢原理的推廣下面舉例說明Ramsey問題例例6 個人中至少存在人相互認識或者相互不認識證證這個問題與K6的邊著色存在同色三角形等價假定用紅藍著色第一百二十九頁，共150頁幻燈片.9Ramsey 問題問題設K6的頂點集為v1 , v2 , , v6 ，dr(v)表示與頂點 v 關聯的紅色邊的條數，db(v)表示與 v 關聯的藍色邊的條數在K6 中，有dr(v)

54、db(v)，由鴿巢原理可知，至少有條邊同色現將證明過程用判斷樹表示如下：第一百三十頁，共150頁幻燈片.9Ramsey 問題問題dr(v1)3?db(v1)3設(v1v2) (v1v3) (v1v4)為紅邊設(v1v2) (v1v3) (v1v4)為藍邊v2v3v4是紅 ?v2v3v4是藍 ?設( v2v3 )是藍邊設( v2v3 )是紅邊v1v2v3是藍v1v2v3是紅YNNNYY第一百三十一頁，共150頁幻燈片.9Ramsey 問題問題若干推論若干推論( ( a )a )K6的邊用紅藍任意著色，則至少有兩個同色的三角形證證由前定理知，有同色三角形，不妨設v1v2v3是紅色三角形可由如下判斷

55、樹證明第一百三十二頁，共150頁幻燈片.9Ramsey 問題問題v1v4v5是藍設 (v4v5)為藍邊v4v5v6是紅?設(v1v4) (v1v5) (v1v6)為藍邊db(v1)3dr(v1)3?設 (v1v4)為紅邊(v4v2) (v4v3) 為藍邊?設 (v4v2)為紅邊db(v4)3?v1v2v4是紅dr(v4)3設 (v4v5)為藍邊(v4v5) (v4v6) 為紅邊v2v3v5是紅?設 (v2v5)為藍邊v2v4v5是藍v4v5v6是紅v1v5v6是藍?設 (v5v6)為紅邊yyyyyynnnnn第一百三十三頁，共150頁幻燈片.9Ramsey 問題問題( ( b )b )K9 的

56、邊紅藍兩色任意著色，則必有紅K4或藍色三角形(藍K4或紅色三角形)證證設個頂點為 v1 , v2 , , v9對個頂點的完全圖的邊的紅、藍著色圖中，必然存在 vi ，使得 dr(vi)3 否則，紅邊數 dr(vi) ，這是不可能的不妨設 dr(v1)3，可得如下判斷樹證明結論1227 2第一百三十四頁，共150頁幻燈片.9Ramsey 問題問題dr(v1)4?db(v1)6設(v1v2) (v1v3) (v1v4)(v1v5)是4紅邊設(v1v2) (v1v7)是6條藍邊K4(v2v3v4v5)是藍K4 ?K6(v2v7)中有紅 ?設(v2v3)是紅邊v1v2v3是紅設v2v3v4是紅K4(v

57、2v3v4v5)是藍K4YYYNNN第一百三十五頁，共150頁幻燈片.9Ramsey 問題問題K9的邊紅、藍著色，必有紅色三角形或藍色K4同理可證 K9的紅、藍著色，必有藍色三角形或紅色K4 (紅 藍K4) (藍 紅K4)存在同色K4或紅及藍 同色K4 (紅 藍 )第一百三十六頁，共150頁幻燈片.9Ramsey 問題問題( ( c )c )K18的邊紅，藍著色，存在紅K4或藍K4 證證設18個頂點為v1 , v2 , , v18 從v1引出的17條邊至少有條是同色的，不妨先假定為紅色從而可得下面的判斷樹證明命題第一百三十七頁，共150頁幻燈片.9Ramsey 問題問題dr(v1)9db(v1)9設(v1v2) (v1v10)是紅邊K9(v2 v