容斥原理和鴿巢原理

容斥原理和鴿巢原理2023/7/231第1頁，課件共132頁，創(chuàng)作于2023年2月例對{1,2,…,n}的排列計數(shù)，其中。解直接計數(shù)：

(1)

：有個；

…

(n-1):有個；共有個間接計數(shù)：：有個所以共有個容斥原理2023/7/232第2頁，課件共132頁，創(chuàng)作于2023年2月例計算1到600中不能被6整除的整數(shù)個數(shù)。證能被6整除的整數(shù)個數(shù)為所求數(shù)的個數(shù)為

一般，若，則或容斥原理2023/7/233第3頁，課件共132頁，創(chuàng)作于2023年2月作為上述法則的第一個推廣：令S是一個有限集合，P1,P2是S中每個的元素可能具有的兩個性質。，分別表示S中具有性質P1，P2的元素的集合，那么有更一般地，設P1,P2，…，Pn是S中每個的元素可能具有的n個性質。令Ai(i=1,2,…,n)是S中具有性質Pi的元素的集合，則有容斥原理2023/7/234第4頁，課件共132頁，創(chuàng)作于2023年2月定理3.2

證任取S中的一個元素a，

(1)若a不具有這n個性質中的任何一個，則a對方程左端的貢獻為1，而對方程右端的貢獻為

容斥原理2023/7/235第5頁，課件共132頁，創(chuàng)作于2023年2月(2)若a具有這n個性質中的m個，則a對方程左端的貢獻為0，而對方程右端的貢獻為

容斥原理2023/7/236第6頁，課件共132頁，創(chuàng)作于2023年2月推論證容斥原理2023/7/237第7頁，課件共132頁，創(chuàng)作于2023年2月例3.2

一個學校只有三門課程：數(shù)學、物理、化學。已知修這三門課的學生分別有170、130、120人；同時修數(shù)學、物理兩門課的學生45人；同時修數(shù)學、化學的20人；同時修物理、化學的22人；同時修三門課的學生3人，問這學校共有多少人？解設M為修數(shù)學課學生的集合

P為修物理課學生的集合

C為修化學課學生的集合容斥原理2023/7/238第8頁，課件共132頁，創(chuàng)作于2023年2月由題意知，所求人數(shù)為容斥原理2023/7/239第9頁，課件共132頁，創(chuàng)作于2023年2月例3.3

求a,b,c,d,e,f六個字母的全排列中不允許出現(xiàn)ace和df圖象的排列數(shù)。解A1為出現(xiàn)ace圖象的排列的集合，A2為出現(xiàn)df圖象的排列的集合，那么有所求排列數(shù)為容斥原理2023/7/2310第10頁，課件共132頁，創(chuàng)作于2023年2月例3.4N={1,2,…,500}，求N中能被2，3，5整除的數(shù)的個數(shù)。解設分別為被2、3、5整除的數(shù)的集合。那么有容斥原理2023/7/2311第11頁，課件共132頁，創(chuàng)作于2023年2月容斥原理2023/7/2312第12頁，課件共132頁，創(chuàng)作于2023年2月例3.5

求由a,b,c,d四個字符構成的n位符號串中，a,b,c至少出現(xiàn)一次的符號串的數(shù)目。證設分別表示不出現(xiàn)a,b,c的n位符號串的集合。則容斥原理2023/7/2313第13頁，課件共132頁，創(chuàng)作于2023年2月另解：設為所求的n位符號串數(shù)目，則{an}的指數(shù)型母函數(shù)為

容斥原理2023/7/2314第14頁，課件共132頁，創(chuàng)作于2023年2月例3.6求不超過120的素數(shù)的個數(shù)。解若一個正整數(shù)n是一個合數(shù)，那么n必能被某個素數(shù)整除。由112=121知，不超過120的合數(shù)必能被2,3,5,7之一整除。設為不超過120,但被i整除的數(shù)的集合,

i=2,3,5,7容斥原理2023/7/2315第15頁，課件共132頁，創(chuàng)作于2023年2月容斥原理2023/7/2316第16頁，課件共132頁，創(chuàng)作于2023年2月所求素數(shù)個數(shù)為：27+4-1=30。容斥原理2023/7/2317第17頁，課件共132頁，創(chuàng)作于2023年2月例3.7

