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

關(guān)于組合數(shù)學(xué)第三章容斥原理和鴿巢原理第1頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

3的倍數(shù)是：3，6，9，12，15，18。6個但答案不是10+6=16個，因?yàn)?，12，18在兩類中重復(fù)計數(shù)，應(yīng)減去。故答案是：16-3=13§3.2容斥原理第2頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

容斥原理研究有限集合的交或并的計數(shù)。[DeMorgan定理]論域U，補(bǔ)集,有§3.2容斥原理(a)(b)第3頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五證：(a)的證明。設(shè),則相當(dāng)于和同時成立，亦即(1)§3.2容斥原理第4頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五反之，若故(2)由（1）和（2）得(b)的證明和（a)類似，從略.§3.2容斥原理第5頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五DeMogan定理的推廣：設(shè)

證明：只證(a).N=2時定理已證。設(shè)定理對n是正確的，即假定：§3.2容斥原理第6頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五正確即定理對n+1也是正確的?！?.2容斥原理第7頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§2容斥原理最簡單的計數(shù)問題是求有限集合A和B的并的元素數(shù)目。顯然有即具有性質(zhì)A或B的元素的個數(shù)等于具(1)定理：§3.2容斥原理第8頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五有性質(zhì)A和B的元素個數(shù)。UBA§3.2容斥原理第9頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理證若A∩B=φ，則|A∪B|=|A|+|B||A|＝|A∩(B∪B)|＝|(A∩B)∪(A∩B)|＝|A∩B|+|A∩B|(1)同理|B|＝|B∩A|+|B∩A|(2)|A∪B|＝|(A∩(B∪B))∪(B∩(A∪A))|＝|(A∩B)∪(A∩B)∪(B∩A)∪(B∩A)|＝|A∩B|+|A∩B|+|B∩A|(3)第10頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理(3)－(1)－(2)得|A∪B|－|A|－|B|＝|A∩B|+|A∩B|+|B∩A|－(|A∩B|+|A∩B|)－(|B∩A|+|B∩A|)＝－|A∩B|∴|A∪B|＝|A|+|B|－|A∩B|第11頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五定理：(2)§3.2容斥原理第12頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理第13頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五ABC§3.2容斥原理第14頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

例

一個學(xué)校只有三門課程：數(shù)學(xué)、物理、化學(xué)。已知修這三門課的學(xué)生分別有170、130、120人；同時修數(shù)學(xué)、物理兩門課的學(xué)生45人；同時修數(shù)學(xué)、化學(xué)的20人；同時修物理化學(xué)的22人。同時修三門的3人。問這學(xué)校共有多少學(xué)生？§3.2容斥原理第15頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五令：M為修數(shù)學(xué)的學(xué)生集合；

P為修物理的學(xué)生集合；

C為修化學(xué)的學(xué)生集合；§3.2容斥原理第16頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五即學(xué)校學(xué)生數(shù)為336人?！?.2容斥原理第17頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五同理可推出：利用數(shù)學(xué)歸納法可得一般的定理：§3.2容斥原理第18頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

定理設(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,k)i∈I第19頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理

I∈￠(n-1,k)

I∈￠(n-1,k)i∈I第20頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理

I∈￠(n,k)

I∈￠(n-1,k-1)

I∈￠(n-1,k)此定理也可表示為：第21頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五定理：設(shè)是有限集合，則(4)§3.2容斥原理第22頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五證：用數(shù)學(xué)歸納法證明。已知n=2時有設(shè)n-1時成立，即有：§3.2容斥原理§3.2容斥原理第23頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理第24頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理第25頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理第26頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理第27頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理第28頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.2容斥原理第29頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五其中N是集合U的元素個數(shù)，即不屬于A的元素個數(shù)等于集合的全體減去屬于A的元素的個數(shù)。一般有：§3.2容斥原理第30頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五(5)容斥原理指的就是（4）和（5）式。§3.2容斥原理第31頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§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例第32頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五根據(jù)容斥原理，不出現(xiàn)ace和df的排列數(shù)為：=6!-(5!+4!)+3!=582§3.3例第33頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五例2求從1到500的整數(shù)中能被3或5除盡的數(shù)的個數(shù)。

