哈工大-組合數(shù)學(xué)講義2010版-新

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

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

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

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

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

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

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

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

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

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

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

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

13、間的函數(shù)(function，或說(shuō)映射mapping)：設(shè)X和Y是任意兩個(gè)集合，而f 是X到Y(jié)的一個(gè)關(guān)系，如果對(duì)于每一個(gè)x?X,有唯一的y?Y，使得?f，稱關(guān)系f 為函數(shù)，記作f : X?Y或 X ? Y。原象和象：如果?f，則x稱為自變?cè)ㄔ螅?，y稱為在f 作用下x的象(image)，?f 亦可記作y=f(x)，且記f(X)={ f(x)| x?X} 。,鴿巢原理,函數(shù)基本知識(shí)定義域：函數(shù)f : X?Y的定義域(domain) d

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

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

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

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

18、看成是物體，余數(shù)看成是盒子，根據(jù)鴿巢原理，那么必有兩個(gè)和除以m有相同的余數(shù)。因此，存在整數(shù)k和l，k<l，使得a1+a2+...+ak和a1+a2+...+al除以m有相同的余數(shù)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：一位國(guó)際象棋大師有11周的時(shí)間備戰(zhàn)一場(chǎng)錦標(biāo)賽，他

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

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

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

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

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

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

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

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

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

28、-1)+…+(qn-1)=q1+q2+…+qn-n這與物體的總數(shù)為q1+q2+…+qn-n+1相矛盾，所以或者第一個(gè)盒子至少含有q1個(gè)物體，或者第二個(gè)盒子至少含有q2個(gè)物體,…,或者第n個(gè)盒子至少含有qn個(gè)物體。,鴿巢原理,鴿巢原理的簡(jiǎn)單形式是其加強(qiáng)形式通過(guò)q1=q2=…=qn=2來(lái)實(shí)現(xiàn)的。這時(shí)， 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個(gè)物體，n個(gè)盒子，則至少有一個(gè)盒子里有不少于[(m-1)/n]+1個(gè)物體。,證明：采用反證法，設(shè)所有盒子了最多有[(m-1)/n]個(gè)物體，則n個(gè)盒子中的物體數(shù)最多為n[(m-1)/n] ≤m-1，與假設(shè)矛盾。,推論2：若取n(m-1)+1個(gè)物體放入n個(gè)盒子中，則至少有1個(gè)盒子有m個(gè)物體。,這個(gè)推論相當(dāng)于q1=q2=…=qn=m時(shí)的特殊情況。,采用著

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

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

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

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

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

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

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

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

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

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

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

41、r(m,n)是使得Kp?Km,Kn成立的最小整數(shù)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的邊或者涂成紅色或者涂成藍(lán)色，那么，或者Kn的某條邊是紅色的，因此我們得到了一個(gè)紅K2，或者Kn的所有邊都是藍(lán)色的，因此我們得到了一個(gè)藍(lán)Kn。即，Kn?K2,Kn，由于

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

43、平凡的結(jié)論，比如說(shuō)r(3,10)、r(5,5)，現(xiàn)在還沒(méi)人知道它們的準(zhǔn)確取值。,鴿巢原理,推論5：當(dāng)m, n≥3時(shí)，r(m,n)≤r(m-1,n)+r(m,n-1)。證明：令N=r(m-1,n)+r(m,n-1)。對(duì)KN的邊采用紅、藍(lán)兩色進(jìn)行任意著色。設(shè)p是KN的一個(gè)頂點(diǎn)，在KN中與p相連的邊有r(m-1, n)+r(m,n-1)-1條，這些邊要么為紅色，要么為藍(lán)色。根據(jù)鴿巢原理的加強(qiáng)形式，要么至少有r(m-1,n)條紅邊，要么至少有

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

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

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

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

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

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