用26個英文字母作不允許重復的全排列，要求排除dog,god,gum,depth,thing字樣的出現(xiàn)，求滿足這些條件的排列數(shù)。解設A1為出現(xiàn)dog的排列的集合；A2為出現(xiàn)god的排列的集合；

A3為出現(xiàn)gum的排列的集合；A4為出現(xiàn)depth的排列的集合；

A5為出現(xiàn)thing的排列的集合。容斥原理2023/7/2318第18頁，課件共132頁，創(chuàng)作于2023年2月所求的排列數(shù)為容斥原理2023/7/2319第19頁，課件共132頁，創(chuàng)作于2023年2月例3.8

求完全由n個布爾變量確定的布爾函數(shù)的個數(shù)。解設n個布爾變量為，自變量可能的取值有個，n個布爾變量的布爾函數(shù)有個。設是一個布爾函數(shù)，不依賴于變量是指對于每一都有容斥原理2023/7/2320第20頁，課件共132頁，創(chuàng)作于2023年2月不依賴于某個布爾變量的布爾函數(shù)有個。不依賴于k個布爾變量的布爾函數(shù)有個。設為不依賴于布爾變量xi的函數(shù)的集合，那么所求函數(shù)的個數(shù)為當n=2時容斥原理2023/7/2321第21頁，課件共132頁，創(chuàng)作于2023年2月例3.9

歐拉函數(shù)表示不大于n，且與n互素的正整數(shù)的個數(shù)。設，表示從1到n中能被整除的數(shù)的集合，那么有

,…容斥原理2023/7/2322第22頁，課件共132頁，創(chuàng)作于2023年2月容斥原理2023/7/2323第23頁，課件共132頁，創(chuàng)作于2023年2月例容斥原理2023/7/2324第24頁，課件共132頁，創(chuàng)作于2023年2月例3.10

錯排問題設表示i在第i位排列的集合，則有，…容斥原理2023/7/2325第25頁，課件共132頁，創(chuàng)作于2023年2月例2.66在8個字母A,B,C,D,E,F,G,H的全排列中，求使A,C,E,G四個字母不在原來位置上的排列的數(shù)目。解設A1,A2,A3,A4分別表示A,C,E,G在原來位置上排列的集合。所求數(shù)目為容斥原理2023/7/2326第26頁，課件共132頁，創(chuàng)作于2023年2月習題3.13.23.163.622023/7/2327第27頁，課件共132頁，創(chuàng)作于2023年2月例3.11

在4個x，3個y，2個z的全排列中，求不出現(xiàn)xxxx、yyy、zz圖象的排列數(shù)。解設分別為出現(xiàn)xxxx、yyy、zz圖象的全排列的集合。則有限制的排列2023/7/2328第28頁，課件共132頁，創(chuàng)作于2023年2月所有全排列的個數(shù)為：有限制的排列2023/7/2329第29頁，課件共132頁，創(chuàng)作于2023年2月n個元素的一個排列可以看作是n個棋子在的棋盤上的一種布局，每行每列有且僅有一個棋子，其中是棋盤第i行棋子所在的列數(shù)例如排列3142所對應的棋盤布局如下圖所示棋盤多項式1234

12342023/7/2330第30頁，課件共132頁，創(chuàng)作于2023年2月可以把棋盤C推廣到任意形狀。令表示k只棋子布到棋盤C的不同的方案數(shù)，規(guī)則是當一個棋子置于棋盤的某一格子時，則這一格子所在的行和列都不能再布任何棋子。棋盤多項式2023/7/2331第31頁，課件共132頁，創(chuàng)作于2023年2月對于給定的棋盤C，稱下列多項式

為棋盤C的棋盤多項式，其中n為棋盤C的格子數(shù)，并定義。例如對右圖所示的棋盤，其棋盤多項式為棋盤多項式2023/7/2332第32頁，課件共132頁，創(chuàng)作于2023年2月在棋盤C上選定一個格子，將分為兩類：

(1)該格子放置棋子：有種放法；

