哈工大-組合數學講義2010版-新

1、組合數學(Combinatorics),哈爾濱工業(yè)大學(威海)計算機科學與技術學院孟凡超 Email: mfc@hitwh.edu.cnTele：15163155787,參考書目,組合數學(第四版)/(美)布魯斯(Brualdi, R.A)著；北京機械工業(yè)出版社,2005.2盧開澄,組合數學,清華大學出版社.,主要內容,概述鴿巢原理 排列與組合生成排列和組合 二項式系數 容斥原理及應用 遞推關系和生成

2、函數特殊計數序列二分圖中的匹配 Polya計數法,概述,數學研究問題研究連續(xù)對象(微積分)研究離散對象(組合數學)組合數學研究的問題將一個集合的物體排列成滿足一些指定規(guī)則的格式，如下兩類問題反復出現：排列存在性：如果想要排列一個集合的成員使得某些條件得以滿足，并且這種排列不總是可能的，那么這種排列在什么樣的條件下滿足。排列的計數和分類：如果一個指定的排列是可能的，那么會有多少種方法去實現它。此時，人們就可以計數并將它

3、們分類。,概述,棋盤的完美覆蓋：考慮一張8?8(8行8列)的64個正方形的國際象棋棋盤，設有形狀一樣的多米諾牌，每張牌恰好覆蓋棋盤上相鄰的兩個方格，那么，是否能夠把32張多米諾牌擺放到棋盤上，使得任何兩張多米諾牌均不重疊，每張多米諾牌覆蓋兩個方格，并且棋盤上的所有方格都被覆蓋?。课覀儼堰@樣一種排列稱為棋盤的多米諾牌的完美覆蓋。,8?8棋盤,完美覆蓋1,完美覆蓋2,完美覆蓋數：12988816=24?(901)2),概述,與上述問題同時出

4、現的另外兩種組合數學問題：研究一個已知的排列：當人們建立起滿足某些指定條件的一個排列以后，可能要考察這個排列的性質和結構，這樣的結構可能會涉及到分類問題。構造一個最優(yōu)的排列：如果可能存在多于一個的排列，人們也許想要確定滿足某些優(yōu)化準則的一個排列，即找出某種規(guī)定意義下的“最好的”或“最優(yōu)的”排列。,概述,例，設S={1,2,3,4}為一個集合 1)從S中取兩個不相同的元素進行排列，這樣的排列有多少種2)列出所有可能的排列。3)求

5、出兩個元素之和最大的排列。,組合數學是研究離散結構的存在、計數、分析和優(yōu)化等問題的一門科學。,概述,問題1. 如果將棋盤變?yōu)?m?n (m行n列)，則完美覆蓋是否存在？,問題2. 對于什么樣的m和n存在完美覆蓋？,當且僅當m和n中至少有一個是偶數時，m?n 棋盤存在完美覆蓋。,不一定存在，例如，3行3列的棋盤就不存在完美覆蓋。,概述,問題3. 8?8的棋盤用一把剪刀剪掉棋盤一副對角上的兩個方格，總共剩下62個方格，那么是否能夠排列31張

6、多米諾牌來得出對這幅被剪過棋盤的完美覆蓋？,不存在完美覆蓋。在一副8?8棋盤上交替地將方格涂成黑色和白色，則其中的32個方格是黑色，32個方格是白色。如果我們剪掉棋盤一副對角線上的兩個方格，那么我們就剪掉同樣種顏色的兩個方格，比如兩個白色方格。這就變成了32個黑方格和30個白方格。但是，每張多米諾牌需要一個白方格和一個黑方格，于是，31張不重疊的多米諾牌則覆蓋住31個黑方格和31個白方格。因此，這幅被剪過的棋盤不存在完美覆蓋。,概

7、述,問題4. 將m?n的棋盤上的方格交替涂成黑色和白色，切除一些方格，得到一塊被剪過的棋盤，這塊棋盤什么時候有一個完美覆蓋？,必要條件。這塊被剪過的棋盤必須具有相等的黑方格數和白方格數。該條件不是充分條件。,4?5棋盤,概述,B-牌：設b是一個正整數，我們用b個1?1的方格并排連接成的1?b的方格條來代替多米諾牌，這些方方格條稱為b-牌。,一張5-牌,一張2-牌（多米諾牌）,m?n棋盤被B-牌的完美覆蓋：b-牌在m?n棋盤上沒有兩張

8、重疊，每一條b-牌蓋住棋盤上的b個方格，并且盤上的所有方格都被覆蓋住。,概述,問題5. m?n棋盤何時具有b-牌的完美覆蓋？,當且僅當b是m的一個因子或者b是n的一個因子,充分性。如果b是m的一個因子或者b是n的一個因子，則m?n棋盤存在b-牌完美覆蓋。,如果b是m的一個因子，我們就可以對n列的每一列用m/b個b-牌覆蓋并進而完成對m?n棋盤的完美覆蓋。如果b是n的一個引子，我們就可以對m行的每一行用n/b個b-牌覆蓋并進而完成對m?

