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

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

3的倍數(shù)是：3，6，9，12，15，18。6個(gè)但答案不是10+6=16個(gè)，因?yàn)?，12，18在兩類中重復(fù)計(jì)數(shù)，應(yīng)減去。故答案是：16-3=13§3.2容斥原理第2頁(yè),共150頁(yè)，2024年2月25日，星期天

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

證明：只證(a).N=2時(shí)定理已證。設(shè)定理對(duì)n是正確的，即假定：§3.2容斥原理第6頁(yè),共150頁(yè)，2024年2月25日，星期天正確即定理對(duì)n+1也是正確的?！?.2容斥原理第7頁(yè),共150頁(yè)，2024年2月25日，星期天§2容斥原理最簡(jiǎn)單的計(jì)數(shù)問(wèn)題是求有限集合A和B的并的元素?cái)?shù)目。顯然有即具有性質(zhì)A或B的元素的個(gè)數(shù)等于具(1)定理：§3.2容斥原理第8頁(yè),共150頁(yè)，2024年2月25日，星期天有性質(zhì)A和B的元素個(gè)數(shù)。UBA§3.2容斥原理第9頁(yè),共150頁(yè)，2024年2月25日，星期天§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頁(yè),共150頁(yè)，2024年2月25日，星期天§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頁(yè),共150頁(yè)，2024年2月25日，星期天定理：(2)§3.2容斥原理第12頁(yè),共150頁(yè)，2024年2月25日，星期天§3.2容斥原理第13頁(yè),共150頁(yè)，2024年2月25日，星期天ABC§3.2容斥原理第14頁(yè),共150頁(yè)，2024年2月25日，星期天

例

一個(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容斥原理第15頁(yè),共150頁(yè)，2024年2月25日，星期天令：M為修數(shù)學(xué)的學(xué)生集合；

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

C為修化學(xué)的學(xué)生集合；§3.2容斥原理第16頁(yè),共150頁(yè)，2024年2月25日，星期天即學(xué)校學(xué)生數(shù)為336人?！?.2容斥原理第17頁(yè),共150頁(yè)，2024年2月25日，星期天同理可推出：利用數(shù)學(xué)歸納法可得一般的定理：§3.2容斥原理第18頁(yè),共150頁(yè)，2024年2月25日，星期天

定理設(shè)￠(n,k)是［1,n］的所有k-子集的集合,則|∪Ai|=∑(－1)k-1∑|∩Ai|證

對(duì)n用歸納法。n=2時(shí)，等式成立。

假設(shè)對(duì)n-1，等式成立。對(duì)于n有

§3.2容斥原理ni=1k=1n

I∈￠(n,k)i∈I第19頁(yè),共150頁(yè)，2024年2月25日，星期天§3.2容斥原理

I∈￠(n-1,k)

I∈￠(n-1,k)i∈I第20頁(yè),共150頁(yè)，2024年2月25日，星期天§3.2容斥原理

I∈￠(n,k)

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

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

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

解：令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)是§3.3例第36頁(yè),共150頁(yè)，2024年2月25日，星期天

a，b，c至少出現(xiàn)一次的n位符號(hào)串集合即為§3.3例第37頁(yè),共150頁(yè)，2024年2月25日，星期天

例4。求不超過(guò)120的素?cái)?shù)個(gè)數(shù)。因，故不超過(guò)120的合數(shù)必然是2、3、5、7的倍數(shù)，而且不超過(guò)120的合數(shù)的因子不可能都超過(guò)11。設(shè)為不超過(guò)120的數(shù)的倍數(shù)集，=2，3，5，7?！?.3例第38頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第39頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第40頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第41頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第42頁(yè),共150頁(yè)，2024年2月25日，星期天注意：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=30§3.3例第43頁(yè),共150頁(yè)，2024年2月25日，星期天例5。用26個(gè)英文字母作不允許重復(fù)的全排列，要求排除dog，god，gum，depth，thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。

解：所有排列中，令：§3.3例第44頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第45頁(yè),共150頁(yè)，2024年2月25日，星期天

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

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

類似：§3.3例第46頁(yè),共150頁(yè)，2024年2月25日，星期天

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

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

§3.3例第47頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第48頁(yè),共150頁(yè)，2024年2月25日，星期天由于god、depth、thing不可以同時(shí)出現(xiàn)，故有：其余多于3個(gè)集合的交集都為空集。§3.3例第49頁(yè),共150頁(yè)，2024年2月25日，星期天故滿足要求的排列數(shù)為：