(2)該格子不放置棋子:有種放法.

故有

其中表示從棋盤C中刪除所選定格子所在的行和列后所得到的棋盤，而表示從棋盤C中刪除所選定格子后所得到的棋盤。棋盤多項式2023/7/2333第33頁，課件共132頁，創(chuàng)作于2023年2月由上述關系得棋盤多項式2023/7/2334第34頁，課件共132頁，創(chuàng)作于2023年2月棋盤多項式2023/7/2335第35頁，課件共132頁，創(chuàng)作于2023年2月棋盤多項式2023/7/2336第36頁，課件共132頁，創(chuàng)作于2023年2月棋盤多項式2023/7/2337第37頁，課件共132頁，創(chuàng)作于2023年2月若棋盤是由兩個部分棋盤C1和C2組成，其沒有C1中的格子與C2中的格子在同一行或同一列中，那么有這時有棋盤多項式2023/7/2338第38頁，課件共132頁，創(chuàng)作于2023年2月棋盤多項式2023/7/2339第39頁，課件共132頁，創(chuàng)作于2023年2月有禁區(qū)的排列例考慮1，2，3，4的排列，要求不能為3，不能為1和4，不能為2和4，不能為2。p1p2p3p4

12342023/7/2340第40頁，課件共132頁，創(chuàng)作于2023年2月定理3.3有禁區(qū)的排列數(shù)為

其中是有個棋子布置到禁區(qū)部分的方案數(shù)。

證設Ai(i=1,2,…,n)為第i行的棋子落在禁區(qū)內的方案數(shù)，那么有有禁區(qū)的排列2023/7/2341第41頁，課件共132頁，創(chuàng)作于2023年2月有禁區(qū)的排列例3.12有G,L,W,Y4位工作人員，A,B,C,D為四項任務，但G不能從事任務B；L不能從事任務B，C；W不能從事任務C，D；Y不能從事任務D。若要求每人從事各自力所能及的一項工作，試問有多少種不同的方案？

解ABCDGLWYGLWYCDBA2023/7/2342第42頁，課件共132頁，創(chuàng)作于2023年2月有禁區(qū)的排列圖中禁區(qū)的棋盤多項式為所求的方案數(shù)為

2023/7/2343第43頁，課件共132頁，創(chuàng)作于2023年2月例3.13錯排問題。錯排的個數(shù)為有禁區(qū)的排列2023/7/2344第44頁，課件共132頁，創(chuàng)作于2023年2月有禁區(qū)的排列例3.14設4種材料A,B,C,D擬分配去做1,2,3,4這4種產(chǎn)品。若A不宜于1的產(chǎn)品；B不宜于3,4的產(chǎn)品；C不宜于1,3的產(chǎn)品；D不宜于4的產(chǎn)品。試問有多少種分配方案，使每種產(chǎn)品有一種其適宜的材料。

1234ABCDABCD21432023/7/2345第45頁，課件共132頁，創(chuàng)作于2023年2月有禁區(qū)的排列***2023/7/2346第46頁，課件共132頁，創(chuàng)作于2023年2月有禁區(qū)的排列所求分配方案數(shù)為2023/7/2347第47頁，課件共132頁，創(chuàng)作于2023年2月廣義容斥原理設P1,P2，…，Pn是S中每個的元素可能具有的n個性質。令Ai(i=1,2,…,n)是S中具有性質Pi的元素的集合.

記2023/7/2348第48頁，課件共132頁，創(chuàng)作于2023年2月廣義容斥原理