解：令A(yù)為從1到500的整數(shù)中被3除盡的數(shù)的集合，B為被5除盡的數(shù)的集合§3.3例第34頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五被3或5除盡的數(shù)的個數(shù)為例3求由a,b,c,d四個字母構(gòu)成的位符號串中，a,b,c,d至少出現(xiàn)一次的符號串?dāng)?shù)目?！?.3例第35頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

解：令A(yù)、B、C分別為n位符號串中不出現(xiàn)a，b，c符號的集合。由于n位符號串中每一位都可取a，b，c，d四種符號中的一個，故不允許出現(xiàn)a的n位符號串的個數(shù)應(yīng)是§3.3例第36頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

a，b，c至少出現(xiàn)一次的n位符號串集合即為§3.3例第37頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

例4。求不超過120的素數(shù)個數(shù)。因，故不超過120的合數(shù)必然是2、3、5、7的倍數(shù)，而且不超過120的合數(shù)的因子不可能都超過11。設(shè)為不超過120的數(shù)的倍數(shù)集，=2，3，5，7。§3.3例第38頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第39頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第40頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第41頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第42頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五注意：27并非就是不超過120的素數(shù)個數(shù)，因?yàn)檫@里排除了2，3，5，7著四個數(shù)，又包含了1這個非素數(shù)。2，3，5，7本身是素數(shù)。故所求的不超過120的素數(shù)個數(shù)為：27+4-1=30§3.3例第43頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五例5。用26個英文字母作不允許重復(fù)的全排列，要求排除dog，god，gum，depth，thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。

解：所有排列中，令：§3.3例第44頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第45頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

出現(xiàn)dog字樣的排列，相當(dāng)于把dog作為一個單元參加排列，故類似有：

由于god,dog不可能在一個排列中同時出現(xiàn)，故：

類似：§3.3例第46頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

由于gum,dog可以在dogum字樣中同時出現(xiàn)，故有：類似有g(shù)od和depth可以在godepth字樣中同時出現(xiàn)，故

god和thing可以在thingod字樣中同時出現(xiàn)，從而

§3.3例第47頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第48頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五由于god、depth、thing不可以同時出現(xiàn)，故有：其余多于3個集合的交集都為空集?！?.3例第49頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五故滿足要求的排列數(shù)為：

§3.3例第50頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五

例6。求完全由n個布爾變量確定的布而函數(shù)的個數(shù)。

解：設(shè)布爾函數(shù)類為：

由于n個布爾變量的不同的真值表數(shù)目與位2進(jìn)制數(shù)數(shù)目相同，故為個。根據(jù)容斥原理，滿足條件的函數(shù)數(shù)目為：§3.3例第51頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第52頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例這10個布爾函數(shù)為：x1∧x2，x1∧x2，x1∧x2，x1∧x2，x1∨x2，x1∨x2，x1∨x2，x1∨x2，(x1∨x2)∧(x1∨x2)，(x1∨x2)∧(x1∨x2)第53頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五例7。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個數(shù)。解：若n分解為素數(shù)的乘積

設(shè)1到n的n個數(shù)中為倍數(shù)的集合為則有§3.3例第54頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第55頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.3例第56頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五即比60小且與60無公因子的數(shù)有16個：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一個1?！?.3例第57頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§4錯排問題

n個元素依次給以標(biāo)號1，2，…，n。N個元素的全排列中，求每個元素都不在自己原來位置上的排列數(shù)。設(shè)為數(shù)在第位上的全體排列，=1，2，…，n。因數(shù)字不能動，因而有：§3.3例第58頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.4錯排問題第59頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五每個元素都不在原來位置的排列數(shù)為§3.4錯排問題第60頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五例1。數(shù)1，2，…，9的全排列中，求偶數(shù)在原來位置上，其余都不在原來位置的錯排數(shù)目。

