版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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è)盒子
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 組合數(shù)學(xué)講義
- 組合數(shù)學(xué)
- 哈工大matlab講義第三講
- 組合數(shù)學(xué)答案
- 組合數(shù)學(xué)3
- 組合數(shù)學(xué)2
- 組合數(shù)學(xué)7
- acm之組合數(shù)學(xué)
- 馮榮權(quán) 組合數(shù)學(xué)
- 組合數(shù)學(xué)課后答案
- 組合數(shù)學(xué)題庫(kù)答案
- 組合數(shù)學(xué)鴿巢原理
- 組合數(shù)學(xué)第二講
- acm組合數(shù)學(xué)知識(shí)
- 理論力學(xué)復(fù)習(xí)題哈工大版
- 組合數(shù)學(xué)第二章
- 組合數(shù)學(xué)習(xí)題解答
- chap1組合數(shù)學(xué)
- 組合數(shù)學(xué)第五章
- 推薦理論力學(xué)哈工大版課后習(xí)題答案
評(píng)論
0/150
提交評(píng)論