9、n棋盤的完美覆蓋。,概述,必要性。如果m?n棋盤存在b-牌完美覆蓋，則b或者是m一個因子或者是n的一個因子。,我們需要證明m和n除以b的余數至少有一個是零。設b除以m和n得到商p和q以及余數r和s, m=pb+r (0?r?b-1)n=qb+s (0?s?b-1)我們不妨設r?s，因此，我們需要證明r=0。采用反證法，設r>0。,主要內容,概述鴿巢原理 排列與組合 生成排列和組合二項式系數 容斥原理及應用

10、遞推關系和生成函數特殊計數序列 二分圖匹配Polya計數法,鴿巢原理,鴿巢原理：簡單形式定理1. 如果n+1個物體被放進n個盒子中，那么至少有一個盒子包含兩只或更多的物體。其它表述形式：如果n+1只鴿子被放進n個鴿巢中，那么至少有一個鴿巢包含兩只或更多的鴿子。如果n+1個物體用種顏色涂色，那么必然有兩個物體被涂成相同的顏色。,鴿巢原理,,,,,4個物體,3個盒子,,存放,,,,,,,,,,,,,,,,,,,,,,,,,,,

11、,,,,,,,,,,,,,1,2,3,4,5,鴿巢原理,例題：例1：在13個人中存在兩個人，他們的生日在同一個月份里?？紤]12個盒子，每個盒子對應一個月份，將13個人放到12個盒子中，則至少有一個盒子包含兩個或兩個以上的人，即，這在13個人中存在兩個人，他們的生日在同一個月份里。例2：設有n對已婚夫婦。為保證能夠有一對夫婦被選出，至少要從這2n個人中選出多少人。應至少選擇n+1個人。考慮n個盒子，每個盒子對應一對夫婦。如果我們選

12、擇n+1個人并把他們中的每一個人放到他們對偶所在的那個盒子中去，那么就有同一個盒子含有兩個人，也就是說，我們選擇了一對已婚夫婦。如果選擇n個人，可以只選擇所有丈夫或只選擇所有的妻子。,鴿巢原理,與鴿巢原理相關的原理定理2：如果將n個物體放入n個盒子并且沒有一個盒子是空的，那么每個盒子恰好包含一個物體。定理3：如果將n個物體放入n個盒子且沒有一個盒子被放入多于一個物體，那么每個盒子里有一個物體。,鴿巢原理,函數基本知識函數：集合之

13、間的函數(function，或說映射mapping)：設X和Y是任意兩個集合，而f 是X到Y的一個關系，如果對于每一個x?X,有唯一的y?Y，使得?f，稱關系f 為函數，記作f : X?Y或 X ? Y。原象和象：如果?f，則x稱為自變元（原象），y稱為在f 作用下x的象(image)，?f 亦可記作y=f(x)，且記f(X)={ f(x)| x?X} 。,鴿巢原理,函數基本知識定義域：函數f : X?Y的定義域(domain) d

14、om f 定義為： dom f = {x | 存在某個y?Y使得?f } =X 。值域：函數f : X?Y的值域(range) ran f 定義為： ran f = {y | (?x)(x?X)??f }?Y。全函數：f 是全函數(total function)若dom f=X， f 是全函數,否則稱f是偏函數(partial function)。

15、,鴿巢原理,函數基本知識滿射： f 是滿射( surjection, 或說f maps X onto Y )如果ran f = Y，即對任意的y?Y都有原像。設f : X?Y是滿射，即對任意的y?Y，必存在x?X，使得f(x) = y成立。入射：f 是入射(injection，或說f is one to one 是一對一)設f : X?Y是入射，即對任意的x1, x2?X，如果f (x1) = f (x2), 則x1 =

16、 x2，或者 如果x1≠x2，則得f (x1) ≠ f (x2)。,鴿巢原理,從函數角度來分析鴿巢原理的含義設X和Y是兩個有限集，并令f :X?Y是一個從X到Y的函數。如果X的元素多于Y的元素，那么f 就不是一對一的。如果X和Y含有相同個數的元素，并且f 是映上(onto)的，那么f 就是一對一的。如果X和Y含有相同個數的元素，并且f是一對一的，那么f 就是映上的。,鴿巢原理,例3：給定m個整數a1,a2,…,am,存在整數k

17、和l，0≤k<l≤m， 使得ak+1,ak+2,…,al能夠被m整除。也就是說，在序列a1,a2,…,am中存在連續(xù)個元素，它們的和能被m整除。,考慮m個和：a1,a1+a2,a1+a2+a3,…,a1+a2+a3+...+am如果這些和中存在一個可以被m整除，那么結論就成立。否則，這些和中的任意一個都不能被m整除，即，這些和中的每一個除以m都有一個非零余數，余數等于1,2,…,m-1。由于m個和而只有m-1個余數，如果我們將和