解：實(shí)際上是1，3，5，7，9五個數(shù)的錯排問題，總數(shù)為：§3.4錯排問題第61頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五例2.在8個字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四個字母不在原來上的錯排數(shù)目。8個字母的全排列中，令分別表A,C,E,G在原來位置上的排列，則錯排數(shù)為：§3.4錯排問題第62頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.4錯排問題第63頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五例3。求8個字母A,B,C,D,E,F,G,H的全排列中只有4個不在原來位置的排列數(shù)。解：8個字母中只有4個不在原來位置上，其余4個字母保持不動，相當(dāng)于4個元素的錯排，其數(shù)目為§3.4錯排問題第64頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五故8個字母的全排列中有4個不在原來位置上的排列數(shù)應(yīng)為：C(8,4)·9=630§3.4錯排問題第65頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§5棋盤多項(xiàng)式和有限制排列1.有限制排列§3.5棋盤多項(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；6!1!·3!·2!4!2!7!第66頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列設(shè)出現(xiàn)zz的排列的集合記為A3，|A3|==280；|A1∩A2|==12；|A1∩A3|==20；|A2∩A3|==30；|A1∩A2∩A3|=3!=6；

全排列的個數(shù)為：=1260；所以：

|A1∩A2∩A3|=1260－(60+105+280)+(12+20+30)－6=871

4!·3!8!4!2!5!3!6!4!9!2!·3!·4!第67頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列2．棋子多項(xiàng)式

n個不同元素的一個全排列可看做n個相同的棋子在n×n的棋盤上的一個布局。布局滿足同一行（列）中有且僅有一個棋子xxxxx如圖所示的布局對應(yīng)于排列41352。第68頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列可以把棋盤的形狀推廣到任意形狀：布子規(guī)定稱為無對攻規(guī)則，棋子相當(dāng)于象棋中的車。令r

k（C）表示k個棋子布到棋盤C上的方案數(shù)。如：第69頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。為了形象化起見，（）中的圖象便是棋盤的形狀。第70頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列定義設(shè)C為一棋盤，稱R(C)=∑rk(C)xk為C的棋盤多項(xiàng)式。規(guī)定r0(C)=1，包括C=Ф時。設(shè)Ci是棋盤C的某一指定格子所在的行與列都去掉后所得的棋盤；Ce是僅去掉該格子后的棋盤。在上面定義下，顯然有

rk(C)=rk－1(Ci)＋rk(Ce)，k=0∞第71頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列即對任一指定的格子，要么布子，所得的方案數(shù)為rk－1(Ci)；

要么不布子，方案數(shù)為rk(Ce)。設(shè)C有n個格子，則r1(C)＝n．r1(C)＝r0(Ci)+r1(Ce)，∵r1(Ce)＝n－1∴r0(Ci)＝1．故規(guī)定r0(C)＝1是合理的．第72頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列即對任一指定的格子，要么布子，所得的方案數(shù)為rk－1(Ci)；

要么不布子，方案數(shù)為rk(Ce)。從而

R(C)=∑rk(C)xk

＝１＋∑[rk－1(Ci)+

rk(Ce)]xk=x∑rk(Ci)xk+∑rk(Ce)xk

＝xR(Ci)+R(C

e)(3)∞k=0∞∞∞k=0k=0k=0第73頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列例如：R()=1+x；R()=xR()+R()=x+(1+x)=1+2x；R()=xR()+R()=x(1+x)+1+x=1+2x+x2第74頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒有C2的格子。則有：

rk(C)=∑ri(C1)rk－i(C2)i=0k故R(C)=∑(∑ri(C1)rk－i(C2))xk

=(∑ri(C1)xi)(∑rj(C2)xj)j=0nnkni=0i=0k=0∴R(C)=R(C1)R(C2)(4)第75頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列利用（３）和（４），可以把一個比較復(fù)雜的棋盤逐步分解成相對比較簡單的棋盤，從而得到其棋盤多項(xiàng)式。例R()=xR()+R()=x(1+x)2+(1+2x)2=1+5x+6x2+x3*R()=xR()+R()=1+6x+10x2+4x3第76頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列３．有禁區(qū)的排列例設(shè)對于排列P=P1P2P3P4，規(guī)定P1≠３，P２≠１、４，P３≠2、４，P4≠2。1234P1P2P3P41243143223431214這樣的排列對應(yīng)于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。第77頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列定理設(shè)ri為I個棋子布入禁區(qū)的方案數(shù)，i=1,2,3,···,n。有禁區(qū)的布子方案數(shù)（即禁區(qū)內(nèi)不布子的方案數(shù)）為

r0n!－r1(n－1)!＋r2(n－2)!－···＋(－1)nrn＝∑(－1)krk

(n－k)!

k=0n證設(shè)Ai

為第i個棋子布入禁區(qū)，其他棋子任意布的方案集，i=1,2,3,…,n。第78頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列則所有棋子都不布入禁區(qū)的方案數(shù)為｜A1∩A2∩···∩An｜＝n?。?－1)k∑｜∩Ai｜I∈￠(n,k)ni∈Ik=0而∑｜∩Ai｜正是k個棋子布入禁區(qū)，其他n-k個棋子任意布的方案數(shù)。由假設(shè)可知等于rk(n－k)！(注意：布入禁區(qū)的棋子也要遵守?zé)o對攻規(guī)則）.所以｜A1∩A2∩···∩An｜=n!+∑(－1)krk