§3.3例第50頁(yè),共150頁(yè)，2024年2月25日，星期天

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

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

由于n個(gè)布爾變量的不同的真值表數(shù)目與位2進(jìn)制數(shù)數(shù)目相同，故為個(gè)。根據(jù)容斥原理，滿足條件的函數(shù)數(shù)目為：§3.3例第51頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第52頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例這10個(gè)布爾函數(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頁(yè),共150頁(yè)，2024年2月25日，星期天例7。歐拉函數(shù)(n)是求小于n且與n互素的數(shù)的個(gè)數(shù)。解：若n分解為素?cái)?shù)的乘積

設(shè)1到n的n個(gè)數(shù)中為倍數(shù)的集合為則有§3.3例第54頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第55頁(yè),共150頁(yè)，2024年2月25日，星期天§3.3例第56頁(yè),共150頁(yè)，2024年2月25日，星期天即比60小且與60無(wú)公因子的數(shù)有16個(gè)：7，11，13，17。19。23，29，31，37，41，43，47，49，53，59，此外尚有一個(gè)1?！?.3例第57頁(yè),共150頁(yè)，2024年2月25日，星期天§4錯(cuò)排問(wèn)題

n個(gè)元素依次給以標(biāo)號(hào)1，2，…，n。N個(gè)元素的全排列中，求每個(gè)元素都不在自己原來(lái)位置上的排列數(shù)。設(shè)為數(shù)在第位上的全體排列，=1，2，…，n。因數(shù)字不能動(dòng)，因而有：§3.3例第58頁(yè),共150頁(yè)，2024年2月25日，星期天§3.4錯(cuò)排問(wèn)題第59頁(yè),共150頁(yè)，2024年2月25日，星期天每個(gè)元素都不在原來(lái)位置的排列數(shù)為§3.4錯(cuò)排問(wèn)題第60頁(yè),共150頁(yè)，2024年2月25日，星期天例1。數(shù)1，2，…，9的全排列中，求偶數(shù)在原來(lái)位置上，其余都不在原來(lái)位置的錯(cuò)排數(shù)目。