18、看成是物體，余數看成是盒子，根據鴿巢原理，那么必有兩個和除以m有相同的余數。因此，存在整數k和l，k<l，使得a1+a2+...+ak和a1+a2+...+al除以m有相同的余數r，a1+a2+...+ak=bm+r， a1+a2+...+al=cm+r兩式相減，有ak+1+ak+2+...+al=(c-b)m，從而ak+1+ak+2+...+al能夠被m整除。,鴿巢原理,例4：一位國際象棋大師有11周的時間備戰(zhàn)一場錦標賽，他

19、決定每天至少下一盤棋，但是為了使自己不過分疲勞他還決定在每周不能下棋超過12盤。證明存在連續(xù)若干天，期間這位大師恰好下了21盤棋。一共備戰(zhàn)11?7=77天。令x1,x2,…,x77分別為第1,2,…,77天下的棋數，則xi≥1(i=1,2,…,77)。我們構造如下嚴格遞增序列：a1=x1, a2=x1+x2, a3=x1+x2+x3,…,a77=x1+x2+x3…+x77，其中，ai表示前i (i=1,2,…,77)天下棋的總數，并

20、且1≤a1<a2<a3,…,<a77 ≤11?12=132 。則序列a1+21, a2+21,a3+21,…,a77+21 也是一個嚴格遞增序列，并且22≤a1+21<a2+21<a3+21,…,<a77+21 ≤153 。,鴿巢原理,于是，這154個數：a1,a2,…,a77,a1+21,a2+21,…,a77+21中的每一個都是1到153中的一個整數。如果我們將這個序列中的每個元素作為物體，1到

21、153中的每個數作為盒子，根據鴿巢原理，在這154中必有兩個元素相等，既然a1,a2,…,a77中沒有相等的元素，a1+21,a2+21,…,a77+21中也沒有相等的元素，則必然存在一個i和j(1≤i,j ≤77)使得aj=ai+21，從而這位國際象棋大師在第i+1,i+2,…,j天總共下了21盤棋。,鴿巢原理,例5：從整數1,2,3,…,200中我們選擇101個整數。證明，在所選擇的這些整數之間存在兩個這樣的整數，其中一個可以被另一

22、個整除。整數分解知識：任何一個整數都可以寫成2k?a的形式，其中，k≥0，a為奇數。對于1,2,3,…,200之間的一個整數，a是100個數1,3,…,199中的一個。因此，如果我們將所選擇的101個數作為物體，1,3,…,199這100個奇數作為盒子，根據鴿巢原則，在這101中存在兩個整數，當寫成上述形式時這兩個數具有相同的a值。令這兩個數是2r?a和2s?a。如果rs，那么第二個數就能被第一個數整除。,鴿巢原理,例6(中國乘余定

23、理)：令m和n是兩個互素的整數，并令a和b為兩個整數，且0≤a≤m-1以及0≤b≤n-1 。于是存在一個整數x，使得x除以m的余數為a，并且x除以n的余數為b，即，x既可以寫成x=pm+a的同時又可以寫成x=qn+b的形式，在這里，p和q為兩個整數。素數定義：如果兩個整數m和n的最大公約數為1，我們稱m和n為互素。為了證明這個結論，我們需要構造出x，那么如何構造？我們首先按照x=pm+a的形式構造x(p取0,1,…,n-1)，考慮

24、如下n個整數：a, m+a, 2m+a,…, (n-1)m+a。這些整數中的每個除以m的余數都為a，即x可以寫成pm+a的形式。如果我們能夠證明a, m+a, 2m+a,…, (n-1)m+a這n個數中存在一個數能夠寫成qn+b的形式，則即可證明本題結論。,鴿巢原理,如果a, m+a, 2m+a,…, (n-1)m+a中的每個數除以n的余數都不相等，則我們將這n個數作為物體，n的余數0,1,2,…,n-1作為盒子，根據鴿巢原理(定理3

25、)， 0,1,2,…,n-1中的每個數作為余數都會出現，特別是數b作為余數也會出現。令p為整數，滿足0 ≤p ≤n-1，且使數x=pm+a除以n的余數為b，則對某個適當的q，有x=qn+b，因此，x=pm+a且x=qn+b，從而x具有所要求的性質。否則，如果這n個數存在兩個數除以n有相同的余數r，我們令這兩個數分別為im+a和jm+a，其中，0≤i<j≤n-1，因此，存在兩個整數qi和qj，使得,鴿巢原理,im+a=qin+r,

26、 jm+a=qjn+r，用第二個方程減去第一個方程，得到(j-i)m=(qj-qi)n，這說明n是(j-i)m的一個因子。由于n與m沒有除了1之外的公因子，因此n是j-i的一個因子，然而， 0≤j-i≤n-1，也就是說，n不可能是j-i的一個因子。這個矛盾產生于我們假設a, m+a, 2m+a,…, (n-1)m+a中有兩個除以n會有相同的余數。因此，我們斷言，這n個數中的每一個除以n都會有不同的余數，這樣根據前述結論即可證明本題正確