(n－k)!I∈￠(n,k)i∈Ik=0

n第79頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列上例方案數(shù)為4!－6(4－1)!＋11(4－2)!－7(4－3)!＋1(4－４)!＝4例１，２，３，４四位工人，A，B，C，D四項(xiàng)任務(wù)。條件如下：１不干B；２不干B、C；３不干C、D；４不干D。問有多少種可行方案？第80頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列解由題意，可得如下棋盤：其中有影線的格子表示禁區(qū)。ABCD1234

R()=1+6x+10x2+4x3

方案數(shù)=4!－6(4－1)!+10(4－2)!－4(4－3)!+0(4－4)!=4第81頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.5棋盤多項(xiàng)式和有限制排列例三論錯排問題錯排問題對應(yīng)的是n×n的棋盤的主對角線上的格子是禁區(qū)的布子問題。C=···R(C)=(1+x)n=∑()xk令rk=()

nk=0

n

k

n

k故R(C)中的xn:n!+∑(－1)k()(n－k)!=n!∑(－1)k－=Pnk=1

n

nk=0

k!1

k

n第82頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式

§3.6一般公式若將§３.2中的例子改為“單修一門數(shù)學(xué)的學(xué)生有多少？”“只修一門課的學(xué)生有多少”“只修兩門課的學(xué)生有多少？”則相應(yīng)的答案表示如下：｜M∩P∩C｜；｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜｜M∩P∩C｜+｜M∩P∩C｜+｜M∩P∩C｜第83頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§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=|A1∩A2|+|A1∩A3|+···+|An-1∩An|Pk=∑|∩Aij|qk=∑|(∩Ai)∩(∩Aj)|

I∈￠(n,k)i∈I

I∈￠(n,k)i∈Ij∈I第84頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式定理qk=∑(－1)i()Pk+i