解：實(shí)際上是1，3，5，7，9五個(gè)數(shù)的錯(cuò)排問(wèn)題，總數(shù)為：§3.4錯(cuò)排問(wèn)題第61頁(yè),共150頁(yè)，2024年2月25日，星期天例2.在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.4錯(cuò)排問(wèn)題第62頁(yè),共150頁(yè)，2024年2月25日，星期天§3.4錯(cuò)排問(wèn)題第63頁(yè),共150頁(yè)，2024年2月25日，星期天例3。求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.4錯(cuò)排問(wèn)題第64頁(yè),共150頁(yè)，2024年2月25日，星期天故8個(gè)字母的全排列中有4個(gè)不在原來(lái)位置上的排列數(shù)應(yīng)為：C(8,4)·9=630§3.4錯(cuò)排問(wèn)題第65頁(yè),共150頁(yè)，2024年2月25日，星期天§5棋盤(pán)多項(xiàng)式和有限制排列1.有限制排列§3.5棋盤(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!1!·3!·2!4!2!7!第66頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列設(shè)出現(xiàn)zz的排列的集合記為A3，|A3|==280；|A1∩A2|==12；|A1∩A3|==20；|A2∩A3|==30；|A1∩A2∩A3|=3!=6；

全排列的個(gè)數(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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列2．棋子多項(xiàng)式

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

k（C）表示k個(gè)棋子布到棋盤(pán)C上的方案數(shù)。如：第69頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列r1()=1，r1()=2，r1()=2，r2()=0，r2()=1。為了形象化起見(jiàn)，（）中的圖象便是棋盤(pán)的形狀。第70頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列定義設(shè)C為一棋盤(pán)，稱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)=rk－1(Ci)＋rk(Ce)，k=0∞第71頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列即對(duì)任一指定的格子，要么布子，所得的方案數(shù)為rk－1(Ci)；

要么不布子，方案數(shù)為rk(Ce)。設(shè)C有n個(gè)格子，則r1(C)＝n．r1(C)＝r0(Ci)+r1(Ce)，∵r1(Ce)＝n－1∴r0(Ci)＝1．故規(guī)定r0(C)＝1是合理的．第72頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列即對(duì)任一指定的格子，要么布子，所得的方案數(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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列如果C由相互分離的C1，C2組成，即C1的任一格子所在的行和列中都沒(méi)有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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列利用（３）和（４），可以把一個(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+10x2+4x3第76頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列３．有禁區(qū)的排列例設(shè)對(duì)于排列P=P1P2P3P4，規(guī)定P1≠３，P２≠１、４，P３≠2、４，P4≠2。1234P1P2P3P41243143223431214這樣的排列對(duì)應(yīng)于有禁區(qū)的布子。如右圖有影線的格子表示禁區(qū)。第77頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列定理設(shè)ri為I個(gè)棋子布入禁區(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個(gè)棋子布入禁區(qū)，其他棋子任意布的方案集，i=1,2,3,…,n。第78頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列則所有棋子都不布入禁區(qū)的方案數(shù)為｜A1∩A2∩···∩An｜＝n！＋∑(－1)k∑｜∩Ai｜I∈￠(n,k)ni∈Ik=0而∑｜∩Ai｜正是k個(gè)棋子布入禁區(qū)，其他n-k個(gè)棋子任意布的方案數(shù)。由假設(shè)可知等于rk(n－k)！(注意：布入禁區(qū)的棋子也要遵守?zé)o對(duì)攻規(guī)則）.所以｜A1∩A2∩···∩An｜=n!+∑(－1)krk

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

n第79頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(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。問(wèn)有多少種可行方案？第80頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列解由題意，可得如下棋盤(pán)：其中有影線的格子表示禁區(qū)。ABCD1234

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

方案數(shù)=4!－6(4－1)!+10(4－2)!－4(4－3)!+0(4－4)!=4第81頁(yè),共150頁(yè)，2024年2月25日，星期天§3.5棋盤(pán)多項(xiàng)式和有限制排列例三論錯(cuò)排問(wèn)題錯(cuò)排問(wèn)題對(duì)應(yīng)的是n×n的棋盤(pán)的主對(duì)角線上的格子是禁區(qū)的布子問(wèn)題。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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式

§3.6一般公式若將§３.2中的例子改為“單修一門(mén)數(shù)學(xué)的學(xué)生有多少？”“只修一門(mén)課的學(xué)生有多少”“只修兩門(mén)課的學(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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式設(shè)有與性質(zhì)１,2,···,n相關(guān)的元素N個(gè)，Ai為有第i種性質(zhì)的元素的集合.i=1,2,…,nPk為至少有k種性質(zhì)的元素的元次；qk為恰有k種性質(zhì)的元素的個(gè)數(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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式定理qk=∑(－1)i()Pk+i

k+iii=0n-k證１設(shè)某一元素恰有k種性質(zhì)，則其對(duì)Pk的某一項(xiàng)的貢獻(xiàn)為１，而對(duì)Pk+1，Pk+2,···,Pn的貢獻(xiàn)都是０。若某一元的性質(zhì)少于k種則其對(duì)Pk，Pk+1，···，Pn的貢獻(xiàn)都是０。若恰有k+j種性質(zhì)，則其對(duì)Pk的貢獻(xiàn)是(),對(duì)Pk+i的貢獻(xiàn)是（）k+j

kk+jk+i第85頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式而∑(－1)i(

)()=∑(－1)i()()=∑(－1)i()()=()∑(－1)i()=()·0=0即某恰有k+j種性質(zhì)的元素對(duì)上式右邊的總的貢獻(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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式前例中只修一門(mén)課的學(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|，就得到原來(lái)的容斥原理。第87頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式證２根據(jù)定義

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

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

I∈￠(n,k)i∈Ij∈Inkk+jk+jk+jk+jjn－kn－knnnkjkk第88頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式∴qk=∑(－1)j()Pk+j=∑(－1)j－k()Pjk+jkkjj=0n－kkn證３對(duì)N做歸納。

N=1時(shí)，設(shè)此元有m種性質(zhì)，m＜n,不妨設(shè)A1=A2=···=Am={a1}。顯然Pj=()，若j＞m，則Pj=0；由定義，得qk=｛jm1k=m0k≠m第89頁(yè),共150頁(yè)，2024年2月25日，星期天§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è)對(duì)于N－1，等式成立。對(duì)于N，設(shè)新增元有m種性質(zhì)，對(duì)于N個(gè)元的P’j＝Pj＋()，q’k＝｛jm1k=m0k≠m第90頁(yè),共150頁(yè)，2024年2月25日，星期天§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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式例某校有１２個(gè)教師，已知教數(shù)學(xué)的有８位，教物理的有６位，教化學(xué)的５位；數(shù)、理５位，數(shù)、化４位，理、化３位；數(shù)理化３位。問(wèn)教其他課的有幾位？只教一門(mén)的有幾位？只好教兩門(mén)的有幾位？解令教數(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頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式故教其他課的老師數(shù)為：

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

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

q2＝P2－3P3＝3第93頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式例

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

i+1號(hào)女人之間的位置為第

i號(hào)位置，1≤i≤n－1。第n號(hào)女人與第1號(hào)之第94頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式間的位置為第n號(hào)位置。設(shè)第

i號(hào)女人的丈夫的編號(hào)也為第

i號(hào)，1≤i≤n。讓n個(gè)男人坐到上述編號(hào)的

n個(gè)位置上。設(shè)

ai是坐在第

i號(hào)位置上的男人，則

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

······an－1an第95頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式每列中都無(wú)相同元素。滿足這樣的限制的排列a1a2···an稱為二重錯(cuò)排。設(shè)二重錯(cuò)排的個(gè)數(shù)為Un，原問(wèn)題所求的方案數(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)鍵是計(jì)算∑|∩Ai|

I∈￠(n,k)i∈I第96頁(yè),共150頁(yè)，2024年2月25日，星期天§3.6一般公式也就是從(1,2)(2,3)···(n－１,n)(n,1)這n對(duì)數(shù)的k對(duì)中各取一數(shù)，且互不相同的取法的計(jì)數(shù)。這相當(dāng)于從1,2,2,3,3,4,···,n－1,n－1,n,n,1中取

k個(gè)互不相鄰數(shù)的組合的計(jì)數(shù)，但首尾的１不能同時(shí)取。回想無(wú)重復(fù)不相鄰組合的計(jì)數(shù)：

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

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

第100頁(yè),共150頁(yè)，2024年2月25日，星期天§３.11反演定理證第101頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.11反演定理(Mǒbíus反演定理)設(shè)f(n)和g(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)．

f(n)=∑g(d)=∑g()(M1)g(n)=∑μ(d)f()=∑μ()f(d)(M2)ndndd|nd|nd|nd|n則(M1)(M2)nd第106頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.11反演例圓排列問(wèn)題設(shè)a1a2···an

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

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

第109頁(yè),共150頁(yè)，2024年2月25日，星期天§３.11反演(a1a2···ad)···(a1a2···ad)

nd組只能形成d個(gè)不同的線排列。若一個(gè)圓排列可由一個(gè)長(zhǎng)度為k的線排列重復(fù)若干次形成，則這樣的k中最小者成為該圓排列的周期。一個(gè)圓排列中元素的個(gè)數(shù)（重復(fù)出現(xiàn)的按其重復(fù)次數(shù)計(jì)）稱為它的長(zhǎng)度第110頁(yè),共150頁(yè)，2024年2月25日，星期天§３.11反演設(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的可重排列。因此有∑dM(d)=mn

由Mǒbíus反演定理nM(n)=∑μ(d)m故M(n)=∑μ(d)md｜nd｜nd｜nndnd第111頁(yè),共150頁(yè)，2024年2月25日，星期天§３.11反演設(shè)長(zhǎng)度為n的圓排列的個(gè)數(shù)為T(mén)(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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.7鴿巢原理之一鴿巢原理是組合數(shù)學(xué)中最簡(jiǎn)單也是最基本的原理，也叫抽屜原理。即“若有n個(gè)鴿子巢，n+1個(gè)鴿子，則至少有一個(gè)巢內(nèi)有至少有兩個(gè)鴿子?！崩?67人中至少有２人的生日相同。例２10雙手套中任取11只，其中至少有兩只是完整配對(duì)的。例３參加一會(huì)議的人中至少有２人認(rèn)識(shí)的別的參加者的人數(shù)相等。第113頁(yè),共150頁(yè)，2024年2月25日，星期天§３.7鴿巢原理之一例４從1到2n的正整數(shù)中任取n+1個(gè)，則這n+1個(gè)數(shù)中，至少有一對(duì)數(shù)，其中一個(gè)是另一個(gè)的倍數(shù)。證設(shè)n+1個(gè)數(shù)是a1,a2,···,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=2αir,aj=2αjr若αi＞αj，則ai是aj的倍數(shù)。第114頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.7鴿巢原理之一例６設(shè)a1,a2,a3為任意３個(gè)整數(shù)，b1b2b3為a1,a2,a3的任一排列，則a1－b1,a2－b2,

a3－b3中至少有一個(gè)是偶數(shù)．證由鴿巢原理，a1,a2,a3必有兩個(gè)同奇偶．設(shè)這３個(gè)數(shù)被２除的余數(shù)為xxy，于是b1,b2,b3中被２除的余數(shù)有２個(gè)x，一個(gè)y．這樣a1－b1,a2－b2,a3－b3被２除的余數(shù)必有一個(gè)為０．第116頁(yè),共150頁(yè)，2024年2月25日，星期天§３.7鴿巢原理之一例７設(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顯然S1<S2<…<S100，且S100=(a1+…+a10)+(a11+…+a20)+…+(a91+…+a100)i=1j第117頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.8鴿巢原理之二鴿巢原理二m1,m2,…,mn都是正整數(shù)，并有m1+m2+…+mn－n+1個(gè)鴿子住進(jìn)n個(gè)鴿巢，則至少對(duì)某個(gè)i有第i個(gè)巢中至少有mi個(gè)鴿子，i=1,2,…,n．上一小節(jié)的鴿巢原理一是這一原理的特殊情況，即m1=m2=…=mn=2，

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

i個(gè)巢中的鴿子數(shù)≤mi－1則第119頁(yè),共150頁(yè)，2024年2月25日，星期天§３.8鴿巢原理之二鴿子總數(shù)≤m1+m2+…+mn－n

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

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

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

r－1,則m1,…,mn至少有一個(gè)不小于rm1+…+mnn第120頁(yè),共150頁(yè)，2024年2月25日，星期天§３.8鴿巢原理之二例設(shè)A=a1a2···a20是10個(gè)0和10個(gè)1組成的２進(jìn)制數(shù)．B=b1b2···b20是任意的２進(jìn)制數(shù)．C=b1b2···b20b1b2···b20=C1C2···C40，則存在某個(gè)i，1≤i≤20，使得CiCi+1···Ci+19與a1a2···a20至少有10位對(duì)應(yīng)相等．…...…...............ABC第i格第i+19格12·········192012·······192012········19201······1920第121頁(yè),共150頁(yè)，2024年2月25日，星期天§３.8鴿巢原理之二證在C=C1C2···C40中，當(dāng)i遍歷1,2,…,20時(shí)，每一個(gè)bj歷遍a1,a2,…,a20．因A中有10個(gè)0和10個(gè)1，每一個(gè)bj都有10位次對(duì)應(yīng)相等．從而當(dāng)i歷遍1,…,20時(shí)，共有10·20=200位次對(duì)應(yīng)相等．故對(duì)每個(gè)i平均有20020=10位相等，因而對(duì)某個(gè)i至少有10位對(duì)應(yīng)相等．第122頁(yè),共150頁(yè)，2024年2月25日，星期天§３.8鴿巢原理之二定理若序列S={a1,a2,…,amn+1}中的各數(shù)是不等的．m,n是正整數(shù)，則S有一長(zhǎng)度為m+1的嚴(yán)格增子序列或長(zhǎng)度為n+1的減子序列，而且

S有一長(zhǎng)度為m+1的減子序列或長(zhǎng)度為n+1的增子序列．證１由S中的每個(gè)ai

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

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

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

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

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

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

．不妨設(shè)A={a1,…,a17}P1。令bi－1=ai－a1，i=2，···，17。654第126頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.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頁(yè),共150頁(yè)，2024年2月25日，星期天§３.9Ramsey問(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)著色．第129頁(yè),共150頁(yè)，2024年2月25日，星期天§３.9Ramsey問(wèn)題設(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)將證明過(guò)程用判斷樹(shù)表示如下：第130頁(yè),共150頁(yè)，2024年2月25日，星期天§３.9Ramsey問(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第131頁(yè),共150頁(yè)，2024年2月25日，星期天§３.9Ramsey問(wèn)題２．若干推論(

a)K6的邊用紅藍(lán)任意著色，則至少有兩個(gè)同色的三角形．證由前定理知，有同色三角形，不妨設(shè)△v1v2v3是紅色三角形可由如下判斷樹(shù)證明．第132頁(yè),共150頁(yè)，2024年2月25日，星期天§３.9Ramsey問(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)為紅邊√√√yyyyyynnnnn第133頁(yè),共150頁(yè)，2024年2月25日，星期天§３.9Ramsey問(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é)論．12272第134頁(yè),共150頁(yè)，2024年2月25日，星期天§３.9Ramsey問(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(v2···v7