2023/7/2349第49頁，課件共132頁，創(chuàng)作于2023年2月廣義容斥原理定理3.42023/7/2350第50頁，課件共132頁，創(chuàng)作于2023年2月證任取一個元素a。若a有少于m個性質，那么a對方程的左端和右端的貢獻都為0。若a恰有m個性質，那么a對方程的左端和右端的貢獻都為1。若a恰有個性質，那么a對等式的左端貢獻為0，而對等式的右端的貢獻為廣義容斥原理2023/7/2351第51頁，課件共132頁，創(chuàng)作于2023年2月廣義容斥原理2023/7/2352第52頁，課件共132頁，創(chuàng)作于2023年2月例3.15某學校有12位教師，已知教數(shù)學、物理、化學課教師分別有8位，6位，5位，其中有5位既教數(shù)學又教物理，有4位兼教數(shù)學和化學，兼教物理和化學的有3位；有3位教師教3門課，試問教數(shù)、理、化以外課的教師有幾位？只教一門課的教師有幾位？正好教兩門課的教師有幾位？解設A1,A2,A3分別表示教數(shù)學、物理、化學課教師的集合。則廣義容斥原理2023/7/2353第53頁，課件共132頁，創(chuàng)作于2023年2月廣義容斥原理教數(shù)、理、化以外課的教師的人數(shù)為只教一門課的教師的人數(shù)為正好教兩門課的教師的人數(shù)為2023/7/2354第54頁，課件共132頁，創(chuàng)作于2023年2月問題：求滿足線性方程的非負整數(shù)解的數(shù)目。

上述方程的非負整數(shù)解與r個無區(qū)別的球放進n個有標志的盒子方案一一對應。故上述方程非負解的個數(shù)為若干應用2023/7/2355第55頁，課件共132頁，創(chuàng)作于2023年2月考慮下列問題：求方程

的整數(shù)解的數(shù)目。若無上界條件，方程非負整數(shù)解的數(shù)目為若干應用2023/7/2356第56頁，課件共132頁，創(chuàng)作于2023年2月令A1,A2,A3分別為所有非負整數(shù)解中滿足,,的解的集合。則所求解的個數(shù)為若干應用2023/7/2357第57頁，課件共132頁，創(chuàng)作于2023年2月若干應用考慮下列問題：如下圖所示，求從O(0,0)點到P(10,5)點的路徑中不通過AB，CD，EF，GH中任何一條路徑的路徑數(shù)。P(10,5)O(0,0)ABCDFEGH2023/7/2358第58頁，課件共132頁，創(chuàng)作于2023年2月設A1,A2,A3,A4分別為從O點到P點過AB邊、CD邊、EF邊、GH邊的路徑；

若干應用2023/7/2359第59頁，課件共132頁，創(chuàng)作于2023年2月若干應用2023/7/2360第60頁，課件共132頁，創(chuàng)作于2023年2月所求路徑數(shù)為而容斥原理2023/7/2361第61頁，課件共132頁，創(chuàng)作于2023年2月習題3.103.213.222023/7/2362第62頁，課件共132頁，創(chuàng)作于2023年2月

n個有區(qū)別的球放到m個相同的盒子中，要求無一空盒，其不同的方案數(shù)用S(n,m)表示，稱為第二類Stirling數(shù)。n個有區(qū)別的球放到m個不同的盒子中，要求無一空盒，求不同的方案數(shù)。

設Ai為使第i個盒子為空的方案的集合，i=1,2,…,m。則有第二類司特林數(shù)展開式2023/7/2363第63頁，課件共132頁，創(chuàng)作于2023年2月容斥原理2023/7/2364第64頁，課件共132頁，創(chuàng)作于2023年2月所求方案為由知容斥原理2023/7/2365第65頁，課件共132頁，創(chuàng)作于2023年2月例容斥原理2023/7/2366第66頁，課件共132頁，創(chuàng)作于2023年2月推論1推論2由，容斥原理2023/7/2367第67頁，課件共132頁，創(chuàng)作于2023年2月問題：設S={1,2,…,n}，從S中取r個進行排列，得要求只有k個數(shù)滿足，這樣的錯排數(shù)用來表示。

例從4個中取3個的排列數(shù)為P(4,3)=24

其中，這11個排列為

231，312，214，241，412，314，341，431，234，342，432錯排問題的推廣2023/7/2368第68頁，課件共132頁，創(chuàng)作于2023年2月定理對于正整數(shù)，若，則有證設Ai為滿足的所有r排列的集合，i=1,…,r

當時，我們有容斥原理2023/7/2369第69頁，課件共132頁，創(chuàng)作于2023年2月，這9個排列為

132，213，321，142，421，134，413，243，324

，這3個排列為

124，143，423

，這1個排列為：123。