27、性。,鴿巢原理,鴿巢原理：加強形式定理4. 令q1,q2,…,qn為n個正整數。如果將q1+q2+…+qn-n+1個物體放入n個盒子內，那么，或者第一個盒子至少含有q1個物體，或者第二個盒子至少含有q2個物體,…,或者第n個盒子至少含有qn個物體。,證明：采用反證法，設將q1+q2+…+qn-n+1個物體放入到n個盒子中，如果對于每個i=1,2,…,n，第i個盒子含有少于qi個物體，那么所有盒子中的物體總數不超過(q1-1)+(q2

28、-1)+…+(qn-1)=q1+q2+…+qn-n這與物體的總數為q1+q2+…+qn-n+1相矛盾，所以或者第一個盒子至少含有q1個物體，或者第二個盒子至少含有q2個物體,…,或者第n個盒子至少含有qn個物體。,鴿巢原理,鴿巢原理的簡單形式是其加強形式通過q1=q2=…=qn=2來實現的。這時， q1+q2+…+qn-n+1=2n-n+1=n+1。,,,,,,,,q1=2,,,,,q2=3,q3=4,q1+q2+q3-3+1=7,b

29、1≥2,,,,,,,,或,或,b1,b2,b3,b1≥3,b1≥4,鴿巢原理,推論1. m個物體，n個盒子，則至少有一個盒子里有不少于[(m-1)/n]+1個物體。,證明：采用反證法，設所有盒子了最多有[(m-1)/n]個物體，則n個盒子中的物體數最多為n[(m-1)/n] ≤m-1，與假設矛盾。,推論2：若取n(m-1)+1個物體放入n個盒子中，則至少有1個盒子有m個物體。,這個推論相當于q1=q2=…=qn=m時的特殊情況。,采用著

30、色的術語來表述：如果q1+q2+…+qn-n+1個物體中的每一個物體被指定用n種顏色中的一種著色，那么，存在這樣一個i，使得第i種顏色的物體至少有qi個。,鴿巢原理,推論3：若m1,m2,…,mn是n個正整數，而且,則m1,m2,…,mn中至少有1個數不小于r。,證明：將該問題與推論2建立聯系。取n(r-1)+1個物體放入n個盒子中，設mi (i=1,2,…,n)是第i個盒子中的物體個數，于是，這n個數m1,m2,…,mn的平均數為,由

31、于這個平均數大于r-1，故而有一個整數mi至少是r。,鴿巢原理,練習1：如果n個非負整數m1,m2,…,mn的平均數小于r+1，即,則m1,m2,…,mn中至少有1個數不超過r。,練習2：如果n個非負整數m1,m2,…,mn的平均數小于r+1，即,則m1,m2,…,mn中至少有1個數不超過r。,鴿巢原理,例7. 一籃子水果裝有蘋果、香蕉和橘子。為了保證籃子內或者至少8個蘋果或者至少6個香蕉或者至少9個橘子，則放入籃子中的水果的最小件數是

32、多少？,例8. 兩個碟子，其中一個比另一個小，它們均被分成200個恒等的扇形。在大碟子中任選100個扇形并涂成紅色，而其余的100個扇形則涂成藍色。在小碟子中，每一個扇形或者涂成紅色，或者涂成藍色，所涂紅色和藍色扇形的數目沒有限制。然后將小蝶子放到大碟子上面是兩個碟子的中心重合。證明，能夠將兩個碟子的扇形對齊使得小碟子和大碟子上相同顏色重合的扇形數目至少是100個。,鴿巢原理,例8：證明每個由n2+1個實數構成的序列a1,a2,…,an

33、2+1或者含有長度為n+1的遞增子序列，或者含有長度為n+1的遞減子序列。證明：我們首先了解一下什么是子序列的概念。子序列：如果b1,b2,…bm是一個序列，那么，則是一個子序列，其中，1≤i1 ≤ i2 ≤… ≤ik ≤m。例如，b2,b4,b5是序列b1,b2,b3,b4,b5,b6的一個子序列，而b2,b6,b5則不是。遞增/減子序列：子序列 若滿足條件則稱為遞增子序列，而滿足

34、 則稱為遞減子序列。,鴿巢原理,我們假設不存在長度為n+1的遞增子序列，則需要證明必然存在長度為n+1的遞減子序列。對于每一個k=1,2,…,n2+1，令mk為從ak開始的最長遞增子序列長度。由于假設不存在長度為n+1的遞增子序列，則對每個k=1,2,…, n2+1，有1≤ mk≤n。 如果將m1,m2,…, mn2+1這n2+1個數作為物體，最長子序列的長度1,2,…,n作為n個盒子，其中，第

35、i個盒子代表長度為i的序列。根據鴿巢原理的加強形式，在m1,m2,…, mn2+1中有n+1個是相等的。令,其中，1≤k1<k2<…<kn+1。設對于某個i=1,2,…,n，有,于是，由于ki<ki+1，我們可以做成一個從,開始的最長,的遞增子序列并將,放到前面而得到一個從,開始,鴿巢原理,的遞增子序列。但這意味著,因此，我們斷言,由于這對每一個i=1,2,…,n均成立，因此我們有,從而我們斷言，,是一個長度為n