k+iii=0n-k證１設(shè)某一元素恰有k種性質(zhì)，則其對Pk的某一項(xiàng)的貢獻(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

kk+jk+i第85頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式而∑(－1)i(

)()=∑(－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第86頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式前例中只修一門課的學(xué)生為：|M∩P∩C|+|M∩P∩C|+|M∩P∩C|=q1=∑(－1)j-1()Pj=P1－2P2+3P3j1j=13在一般公式中，若令

P0=N，q0=|A1∩A2∩···∩An|，就得到原來的容斥原理。第87頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式證２根據(jù)定義

qk=∑|(∩Ai)∩(∩Aj)|qk由Pk+j的代數(shù)和組成，符號(－1)j，計算Pk+j的重復(fù)度：k+j個集的交的絕對值的項(xiàng)的總個數(shù)為()(),共()種。每一項(xiàng)的重復(fù)度為

()()()=()從而Pk+j的重復(fù)度也是()

I∈￠(n,k)i∈Ij∈Inkk+jk+jk+jk+jjn－kn－knnnkjkk第88頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式∴qk=∑(－1)j()Pk+j=∑(－1)j－k()Pjk+jkkjj=0n－kkn證３對N做歸納。

N=1時，設(shè)此元有m種性質(zhì)，m＜n,不妨設(shè)A1=A2=···=Am={a1}。顯然Pj=()，若j＞m，則Pj=0；由定義，得qk=｛jm1k=m0k≠m第89頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式右端＝∑(－1)i()Pk+i

＝∑(－1)i()()＝∑(－1)i()()={k+iii=0n－kk+ik

mk+ii=0n－k

mk

m-kii=0n－k1k=m0k≠m假設(shè)對于N－1，等式成立。對于N，設(shè)新增元有m種性質(zhì)，對于N個元的P’j＝Pj＋()，q’k＝｛jm1k=m0k≠m第90頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式右端＝∑(－1)i()P’k+i＝∑(－1)i()[Pk+i+()]＝∑(－1)i()Pk+i+∑(－1)i()()＝qk+｛等式成立．k+i

ki=0n－kk+i

kk+i

mk+i

ki=0n－kk+i

ki=0n－kk+i

mn－k

i=01k=m0k≠m第91頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式例某校有１２個教師，已知教數(shù)學(xué)的有８位，教物理的有６位，教化學(xué)的５位；數(shù)、理５位，數(shù)、化４位，理、化３位；數(shù)理化３位。問教其他課的有幾位？只教一門的有幾位？只好教兩門的有幾位？解令教數(shù)學(xué)的教師屬于A1，教物理的屬于A2，教化學(xué)的屬于A3。則P0＝１２，P1＝|A1|+|A2|+|A3|＝8+6+5＝１９;P2＝|A1∩A2|+

|A1∩A3|+|A2∩A3|＝12；P3＝|A1∩A2∩A3|＝3；第92頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式故教其他課的老師數(shù)為：

q0＝P0－P1+P2－P3＝２恰好一門的教師數(shù)：

q1＝P1－2P2+3P3＝4恰好教兩門的老師數(shù)為：

q2＝P2－3P3＝3第93頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式例

n對夫妻圍坐問題設(shè)n對夫妻圍圈而坐，男女相間，每個男人都不和他的妻子相鄰，有多少種可能的方案？解不妨設(shè)n個女人先圍成一圈，方案數(shù)為(n－1)!。對任一這樣的給定方案，順時針給每個女人以編號1,2,···,n。設(shè)第i號與第

i+1號女人之間的位置為第

i號位置，1≤i≤n－1。第n號女人與第1號之第94頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式間的位置為第n號位置。設(shè)第

i號女人的丈夫的編號也為第

i號，1≤i≤n。讓n個男人坐到上述編號的

n個位置上。設(shè)

ai是坐在第

i號位置上的男人，則

ai≠i，i+1，１≤i≤n－1；an≠n，1。這樣的限制也即要求在下面3行n列的排列中１２３······n－１n２３４······n1a1a2a3

······an－1an第95頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式每列中都無相同元素。滿足這樣的限制的排列a1a2···an稱為二重錯排。設(shè)二重錯排的個數(shù)為Un，原問題所求的方案數(shù)就是Un(n－1)！。設(shè)Ai為ai=I或

I+1(1≤I≤n－1)，an=n

或1的排列a1a2···an的集合。則｜Ai｜=2(n－1)!，關(guān)鍵是計算∑|∩Ai|

I∈￠(n,k)i∈I第96頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式也就是從(1,2)(2,3)···(n－１,n)(n,1)這n對數(shù)的k對中各取一數(shù)，且互不相同的取法的計數(shù)。這相當(dāng)于從1,2,2,3,3,4,···,n－1,n－1,n,n,1中取

k個互不相鄰數(shù)的組合的計數(shù)，但首尾的１不能同時取?；叵霟o重復(fù)不相鄰組合的計數(shù)：

C’(n,r)=C(n－r+1,r),這里所求的是()－()=()

2n－k+1k2n－4－(k－2)+1k－22n－kk2n2n－k第97頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§3.6一般公式∴Un=∑(－1)k()(n－k)!=｜∩Ai｜2n2n－k2n－kki∈[1,n]第98頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演基本想法：{an}易算，{bn}難算，{an}可用｛bn｝表示，利用反演，將{bn}用{an}表示．１．二項(xiàng)式反演引理第99頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演證

第100頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演定理證第101頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演推論證在定理中bk處用(－1)kbk代入，即可．例n!=∑()Dn－k，Dn=bn，令n－k=l，則n!=∑()DlDn=∑(－1)n-k()k!=n!∑(－1)n-k

=n∑nknknk1(n－k)!k=0k=0k=0nnn(－1)kk!第102頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演２．Mǒbíus反演定義設(shè)n∈Z+

1，若n=1;μ(n)=0，若n=p1α1p2α2···pkαk存在αi>1(－1)k，若n=p1p2···pk

如μ(30)=μ(2·3·5)=(－1)3

μ(12)=0；第103頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演定理設(shè)n∈Z+

則∑μ(d)=1，若n=1；0，若n>1；d|n證若n=1，∑μ(d)=μ(1)=1,成立．若

n>1，設(shè)n=p1α1p2α2···pkαk，n’=p1p2···pk

∑μ(d)=∑μ(d)=∑∑μ(∏pi)+μ(1)=1+∑()(－1)j=(1－1)k=0d|nd|nd|n’j=1ki∈II∈￠(k,j)kjj=1k第104頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演推論

(n)=n∑μ(d)dd|n證

n∑=n∑=n·{1+∑(－1)j∑(∏pi)－1}=n∏(1－)=

(n)μ(d)dd|nμ(d)dd|n’1pij=1i=1kkI∈￠(k,j)i∈I第105頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演定理(Mǒbíus反演定理)設(shè)f(n)和g(n)是定義在正整數(shù)集合上的兩個函數(shù)．

f(n)=∑g(d)=∑g()(M1)g(n)=∑μ(d)f()=∑μ()f(d)(M2)ndndd|nd|nd|nd|n則(M1)(M2)nd第106頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.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第107頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演“”：設(shè)（M2）成立?！苂(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<n第108頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演例圓排列問題設(shè)a1a2···an

是一個圓排列，即a2a3···ana1,···,ana1···an－1，看作是相同的。為了加以區(qū)別，必要時把原先的排列稱為線排列。一個圓排列在n個位置短開形成的

n個線排列在元素可重復(fù)的情況下，未必都不相同。例如，d｜n時，由不重復(fù)的a1a2···ad重復(fù)n／d次構(gòu)成的圓排列

第109頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演(a1a2···ad)···(a1a2···ad)

nd組只能形成d個不同的線排列。若一個圓排列可由一個長度為k的線排列重復(fù)若干次形成，則這樣的k中最小者成為該圓排列的周期。一個圓排列中元素的個數(shù)（重復(fù)出現(xiàn)的按其重復(fù)次數(shù)計）稱為它的長度第110頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演設(shè)集合｛1,2,···,m｝中元素形成的長度與周期都是d的圓排列的個數(shù)為M(d)。設(shè)n是一給定的正整數(shù)。若

d｜n，每個長度與周期都是d的圓排列可在d個位置上斷開，重復(fù)

n/d次形成d個長度為

n的可重排列。因此有∑dM(d)=mn

由Mǒbíus反演定理nM(n)=∑μ(d)m故M(n)=∑μ(d)md｜nd｜nd｜nndnd第111頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.11反演設(shè)長度為n的圓排列的個數(shù)為T(n)，則

T(n)＝∑M(d)d｜n例

m={1,2}，n=7則

M(7)=(27－2)=18T(7)=∑M(d)=M(1)+M(7)=20d｜717第112頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.7鴿巢原理之一鴿巢原理是組合數(shù)學(xué)中最簡單也是最基本的原理，也叫抽屜原理。即“若有n個鴿子巢，n+1個鴿子，則至少有一個巢內(nèi)有至少有兩個鴿子。”例１367人中至少有２人的生日相同。例２10雙手套中任取11只，其中至少有兩只是完整配對的。例３參加一會議的人中至少有２人認(rèn)識的別的參加者的人數(shù)相等。第113頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.7鴿巢原理之一例４從1到2n的正整數(shù)中任取n+1個，則這n+1個數(shù)中，至少有一對數(shù)，其中一個是另一個的倍數(shù)。證設(shè)n+1個數(shù)是a1,a2,···,an+1。每個數(shù)去掉一切2的因子，直至剩下一個奇數(shù)為止。組成序列r1,r2,,···,rn+1。這n+1個數(shù)仍在［1,2n]中，且都是奇數(shù)。而[1,2n]中只有n個奇數(shù).故必有

ri=rj=r,則ai=2αir,aj=2αjr若αi＞αj，則ai是aj的倍數(shù)。第114頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.7鴿巢原理之一例５設(shè)a1,a2,···,am是正整數(shù)序列，則至少存在k和l,1≤k≤l≤m，使得和

ak+ak+1+···+al

是m的倍數(shù)。證設(shè)Sk=∑ai,Sh≡rhmodm0≤rh≤m-1h=1,2,···,m.若存在l,Sl≡0modm則命題成立．否則，1≤rh≤m-1．但h=1,2,···,m．由鴿巢原理，故存在rk=rh,即Sk≡Sh，不妨設(shè)h＞k．則

Sh－Sk=ak+1+ak+2+…+ah≡0modmi=1h第115頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.7鴿巢原理之一例６設(shè)a1,a2,a3為任意３個整數(shù)，b1b2b3為a1,a2,a3的任一排列，則a1－b1,a2－b2,

a3－b3中至少有一個是偶數(shù)．證由鴿巢原理，a1,a2,a3必有兩個同奇偶．設(shè)這３個數(shù)被２除的余數(shù)為xxy，于是b1,b2,b3中被２除的余數(shù)有２個x，一個y．這樣a1－b1,a2－b2,a3－b3被２除的余數(shù)必有一個為０．第116頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.7鴿巢原理之一例７設(shè)a1,a2,···,a100是由1和２組成的序列,已知從其任一數(shù)開始的順序10個數(shù)的和不超過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顯然S1<S2<…<S100，且S100=(a1+…+a10)+(a11+…+a20)+…+(a91+…+a100)i=1j第117頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.7鴿巢原理之一根據(jù)假定有S100≤10×16=160作序列S1,S2,…,S100,S1+39,…,S100+39.共200項(xiàng)．其中最大項(xiàng)S100+39≤160+39由鴿巢原理，必有兩項(xiàng)相等．而且必是前段中某項(xiàng)與后段中某項(xiàng)相等．設(shè)

Sk=Sh+39，k>hSk－Sh=39即

ah+ah+1+…+ak=39第118頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二鴿巢原理二m1,m2,…,mn都是正整數(shù)，并有m1+m2+…+mn－n+1個鴿子住進(jìn)n個鴿巢，則至少對某個i有第i個巢中至少有mi個鴿子，i=1,2,…,n．上一小節(jié)的鴿巢原理一是這一原理的特殊情況，即m1=m2=…=mn=2，

m1+m2+…+mn－n+1=n+1如若不然，則對任一i，都有第

i個巢中的鴿子數(shù)≤mi－1則第119頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二鴿子總數(shù)≤m1+m2+…+mn－n

，與假設(shè)相矛盾．推論１

m只鴿子進(jìn)n個巢，至少有一個巢里有「－|只鴿子．nm推論２

n(m－1)+1只鴿子進(jìn)n個巢，至少有一個巢內(nèi)至少有m只鴿子．推論３若m1,m2,…,mn是正整數(shù)，且>

r－1,則m1,…,mn至少有一個不小于rm1+…+mnn第120頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二例設(shè)A=a1a2···a20是10個0和10個1組成的２進(jìn)制數(shù)．B=b1b2···b20是任意的２進(jìn)制數(shù)．C=b1b2···b20b1b2···b20=C1C2···C40，則存在某個i，1≤i≤20，使得CiCi+1···Ci+19與a1a2···a20至少有10位對應(yīng)相等．…...…...............ABC第i格第i+19格12·········192012·······192012········19201······1920第121頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二證在C=C1C2···C40中，當(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平均有20020=10位相等，因而對某個i至少有10位對應(yīng)相等．第122頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二定理若序列S={a1,a2,…,amn+1}中的各數(shù)是不等的．m,n是正整數(shù)，則S有一長度為m+1的嚴(yán)格增子序列或長度為n+1的減子序列，而且

S有一長度為m+1的減子序列或長度為n+1的增子序列．證１由S中的每個ai

向后選取最長增子序列，設(shè)其長度為li，從而得序列

L={l1,l2,…,lmn+1}．若存在lk≥m+1則結(jié)論成立．第123頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二否則所有的li∈[1,m]，其中必有「|=n+1個相等．設(shè)li1

=li2=···=lin=lin+1不妨設(shè)i1<i2<···<in+1應(yīng)有ai1>ai2>···>ain+1，即有一長度為n+1的減子列．否則不妨設(shè)ai1<ai2，則有l(wèi)i1>li2，矛盾．mn+1m第124頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二證２從ai

向后取最長增子列及減子列，設(shè)其長度分別為li，l’i.若任意i，都有l(wèi)i

∈[1，m],l’i∈［１，n］,不超過mn種對．則存在j<k，(lj,l’j)=(lk,l’k)若aj<ak，則lj>lk，若aj>ak，則l’j>l’k，矛盾．第125頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二例將[1,65]劃分為４個子集，必有一個子集中有一數(shù)是同子集中的兩數(shù)之差．證用反證法．設(shè)次命題不真．即存在劃分P1∪P2∪P3∪P4＝[1，65]，Pi中不存在一個數(shù)是Pi中兩數(shù)之差，i=1,2,3,4因

=17，故有一子集，其中至少有17個數(shù)，設(shè)這17個數(shù)從小到大為a1,…,a17

．不妨設(shè)A={a1,…,a17}P1。令bi－1=ai－a1，i=2，···，17。654第126頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二設(shè)B＝｛b1,···,b16}，B[1,65]。由反證法假設(shè)B∩P1=ф。因而

B(P2∪P3∪P4)。

因?yàn)椋?，不妨設(shè){b1,···,b6}P2，令Ci－1=bi－b1，I=2，···，6設(shè)C＝{C1,···,C5}，C[1,65]由反證法假設(shè)C∩(P1∪P2)=ф，故有

C(P3∪P4)因?yàn)椋?，不妨設(shè){C1,C2,C3}P316352第127頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.8鴿巢原理之二令di－1=Ci－C1，I=2,3設(shè)D＝{d1,d2},D[1,65]。由反證法假設(shè)D∩(P1∪P2∪P3)=ф，因而

DP4。由反證法假設(shè)

d2－d1∈P1∪P2∪P3

且d2－d1∈P4，故d2－d1∈[1,65]，但顯然

d2－d1∈[1,65]，矛盾。第128頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.9Ramsey問題１．Ramsey問題

Ramsey問題可以看成是鴿巢原理的推廣．下面舉例說明Ramsey問題．例6個人中至少存在３人相互認(rèn)識或者相互不認(rèn)識．證這個問題與K6的邊２著色存在同色三角形等價．假定用紅藍(lán)著色．第129頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.9Ramsey問題設(shè)K6的頂點(diǎn)集為{v1,v2,···,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)將證明過程用判斷樹表示如下：第130頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.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第131頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.9Ramsey問題２．若干推論(

a)K6的邊用紅藍(lán)任意著色，則至少有兩個同色的三角形．證由前定理知，有同色三角形，不妨設(shè)△v1v2v3是紅色三角形可由如下判斷樹證明．第132頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.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è)(v5v6)為紅邊√√√yyyyyynnnnn第133頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.9Ramsey問題(b)K9