容斥原理2023/7/2370第70頁，課件共132頁，創(chuàng)作于2023年2月容斥原理2023/7/2371第71頁，課件共132頁，創(chuàng)作于2023年2月廣義容斥原理定理3.42023/7/2372第72頁，課件共132頁，創(chuàng)作于2023年2月容斥原理2023/7/2373第73頁，課件共132頁，創(chuàng)作于2023年2月容斥原理例2023/7/2374第74頁，課件共132頁，創(chuàng)作于2023年2月容斥原理2023/7/2375第75頁，課件共132頁，創(chuàng)作于2023年2月容斥原理性質：

(1)

證

2023/7/2376第76頁，課件共132頁，創(chuàng)作于2023年2月例容斥原理2023/7/2377第77頁，課件共132頁，創(chuàng)作于2023年2月

(2)

證容斥原理2023/7/2378第78頁，課件共132頁，創(chuàng)作于2023年2月鴿巢原理：若n+1個鴿子飛入n個鴿巢，則至少有一個鴿巢中有兩只鴿子。

例3.19從1到2n的正整數(shù)中任取n+1個，則這n+1個數(shù)中至少有一對數(shù)，其中的一個數(shù)是另一個數(shù)的倍數(shù)。

解設所取的n+1個數(shù)是：。令

其中為奇數(shù)。鴿巢原理2023/7/2379第79頁，課件共132頁，創(chuàng)作于2023年2月由于1到2n的正整數(shù)中只有n個奇數(shù)，故

中至少有兩個相等。設，那么當時，是的倍數(shù)，否則是的倍數(shù)。鴿巢原理2023/7/2380第80頁，課件共132頁，創(chuàng)作于2023年2月例3.20設是正整數(shù)序列，則至少存在整數(shù)k和，使得證構造部分和

(1)若存在h，使得,此時取,即可.

(2)若不存在h，使得，這時存在,

其被m除所得的余數(shù)相等，所以

鴿巢原理2023/7/2381第81頁，課件共132頁，創(chuàng)作于2023年2月鴿巢原理2023/7/2382第82頁，課件共132頁，創(chuàng)作于2023年2月例3.22設為三個任意的整數(shù)，為的任一排列，則中至少有一個是偶數(shù)。證中至少有兩個數(shù)的奇、偶性相同。不妨設同為奇數(shù)。故中至少有一個是奇數(shù)。所以中至少有一個是偶數(shù)。鴿巢原理2023/7/2383第83頁，課件共132頁，創(chuàng)作于2023年2月例3.23設是由1,2組成的序列，已知從其中任意一個數(shù)開始的順序10個數(shù)的和不超過16，即對，恒有則存在，使得解作序列 鴿巢原理2023/7/2384第84頁，課件共132頁，創(chuàng)作于2023年2月由于，故?？紤]由知至少有兩項相等。但，鴿巢原理2023/7/2385第85頁，課件共132頁，創(chuàng)作于2023年2月所以存在，使得即有鴿巢原理2023/7/2386第86頁，課件共132頁，創(chuàng)作于2023年2月定理設都是正整數(shù)，若有只鴿子飛入n個鴿巢，則存在，使得第j個鴿巢至少有只鴿子。推論1:設k和n都是正整數(shù)，若至少有kn+1只鴿子分配在n個鴿巢里，則至少存在一個鴿巢，使得該鴿巢中至少有k+1只鴿子。鴿巢原理的推廣2023/7/2387第87頁，課件共132頁，創(chuàng)作于2023年2月推論2m只鴿子，n個鴿子巢，則至少有一個鴿子巢里有不少于只鴿子。

證若每個鴿巢中至多有只鴿子，則n個鴿巢中最多有

只鴿子，與假設矛盾。鴿巢原理的推廣2023/7/2388第88頁，課件共132頁，創(chuàng)作于2023年2月推論3將個球放入n個盒子，則至少有一個盒子有m個球。

推論4若是n個正整數(shù)，而且則中至少有一個數(shù)不小于r鴿巢原理的推廣2023/7/2389第89頁，課件共132頁，創(chuàng)作于2023年2月例