36、+1的,遞減子序列。,鴿巢原理,Ramsey定理Ramsey定理最容易理解的例子： 在6個(或更多的)人中，或者有3個人，他們中的每兩個人都相互認識；或者有3個人，他們中的每兩個人都相互不認識。 在給出這個證明以前，先給出一個抽象的公式：K6?K3,K3 (讀做K6箭指K3,K3)我們用K6代表6個物體(例如，6個人)和由它們配成的15對的集合。我們可以通過在平面上選出6個點來畫出K6，其中沒有3個點是共線的，然后，劃出連接每一

37、對點的連線或邊，這些邊代表這些點對。,鴿巢原理,,,,,,,K6,,,,,,K5,,,,,K4,,,,K3,,,K2,我們把邊涂成紅色表示認識，涂成藍色表示不認識。,,鴿巢原理,K6?K3,K3 (K6箭指K3,K3)含義：無論K6的邊用紅色和藍色如何去涂，總有一個紅K3(原始的6個點中有3個點，它們之間的3條線段均被著成紅色)或藍K3(原始的6個點中有3個點，它們之間的3條線段均被著成藍色)，簡而言之，總有一個單色的三角形。,,,,

38、,,,K6,,,,,,,著色方案1,著色方案2,,,,,,,,…,鴿巢原理,證明K6?K3,K3。證明：考慮K6的任意一點p，它接觸到5條邊，由于這5條邊的每一條都被涂成紅色或藍色，根據鴿巢原理的加強形式可知，這5條邊中或者至少有3條邊被涂成紅色，或者至少有3條邊被涂成藍色。我們設接觸到p點的5條邊有3條是紅色，令這三條邊分別與a、b、c三點相連?？紤]a、b、c兩兩相連的邊。1)如果這些邊都是藍色，那么a、b、c就確定了一個藍色的K

39、3。2)如果它們中的一條邊，比如連接a和c的邊是紅色的，那么p、a、c就確定一個紅K3。因此，我們得到：確實存在一個紅K3，或者是一個藍K3。,b,鴿巢原理,K5?K3,K3是否成立？,鴿巢原理,思考題：證明對10個頂點的完全圖用紅、藍兩色任意著色，證明，必然存在3個點使得連接該3點的3條線段都是紅色，或者必然存在4個點使得連接該4個點的6條線段都是藍色，即K9?K3,K4。將上面的10換成9是否成立？即K9?K3,K4？思考題：

40、證明對18個頂點的完全圖用紅、藍兩色任意著色。證明至少存在一個同色的完全四邊形，即K18?K4,K4。,鴿巢原理,定理5(Ramsey定理)： 給定m和n，存在一個正整數p，使得如果Kp的邊被涂成紅色或藍色，那么或者有一個紅色的Km，或者有一個藍色的Kn。無論Kp的邊如何著色，紅色Km或者藍色Kn的存在性是保證的。如果Kp?Km,Kn(m ≥2,n ≥2)，那么對任何的q≥p, 都有Kq?Km,Kn。 Ramsey數：Ramsey數

41、r(m,n)是使得Kp?Km,Kn成立的最小整數p。例如，r(3,3)=6，r(3,4)=9，r(4,4)=18。,鴿巢原理,推論4：證明r(2,n)=n；r(m,n)=r(n,m)。 證明：只需證明r(2,n)≤n以及r(2,n) >n-1。1)如果我們把Kn的邊或者涂成紅色或者涂成藍色，那么，或者Kn的某條邊是紅色的，因此我們得到了一個紅K2，或者Kn的所有邊都是藍色的，因此我們得到了一個藍Kn。即，Kn?K2,Kn，由于

42、r(2,n)是使得Kn?K2,Kn成立的最小整數，所以，r(2,n)≤n。2)如果我們將Kn-1的邊都涂成藍色，那么我們既得不到紅K2，也得不到藍Kn，所以，r(2,n)>n-1。,鴿巢原理,,m,n,常見的Ramsey數r(m,n),非平凡Ramsey數,平凡Ramsey數,Ramsey定理說明了對于任意m、n，r(m,n)都是存在的。雖然Ramsey定理說明了Ramsey數的存在性，但是對于Ramsey數的求法，目前還沒有非

43、平凡的結論，比如說r(3,10)、r(5,5)，現在還沒人知道它們的準確取值。,鴿巢原理,推論5：當m, n≥3時，r(m,n)≤r(m-1,n)+r(m,n-1)。證明：令N=r(m-1,n)+r(m,n-1)。對KN的邊采用紅、藍兩色進行任意著色。設p是KN的一個頂點，在KN中與p相連的邊有r(m-1, n)+r(m,n-1)-1條，這些邊要么為紅色，要么為藍色。根據鴿巢原理的加強形式，要么至少有r(m-1,n)條紅邊，要么至少有