50、是最小的數(shù)p，它滿足如果p個(gè)元素集合的元素用顏色c1,c2,…,ck中的一種顏色涂色，那么或者存在q1個(gè)涂成顏色c1的元素，或者存在q2個(gè)涂成顏色c2的元素，…，或者存在qk個(gè)涂成顏色ck的元素。因此，由鴿巢原理的加強(qiáng)形式，有r1(q1,q2,…,qk)=q1+q2+…+qk-q+1。這說(shuō)明Ramsey定理是鴿巢原理的加強(qiáng)形式的推廣。,鴿巢原理,若令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。,主要內(nèi)容,概述鴿巢原理 排列與組合 生成排列和組合二項(xiàng)式系數(shù) 容斥原理及應(yīng)用 遞推關(guān)系和生成函數(shù)特殊計(jì)數(shù)序列 二分圖匹配Polya計(jì)數(shù)法,排列與組合,四個(gè)計(jì)數(shù)原理加法原理 集合劃分：令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)稱為該劃分的部分。例：對(duì)08級(jí)的研究生按照性別、年齡、專業(yè)進(jìn)行劃分。,排列與組合,加法原理：設(shè){S1,S2,…,Sn}為集合S的劃分，則S的元素的個(gè)數(shù)可以通過(guò)找出它的每一個(gè)部分的元素的個(gè)數(shù)來(lái)確定，我們把這些數(shù)相加，得到|S|=|S1|+|S2|+…+|Sn|。加法原理的另一表述方式：如果有p種方法能夠從一堆物品中選擇一個(gè)物品，而有q種方法也能夠從另一

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

54、如何，第二項(xiàng)任務(wù)都有q個(gè)結(jié)果，那么，這兩項(xiàng)任務(wù)連續(xù)執(zhí)行就有p×q個(gè)結(jié)果。,1,2,a,b,,,S1,S2,1,a,1,b,2,a,2,b,,,,,c,1,c,,2,c,,,,排列與組合,乘法原理是加法原理的一個(gè)推論。令a1,a2,…,ap是對(duì)元素a的p個(gè)不同的選擇。我們將S劃分成部分S1,S2,…,Sp，其中Si是S內(nèi)第一個(gè)元素為ai(i=1,2,…,p)的序偶的集合。每個(gè)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：第一個(gè)元素為1，集合大小為3,集合2：第一個(gè)元素為2，集合大小為3,,|S|=3+3=2×3=6,排列與組合,例：從ICES中心(9人)和信息安全中心(6人)各選擇一名研究生的方法數(shù)是多少？,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級(jí)研究生選擇兩名屬于不同中心的學(xué)生方法數(shù)是多少？08級(jí)研究生情況：(1)ICES：9人；(2)信息安全：6人；(3)生物信息：4人；(4)嵌入式：2人；(5)醫(yī)學(xué)圖像：2人；(6)在職：1人。,排列與組合,減法原理：令A(yù)是一個(gè)集合，而U是包含A的更大的集合。設(shè),是A在U中的補(bǔ)。那么A中的元素個(gè)數(shù)|A|由下列法則給出：,排列與組合,除法原理：令S是一

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

58、0和10000之間有多少個(gè)整數(shù)恰好有一位數(shù)字是5？,排列與組合,集合的排列S的r排列：令r為正整數(shù)，我們把n個(gè)元素的集合S的一個(gè)r排列定義為n個(gè)元素中的r個(gè)元素的有序擺放。例如，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-排列數(shù)目：我們用P(n,r)表示n個(gè)

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

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

61、組合,循環(huán)排列：例：6個(gè)孩子沿圓圈行進(jìn)，他們能夠以多少種不同的方式形成一個(gè)圓？,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,排列與組合,如果兩個(gè)循環(huán)排列通過(guò)一個(gè)旋轉(zhuǎn)，即一個(gè)循環(huán)移位，從其中的一個(gè)變到另一個(gè)，那么可以將它們看成是相同的。這樣，在6個(gè)孩子的

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

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

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

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

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

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

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

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