例3.25設是由10個0和10個1組成的20位二進制數(shù)串；是任意的20位二進制數(shù)串?，F(xiàn)將A、B分別記入如圖(A)、(B)兩個20個格子，分別得到(A)、(B)兩種圖象，并把兩個B連接得40位二進制數(shù),它的圖象為(C)?！?A)(B)(C)2023/7/2390第90頁，課件共132頁，創(chuàng)作于2023年2月證明存在某一配合可以使圖象(C)上某相連的20格正好和圖象(A)的20格中至少10位對應數(shù)字相同。證將(A)的第1格對應(C)的第i格(i=1,2,…,20)。在這個過程中，圖象(B)的每一格和(A)的每一格比較相同了10次，相同的數(shù)字數(shù)目之和為,

平均每次有相同數(shù)字的格數(shù)為故至少有一次，其中相同的數(shù)字的格數(shù)不少于10。例2023/7/2391第91頁，課件共132頁，創(chuàng)作于2023年2月定理任意n2+1個不同的實數(shù)

組成的序列中，必有一個長度為n+1的單調增子序列或單調減子序列。給定序列5,3,16,10,15,14,9,11,6,7

單調增子序列

5,16；5,10,15；3,9,11；3,6,7；單調減子序列

5,3；16,10,9,6；16,15,14,11,6；例2023/7/2392第92頁，課件共132頁，創(chuàng)作于2023年2月證假定沒有長度為n+1的單調增子序列，下面證明必有長度為n+1的單調降子序列。設表示從開始的最長的單調增子序列的長度，由假設知由鴿巢原理知，至少有例2023/7/2393第93頁，課件共132頁，創(chuàng)作于2023年2月個，使得不失一般性，假設，則有即存在一個長度為n+1的單調減子序列。例2023/7/2394第94頁，課件共132頁，創(chuàng)作于2023年2月3.33.63.73.54

習題2023/7/2395第95頁，課件共132頁，創(chuàng)作于2023年2月定理設都是正整數(shù)，若有只鴿子飛入n個鴿巢，則存在，使得第j個鴿巢至少有只鴿子。推論1:設k和n都是正整數(shù)，若至少有kn+1只鴿子分配在n個鴿巢里，則至少存在一個鴿巢，使得該鴿巢中至少有k+1只鴿子。鴿巢原理的推廣2023/7/2396第96頁，課件共132頁，創(chuàng)作于2023年2月推論3將個球放入n個盒子，則至少有一個盒子有m個球。

推論4若是n個正整數(shù)，而且則中至少有一個數(shù)不小于r

證在推論1中取,并注意鴿巢原理的推廣2023/7/2397第97頁，課件共132頁，創(chuàng)作于2023年2月例3.28設A={1,2,…,99}，X是A的子集,且,則可以找到X的兩個互不相交的真子集Y和Z，使得Y中元素之和等于Z中元素之和。

解由于，所以X有個非空真子集，但X的非空真子集S中的元素之和滿足

例2023/7/2398第98頁，課件共132頁，創(chuàng)作于2023年2月現(xiàn)在有1022只鴿子，855個鴿巢，故至少有兩個鴿巢中的鴿子數(shù)相等。設這兩個子集為B和C，則

(1)當時，令Y=B，Z=C即可；

(2)當時，令即可。例2023/7/2399第99頁，課件共132頁，創(chuàng)作于2023年2月例一個抽屜里有20件襯杉，其中4件是藍的，7件是灰的，9件是紅的。試問應從中隨意抽取多少件能保證有4件是同色的？又應抽取多少件能保證有5，6，7，8，9件是同色的？解由鴿巢原理：n個鴿巢，kn+1只鴿子，則至少存在一個鴿巢，使得該鴿巢中至少有k+1只鴿子。

(1)這時n=3，k+1=4，所以k=3，于是

即隨意抽取10件能保證有4件是同色的。例2023/7/23100第100頁，課件共132頁，創(chuàng)作于2023年2月推論2m只鴿子，n個鴿子巢，則至少有一個鴿子巢里有不少于只鴿子。

證由

及推論1便知結論正確鴿巢原理的推廣2023/7/23101第101頁，課件共132頁，創(chuàng)作于2023年2月