44、r(m,n-1)條藍邊。1)對于至少有r(m-1,n)條紅邊的情形，以這些與p相連的紅邊除p以外的r(m-1,n)個頂點構成的完全圖Kr(m-1,n)中，或者有一個紅色Km-1，或者有一個藍色的Kn。如果有一個紅色的Km-1，則該紅色Km-1加上頂點p以及p與Km-1之間的紅邊，就構成一個紅色Km；否則，就有一個藍色的Kn。,鴿巢原理,2)對于至少有r(m,n-1)條藍邊的情形，以這些與p相連的藍邊除p以外的r(m,n-1)個頂點構成

45、的完全圖Kr(m,n-1)中，或者有一個紅色Km，或者有一個藍色的Kn-1。如果有一個藍色的Kn-1，則該藍色Kn-1加上頂點p以及p與Kn-1之間的藍邊，就構成一個藍色Kn；否則，就有一個紅色的Km。這說明KN?Km,Kn。由于r(m,n)是使得KN?Km,Kn成立的最小整數N，所以，r(m,n)≤KN=r(m-1,n)+r(m,n-1)。,鴿巢原理,Ramsey定理的推廣情況： 如果n1,n2和n3是大于或等于2的3個整數，則存在

46、一個整數p使得Kp?Kn1,Kn2,Kn3，也就是說，如果Kp的每條邊被涂上紅色或藍色或綠色，那么或者存在一個紅Kn1，或者存在一個藍Kn2，或者存在一個綠Kn3。Ramsey數的推廣情況：Ramsey數r(n1,n2,n3)是使得Kp?Kn1,Kn2,Kn3成立的最小整數p。Ramsey定理的任意推廣情況： Kp?Kn1,Kn2,Kn3,…,Kns。Ramsey數的任意推廣情況：r(n1,n2,…,ns)。,鴿巢原理,證明r(

47、3,3,3)≤17。證明：考慮用3種顏色進行著色的完全圖K17，設p是K17的一個頂點。由鴿巢原理可知，以p為端點連接其余16個頂點的16條線中必有6條顏色相同(比如都是紅色)?？疾爝@6條線的除p外的6個頂點所形成的完全圖K6。如果K6中有一條是紅色，則這條邊的兩個頂端加上p就形成了一個紅色三角形，結論成立。否則，K6中沒有一條紅色邊，則K6為用兩種顏色著色的完全圖，此時K6必含有一個同色的三角形。因此，K17中必含有一個同色的三角形

48、，從而r(3,3,3)≤17。,鴿巢原理,Ramsey定理的一般形式： 在這種形式中點對(兩個元素的子集)由t個元素的子集代替，其中t≥1為某個整數。令Knt表示n個元素的集合中所有的t個元素的子集的集合。定理6(Ramsey定理一般形式)： 給定整數t≥2及整數q1,q2,…,qk≥t，存在一個整數p使得Kpt?Kq1t,Kq2t,…,Kqkt，也就是說，存在一個整數p使得如果將p元素集合中的每一個t元素子集指定k種顏色c1,c2,

49、…,ck中的一種，那么或者存在q1個元素，這些元素的所有t元素子集都被指定顏色c1，或者存在q2個元素，這些元素的所有t元素子集都被指定顏色c2,…,或者存在qk個元素，這些元素的所有t元素子集都被指定顏色ck。Ramsey數的一般形式：滿足上述條件的最小整數p被稱為Ramsey數rt(qk,q1,q2,…,qk)。,鴿巢原理,r1(q1,q2,…,qk)=q1+q2+…+qk-q+1。設t=1，于是，r1(q1,q2,…,qk)就

50、是最小的數p，它滿足如果p個元素集合的元素用顏色c1,c2,…,ck中的一種顏色涂色，那么或者存在q1個涂成顏色c1的元素，或者存在q2個涂成顏色c2的元素，…，或者存在qk個涂成顏色ck的元素。因此，由鴿巢原理的加強形式，有r1(q1,q2,…,qk)=q1+q2+…+qk-q+1。這說明Ramsey定理是鴿巢原理的加強形式的推廣。,鴿巢原理,若令R(m)=r(3,3,…,3),目前已知R(1)=3, R(2)=6, R(3,3,3

51、)=17。,,m,思考題：證明R(m) ≤m[R(m-1)-1]+2。,主要內容,概述鴿巢原理 排列與組合 生成排列和組合二項式系數 容斥原理及應用 遞推關系和生成函數特殊計數序列 二分圖匹配Polya計數法,排列與組合,四個計數原理加法原理 集合劃分：令S為給定的非空集合，A={S1,S2,…,Sn}，若1)Si?S, Si≠?，i=1,2,…,n;2)Si∩Sj=?, i≠j, i,j=1,2,…,n；3