的邊紅藍(lán)兩色任意著色，則必有紅K4或藍(lán)色三角形(藍(lán)K4或紅色三角形)．證設(shè)９個頂點(diǎn)為v1,v2,···,v9．對９個頂點(diǎn)的完全圖的邊的紅、藍(lán)２著色圖中，必然存在vi，使得dr(vi)≠3．否則，紅邊數(shù)＝∑dr(vi)＝，這是不可能的．不妨設(shè)

dr(v1)≠3，可得如下判斷樹證明結(jié)論．12272第134頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.9Ramsey問題dr(v1)≥4?db(v1)≥6設(shè)(v1v2)(v1v3)(v1v4)(v1v5)是4紅邊設(shè)(v1v2)···(v1v7)是6條藍(lán)邊K4(v2v3v4v5)是藍(lán)K4?K6(v2···v7)中有紅△?設(shè)(v2v3)是紅邊△v1v2v3是紅△設(shè)△v2v3v4是紅△K4(v2v3v4v5)是藍(lán)K4√√YYYNNN第135頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.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)△)第136頁，共150頁，2022年，5月20日，18點(diǎn)48分，星期五§３.9Ramsey問題(c)K18的邊紅，藍(lán)２著色，存在紅K4或藍(lán)K4

．證設(shè)18個頂點(diǎn)為v1,v2,···,v18．從v1引出的17條邊至少有９條是同色的，不妨先假定為紅色．從而可得下面的判斷