(2)這時不能直接用鴿巢原理?？紤]一種最壞的情形，在所抽取的襯衫中有4件是藍的。這時n=2，k+1=5，所以k=4，于是應抽取

即隨意抽取13件能保證有5件是同色的。例2023/7/23102第102頁，課件共132頁，創(chuàng)作于2023年2月

(3)同樣假設在所抽取的襯衫中有4件是藍的。這時n=2，k+1=6，所以k=5，于是應抽取即隨意抽取15件能保證有6件是同色的。同理可證，隨意抽取17，19，20件能保證有7，8，9件是同色的。例2023/7/23103第103頁，課件共132頁，創(chuàng)作于2023年2月問題：6個人中，或有3個人互相認識，或有3個人互相不認識。每個人用一個頂點表示，若兩個人互相認識，則對相應的兩個頂點之間的邊著紅色，若兩個人互相不認識，則對相應的兩個頂點之間的邊著藍色。這樣問題就轉化為：給定一個6個頂點的完全圖K6，用紅、藍兩色對其邊任意著色，那么或者存在一個紅色邊三角形，或者存在一個藍色邊三角形。Ramsey數(shù)2023/7/23104第104頁，課件共132頁，創(chuàng)作于2023年2月證選定K6的一個頂點v，頂點v有5條邊,由鴿巢原理知，至少有

條同色邊，設為紅色。設這三條邊的另一個端點分別為v1,v2,v3。若v1,v2,v3之間有一條紅色邊，則已得到一個紅色邊三角形，否則，則得到一個藍色邊三角形。Ramsey數(shù)vv1v2v32023/7/23105第105頁，課件共132頁，創(chuàng)作于2023年2月若干推論

(a)對6個頂點的完全圖K6的邊用紅、藍兩色任意著色，那么至少有兩個同色三角形。

下面分情況討論：Ramsey數(shù)圖1圖2圖32023/7/23106第106頁，課件共132頁，創(chuàng)作于2023年2月

(1)

若紅色三角形的某個頂點的其它三條邊均為藍色

(2)若紅色三角形的某個頂點的其它三條邊中至少有兩條為紅色；

(3)若紅色三角形的任一個頂點的其它三條邊中恰有一條邊為紅色。Ramsey數(shù)2023/7/23107第107頁，課件共132頁，創(chuàng)作于2023年2月(b)對10個頂點的完全圖K10的邊用紅、藍兩色任意著色,那么或者有一紅色K4,或者有一藍色K3。

證設a是K10的一個頂點，與a關聯(lián)的9條邊中,或者有6條紅邊,或者有4條藍邊。

(1)若與a關聯(lián)的9條邊中有4條藍邊；Ramsey數(shù)a2023/7/23108第108頁，課件共132頁，創(chuàng)作于2023年2月(2)若與a關聯(lián)的9條邊中有6條紅邊。這時與a鄰接的6個頂點所組成的完全圖中或有一個紅色的K3，或有一個藍色的K3。若有紅色的K3，則該K3與頂點a所組成的K4是一個紅色的K4；否則有一個藍色的K3。Ramsey數(shù)a2023/7/23109第109頁，課件共132頁，創(chuàng)作于2023年2月(c)對9個頂點的完全圖K9的邊用紅、藍兩色任意著色，那么或者有一紅色K4，或者有一藍色K3。

證在K9中，如果與每個頂點關聯(lián)的紅邊均為5條，那么在K9中，應有

條紅邊。但這是不可能的。故必有一個頂點的紅邊數(shù)不為5。設此頂點為a,則與a關聯(lián)的紅邊數(shù)至少為6,或者至多為4。以下與推論(b)的證明類似。Ramsey數(shù)2023/7/23110第110頁，課件共132頁，創(chuàng)作于2023年2月(d)對18個頂點的完全圖K18的邊用紅、藍兩色任意著色,那么或者有一紅色K4,或者有一藍色K4。證設a是K18的一個頂點，與a關聯(lián)的17條邊中,至少有9條是同色邊,不妨設為紅色邊。在這9條邊的另9個端點構成的完全圖K9中,或有一個紅色K3,或有一個藍色K4.