52、)S=S1∪S2 ∪…∪Sn.則稱A為集合S的劃分，其中Si(i=1,2,…,n)稱為該劃分的部分。例：對08級的研究生按照性別、年齡、專業(yè)進行劃分。,排列與組合,加法原理：設{S1,S2,…,Sn}為集合S的劃分，則S的元素的個數可以通過找出它的每一個部分的元素的個數來確定，我們把這些數相加，得到|S|=|S1|+|S2|+…+|Sn|。加法原理的另一表述方式：如果有p種方法能夠從一堆物品中選擇一個物品，而有q種方法也能夠從另一

53、堆物品中選擇一個物品，那么從這兩堆物品中選擇一個物品的方法共有p+q種。例：從ICES中心(9人)和信息安全中心(6人)選擇一名研究生的方法數是多少？,排列與組合,乘法原理：乘法原理：令S是元素的序偶(a,b)的集合，其中第一個元素a來自大小為p的一個集合，而對于a的每個選擇，元素b存在著q種選擇，于是，S的大小為p×q，即，|S|=p×q。 乘法原理的另一種表述方式：一項任務有p個結果，而不論第一項任務的結果

54、如何，第二項任務都有q個結果，那么，這兩項任務連續(xù)執(zhí)行就有p×q個結果。,1,2,a,b,,,S1,S2,1,a,1,b,2,a,2,b,,,,,c,1,c,,2,c,,,,排列與組合,乘法原理是加法原理的一個推論。令a1,a2,…,ap是對元素a的p個不同的選擇。我們將S劃分成部分S1,S2,…,Sp，其中Si是S內第一個元素為ai(i=1,2,…,p)的序偶的集合。每個Si的大小為q，因此由加法原理有|S|=|S1|+|S

55、2|+…+|Sp|=q+q+…+q=p×q。,1,a,1,b,2,a,2,b,,,,,1,c,,2,c,,集合1：第一個元素為1，集合大小為3,集合2：第一個元素為2，集合大小為3,,|S|=3+3=2×3=6,排列與組合,例：從ICES中心(9人)和信息安全中心(6人)各選擇一名研究生的方法數是多少？,1,2,a,b,,,ICES中心,c,3,4,5,6,7,8,9,e,f,g,i,j,信息安全中心,,|S|=|S

56、1|+|S2|+…+|S9|=8×9=72,排列與組合,思考題：從08級研究生選擇兩名屬于不同中心的學生方法數是多少？08級研究生情況：(1)ICES：9人；(2)信息安全：6人；(3)生物信息：4人；(4)嵌入式：2人；(5)醫(yī)學圖像：2人；(6)在職：1人。,排列與組合,減法原理：令A是一個集合，而U是包含A的更大的集合。設,是A在U中的補。那么A中的元素個數|A|由下列法則給出：,排列與組合,除法原理：令S是一

57、個有限集，它以下述方式方式被劃分成k部分，每一部分包含相同數目的元素。此時，劃分中的部分數目由下述公式給出：,排列與組合,例1：確定數34?52 ?117?138的正整數因子的個數？例2：兩位數字有多少兩個位互異且非零的兩位數？例3：計算口令字計劃由0,1,2,…,9和小寫字母a, b, c,…,z中取出的6個字符構成的一個串組成。具有重復字符的計算機口令共有多少？例4：在1000和9999之間有多少具有不同數字的奇數？例5：在

58、0和10000之間有多少個整數恰好有一位數字是5？,排列與組合,集合的排列S的r排列：令r為正整數，我們把n個元素的集合S的一個r排列定義為n個元素中的r個元素的有序擺放。例如，S={a, b, c}，則S的1排列為：,a,b,c,S的2排列為：,a,b,a,c,b,a,b,c,c,a,c,b,S的3排列為：,a,b,c,a,c,b,b,a,c,b,c,a,c,a,b,c,b,a,排列與組合,r-排列數目：我們用P(n,r)表示n個

59、元素集合的r-排列的數目。如果r>n，P(n,r)=0； 如果r=1，P(n,1)=n；定理1：對于正整數n和r，r≤n，有P(n,r)=n×(n-1)×…× (n-r+1)。,證明：在構建n-元素集的一個r排列時，我們可以用n種方法選擇第一項，不論第一項如何選出，都可以用n-1種方法選擇第二項，…，以及不論前r-1項如何選出，都可以用n-(r-1)種方法選擇第r項。根據乘法原理，這r項可以用n&#

60、215;(n-1)×… ×(n-r+1)種方法選出。,排列與組合,1,2,3,n,…,,,,…,第一項有n種方法,第二項有n-1種方法,1,2,r,第r項有n-r+1種方法,,,S,排列與組合,例：將08級的24個研究生排列使得ICES中心(9個學生)的任意兩個學生都不能相繼出現，這種排列的方法總數是多少？例：有多少種方法從08級的24個研究生中取7個人進行排列，并且使得王偉和謝冬輝不能以任何順序相繼出現？,排列與