若有一個紅色K3,則a與該紅色K3構成一個紅色K4.

否則有一個藍色K4.Ramsey數(shù)2023/7/23111第111頁，課件共132頁，創(chuàng)作于2023年2月例對17個頂點的完全圖K17的邊用紅、藍、黃三種顏色任意著色，那么或者有一紅色K3，或者有一藍色K3，或者有一黃色的K3。證任取K17中的一個頂點a，在與a關聯(lián)的16條邊中，至少有6條是同色的，不妨設為紅色。Ramsey數(shù)a2023/7/23112第112頁，課件共132頁，創(chuàng)作于2023年2月定義對于任意給定的兩個正整數(shù)a和b，如果存在最小的正整數(shù),使得當時，對中的邊用紅、藍兩色任意著色，中或者有紅色,或者有藍色,則稱為Ramsey數(shù)。例Ramsey數(shù)2023/7/23113第113頁，課件共132頁，創(chuàng)作于2023年2月定理1,。

定理2對任意整數(shù)，存在。定理3對任意正整數(shù)，有

證令,對KN中的邊用紅、藍兩色任意著色。設x是KN的一個頂點，在KN中與x關聯(lián)的邊共有條,在這些邊中,或者至少有條紅邊,Ramsey數(shù)2023/7/23114第114頁，課件共132頁，創(chuàng)作于2023年2月或者至少有條藍邊。

(1)有條紅邊。在這些紅邊與x關聯(lián)的個頂點構成的完全圖中,或者有一個紅色,或者有一個藍色.

若有紅色,則該紅色加上頂點x以及x與頂點之間的紅邊，構成一個紅色;否則有一個藍色。Ramsey數(shù)2023/7/23115第115頁，課件共132頁，創(chuàng)作于2023年2月(2)有條藍邊在這些藍邊與x關聯(lián)的個頂點構成的完全圖中,或有一個紅色,或有一個藍色。若有藍色，則該藍色加上頂點x以及x與頂點之間的藍邊，構成一個藍色;否則有一個紅色。

由(1)、(2)知。Ramsey數(shù)2023/7/23116第116頁，課件共132頁，創(chuàng)作于2023年2月利用定理3.15，我們可以計算出R(a,b)的上界。Ramsey數(shù)

b234567a223456733610152128441020355515352023/7/23117第117頁，課件共132頁，創(chuàng)作于2023年2月定理4對任意正整數(shù)，有

證對a+b用歸納法。當a+b=4時，定理顯然成立。假設對一切滿足的a,b，定理成立，那么有Ramsey數(shù)2023/7/23118第118頁，課件共132頁，創(chuàng)作于2023年2月這就歸納地證明了定理。Ramsey數(shù)2023/7/23119第119頁，課件共132頁，創(chuàng)作于2023年2月設為正整數(shù)，對N個頂點的完全圖中的邊用k種顏色進行著色，則中或有顏色的,或有顏色的,…，或有顏色的，滿足上述性質的N的最小值記為。Ramsey數(shù)的推廣2023/7/23120第120頁，課件共132頁，創(chuàng)作于2023年2月定理5

對任意正整數(shù)，有證設對中的邊用染色,并將看作是紅色,將看作是藍色,

則或有一個紅色,或者有藍色的,在藍色的中,其邊是用染色的,

故中或有色的,…,或有色的。Ramsey數(shù)的推廣2023/7/23121第121頁，課件共132頁，創(chuàng)作于2023年2月例定理6

對任意的正整數(shù),有定理7對任意的正整數(shù),有

Ramsey數(shù)的推廣2023/7/23122第122頁，課件共132頁，創(chuàng)作于2023年2月一個半群是一個具有滿足結合律二元運算的有限集合。命題:任何有限半群有一個冪等元證令a是半群中的任一個元素，n是半群的階。設,對KN

的邊用n種顏色著色，其中這n種顏色分別響應半群的n個元素。對邊(i,j)著色,由Ramsey定理,KN中存在一個單色三角形,即存在,使得

應用2023/7/23123第123頁，課件共132頁，創(chuàng)作于2023年2月令，便得應用2023/7/23124第124頁，課件