61、組合,循環(huán)排列：例：6個孩子沿圓圈行進，他們能夠以多少種不同的方式形成一個圓？,1,2,3,4,5,6,6,1,2,3,4,5,5,6,1,2,3,4,4,5,6,1,2,3,3,4,5,6,1,2,2,3,4,5,6,1,123456,612345,561234,456123,345612,234561,排列與組合,如果兩個循環(huán)排列通過一個旋轉，即一個循環(huán)移位，從其中的一個變到另一個，那么可以將它們看成是相同的。這樣，在6個孩子的

62、線性排列和6個孩子的循環(huán)排列之間就存在著6到1的對應。因此，要想求得循環(huán)排列的數目，我們只要用6去除線性排列的數目即可。所以，6個孩子的循環(huán)排列數目等于6!/6=5!,排列與組合,定理2：n個元素的集合的循環(huán)r-排列的個數為,特別地，n個元素的循環(huán)排列的個數是(n-1)!。,證明：可以把線性r-排列的集合劃分成一些部分，使得兩個線性r-排列對應同一個循環(huán)r-排列當且僅當它們在同一個部分中。于是，循環(huán)r-排列的個數等于部分的個數。既然每一

63、個部分都含有r個線性r-排列，根據除法原理，部分的數目等于,排列與組合,例：ICES中心08級的9個研究生要圍坐一個圓桌，其中有兩個人不愿意彼此挨著就座，共有多少循環(huán)座位排放方法？例：6男6女圍坐一個圓桌，如果男女交替圍坐，可以有多少圍坐方式？,排列與組合,集合的組合S的r組合：令r為非負整數，我們把n個元素的集合S的r-組合可以定義為從S的n個元素中對r個元素的無序選擇。例如，S={a, b, c, d} 的3的組合為{a,

64、b, c}，{a, b, d}，{a, c, d}，{b, c, d}r-組合數目：我們用 表示n-元素集的r-組合的個數。如果r>n， =0；如果r>0， =0。,,n,0,=1,,n,1,=n,,n,n,=1,,0,0,=1,排列與組合,定理3：對于0≤r≤n，,因此，,證明：令S是一個n-元素集。S的每個r-排列都是由下面的兩個任務執(zhí)行結果產生。1)從S中選出r個元素。2

65、)將所選出的r個元素以某種順序排列。執(zhí)行第一個任務的方法數根據定義可知為組合數 。,排列與組合,執(zhí)行第二個任務的方法數則是P(r,r)=r!。 根據乘法原理我們有,所以，,排列與組合,定理4：,證明：通過對n-元素集S的組合計數來證明。1)S的每一個組合是S對于r(r=0,1,2,…,n)的一個r-組合。由于,等于S的r-組合數，由加法原理,等于S的所有組合的總個數。,排列與組合,2)把一個組合的選取分成n個任務來完成

66、。令S的元素為x1,x2,…,xn。在選擇S的一個組合時，對n個元素的每一個都有兩種選擇：xi(i=1,2,…,n)要么在這個組合里； xi(i=1,2,…,n)要么不在這個組合里。因此，由乘法原理，存在2n種方法使得我們可以形成S的一個組合。使兩種方法相等就完成了定理的證明。,排列與組合,多重集排列多重集多重集同一般集合一樣，是一組對象的整體，只不過不像一般集合那樣必須要求集合中的每個元素互不相同。例如，S={a,a,a,b,c

67、,c,d,d,d,d,d}是一個10元素的多重集，其中，有3個a，1個b，2個c和4個d。我們可以將S表示為S={3?a,1?b,2?c,4?d}。一般地，多重集可以表示為S={k1?a1,k2?a2,…,kn?an}，其中，a1,a2,…,an為S中所有的互不相同的元素，S中有ki個ai(1≤i ≤n)，稱ki為ai的重數，ki是正整數，也可以是∞，表示S中有無限多個ai。,排列與組合,多重集排列設S={3?a,1?b,2?c,

68、4?d} ，那么acbc，cbcc為S的4排列，而abaacddcdd是S的一個排列(10排列)。定理：令S={∞?a1,∞?a2,…,∞?ak}是一個多重集，則S的r-排列的個數為kr。證明：,,,,…,第一項有k種方法,第二項有k種方法,1,2,r,第r項有k種方法,,,S,所以，S的r-排列個數為kr,排列與組合,該問題是求S={∞?a,∞?b,…,∞?z}的包含4個元音字母的8-排列數。在長度為8的字符串中，4個元音字母出現

69、的位置的選擇方式有 種，而每個元音位置可以取5個元音字母中的任何一個，4個輔音位置可以取21個輔音字母中的任何一個。因此，滿足要求的字符串有,?54?214個。,例：用26個英文字母可以構造出多少個包含4個元音字母、長度為8的字符串。,排列與組合,例：把r個不同的球放入k個不同的盒子中，每個盒子可以放多個，也可以不放，其方案數為多少？ 方法1：第一個球有k個盒子可放，第二個球有k個盒子可放，…，第r個球也有k個盒子