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

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

2、系和生成函數(shù)遞推關(guān)系和生成函數(shù)n特殊計數(shù)序列特殊計數(shù)序列n二分圖中的匹配二分圖中的匹配 nPolya計數(shù)法計數(shù)法 4概述概述n數(shù)學(xué)研究問題數(shù)學(xué)研究問題研究連續(xù)對象研究連續(xù)對象(微積分微積分)研究離散對象研究離散對象(組合數(shù)學(xué)組合數(shù)學(xué))n組合數(shù)學(xué)研究的問題組合數(shù)學(xué)研究的問題將一個集合的物體排列成滿足一些指定規(guī)則的格式，將一個集合的物體排列成滿足一些指定規(guī)則的格式，如下兩類問題反復(fù)出現(xiàn)：如下兩類問題反復(fù)出現(xiàn)：排列存在性：排列存在性：如果想要排列一個集合的成員使得某如果想要排列一個集合的成員使得某些條件得以滿足，并且這種排列不總是可能的，那些條件得以滿足，并且這種排列不總是可能的，那么這種排列在什么

3、樣的條件下滿足。么這種排列在什么樣的條件下滿足。排列的計數(shù)和分類：排列的計數(shù)和分類：如果一個指定的排列是可能的，如果一個指定的排列是可能的，那么會有多少種方法去實現(xiàn)它。此時，人們就可以那么會有多少種方法去實現(xiàn)它。此時，人們就可以計數(shù)并將它們分類。計數(shù)并將它們分類。5概述概述棋盤的完美覆蓋：棋盤的完美覆蓋：考慮一張考慮一張8 8(8行行8列列)的的64個正方形的國際象棋個正方形的國際象棋棋盤，設(shè)有形狀一樣的多米諾牌，每張牌恰好覆蓋棋盤上相鄰的兩個棋盤，設(shè)有形狀一樣的多米諾牌，每張牌恰好覆蓋棋盤上相鄰的兩個方格，那么，是否能夠把方格，那么，是否能夠把32張多米諾牌擺放到棋盤上，使得任何兩張張多米諾

4、牌擺放到棋盤上，使得任何兩張多米諾牌均不重疊，每張多米諾牌覆蓋兩個方格，并且棋盤上的所有多米諾牌均不重疊，每張多米諾牌覆蓋兩個方格，并且棋盤上的所有方格都被覆蓋住？我們把這樣一種排列稱為棋盤的多米諾牌的完美覆方格都被覆蓋?。课覀儼堰@樣一種排列稱為棋盤的多米諾牌的完美覆蓋。蓋。8 8棋盤棋盤完美覆蓋完美覆蓋1完美覆蓋完美覆蓋2完美覆蓋數(shù)：完美覆蓋數(shù)：12988816=24 (901)2)6概述概述與上述問題同時出現(xiàn)的另外兩種組合數(shù)學(xué)問題：與上述問題同時出現(xiàn)的另外兩種組合數(shù)學(xué)問題：研究一個已知的排列：研究一個已知的排列：當人們建立起滿足某些指定當人們建立起滿足某些指定條件的一個排列以后，可能要考察

5、這個排列的性質(zhì)條件的一個排列以后，可能要考察這個排列的性質(zhì)和結(jié)構(gòu)，這樣的結(jié)構(gòu)可能會涉及到分類問題。和結(jié)構(gòu)，這樣的結(jié)構(gòu)可能會涉及到分類問題。構(gòu)造一個最優(yōu)的排列：構(gòu)造一個最優(yōu)的排列：如果可能存在多于一個的排如果可能存在多于一個的排列，人們也許想要確定滿足某些優(yōu)化準則的一個排列，人們也許想要確定滿足某些優(yōu)化準則的一個排列，即找出某種規(guī)定意義下的列，即找出某種規(guī)定意義下的“最好的最好的”或或“最優(yōu)最優(yōu)的的”排列。排列。7概述概述例，設(shè)例，設(shè)S=1,2,3,4為一個集合為一個集合 1)從從S中取兩個不相同的元素進行排列，這樣的排列有多少種中取兩個不相同的元素進行排列，這樣的排列有多少種2)列出所有可能的

6、排列。列出所有可能的排列。3)求出兩個元素之和最大的排列。求出兩個元素之和最大的排列。組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計數(shù)、組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計數(shù)、分析和優(yōu)化等問題的一門科學(xué)。分析和優(yōu)化等問題的一門科學(xué)。8概述概述問題問題1. 如果將棋盤變?yōu)槿绻麑⑵灞P變?yōu)?m n (m行行n列列)，則完美覆蓋是否，則完美覆蓋是否存在？存在？問題問題2. 對于什么樣的對于什么樣的m和和n存在完美覆蓋？存在完美覆蓋？當且僅當當且僅當m和和n中至少有一個是偶數(shù)時，中至少有一個是偶數(shù)時，m n 棋盤存在棋盤存在完美覆蓋。完美覆蓋。不一定存在，不一定存在，例如，例如，3行行3列的棋盤就不存在完美覆蓋。列的棋盤

7、就不存在完美覆蓋。9概述概述問題問題3. 8 8的棋盤用一把剪刀剪掉棋盤一副對角上的兩個的棋盤用一把剪刀剪掉棋盤一副對角上的兩個方格，總共剩下方格，總共剩下62個方格，那么是否能夠排列個方格，那么是否能夠排列31張多米張多米諾牌來得出對這幅被剪過棋盤的完美覆蓋？諾牌來得出對這幅被剪過棋盤的完美覆蓋？不存在完美覆蓋。不存在完美覆蓋。在一副在一副8 8棋盤上交替地將方格涂成黑色和白色，則其棋盤上交替地將方格涂成黑色和白色，則其中的中的32個方格是黑色，個方格是黑色，32個方格是白色。個方格是白色。如果我們剪掉棋盤一副對角線上的兩個方格，那么我們?nèi)绻覀兗舻羝灞P一副對角線上的兩個方格，那么我們就剪掉

8、同樣種顏色的兩個方格，比如兩個白色方格。這就剪掉同樣種顏色的兩個方格，比如兩個白色方格。這就變成了就變成了32個黑方格和個黑方格和30個白方格。個白方格。但是，每張多米諾牌需要一個白方格和一個黑方格，于但是，每張多米諾牌需要一個白方格和一個黑方格，于是，是，31張不重疊的多米諾牌則覆蓋住張不重疊的多米諾牌則覆蓋住31個黑方格和個黑方格和31個個白方格。因此，這幅被剪過的棋盤不存在完美覆蓋。白方格。因此，這幅被剪過的棋盤不存在完美覆蓋。10概述概述問題問題4. 將將m n的棋盤上的方格交替涂成黑色和白色，切的棋盤上的方格交替涂成黑色和白色，切除一些方格，得到一塊被剪過的棋盤，這塊棋盤什么時除一些

9、方格，得到一塊被剪過的棋盤，這塊棋盤什么時候有一個完美覆蓋？候有一個完美覆蓋？必要條件。這塊被剪過的棋盤必須具有相等的黑方格數(shù)必要條件。這塊被剪過的棋盤必須具有相等的黑方格數(shù)和白方格數(shù)。和白方格數(shù)。該條件不是充分條件。該條件不是充分條件。 4 5棋盤棋盤 11概述概述nB-牌：牌：設(shè)設(shè)b是一個正整數(shù)，我們用是一個正整數(shù)，我們用b個個1 1的方格并排連的方格并排連接成的接成的1 b的方格條來代替多米諾牌，這些方方格條稱為的方格條來代替多米諾牌，這些方方格條稱為b-牌。牌。一張一張5-5-牌牌一張一張2-2-牌牌（多米諾牌）（多米諾牌）nm n棋盤被棋盤被B-牌的完美覆蓋：牌的完美覆蓋：b-牌在牌

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

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

12、及應(yīng)用 n遞推關(guān)系和生成函數(shù)遞推關(guān)系和生成函數(shù)n特殊計數(shù)序列特殊計數(shù)序列 n二分圖匹配二分圖匹配nPolya計數(shù)法計數(shù)法 15鴿巢原理鴿巢原理n鴿巢原理：簡單形式鴿巢原理：簡單形式定理定理1. 如果如果n+1個物體被放進個物體被放進n個盒子中，那么至少有一個盒個盒子中，那么至少有一個盒子包含兩只或更多的物體。子包含兩只或更多的物體。其它表述形式：其它表述形式：如果如果n+1只鴿子被放進只鴿子被放進n個鴿巢中，那么至少有一個鴿巢包含個鴿巢中，那么至少有一個鴿巢包含兩只或更多的鴿子。兩只或更多的鴿子。如果如果n+1個物體用種顏色涂色，那么必然有兩個物體被涂成相個物體用種顏色涂色，那么必然有兩個物體

13、被涂成相同的顏色。同的顏色。16鴿巢原理鴿巢原理4個物體個物體3個盒子個盒子存放存放1234517鴿巢原理鴿巢原理p例題：例題：例例1：在在13個人中存在兩個人，他們的生日在同一個月份里個人中存在兩個人，他們的生日在同一個月份里?？紤]12個盒子，每個盒子對應(yīng)一個月份，將13個人放到12個盒子中，則至少有一個盒子包含兩個或兩個以上的人，即，這在13個人中存在兩個人，他們的生日在同一個月份里。例例2：設(shè)有設(shè)有n對已婚夫婦。為保證能夠有一對夫婦被選出，至對已婚夫婦。為保證能夠有一對夫婦被選出，至少要從這少要從這2n個人中選出多少人。個人中選出多少人。應(yīng)至少選擇n+1個人?？紤]n個盒子，每個盒子對應(yīng)一

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

15、一個物體。19鴿巢原理鴿巢原理p函數(shù)基本知識函數(shù)基本知識函數(shù)：函數(shù)：集合之間的函數(shù)集合之間的函數(shù)(function，或說映射，或說映射mapping)：設(shè)：設(shè)X和和Y是任意兩個集合，而是任意兩個集合，而f 是是X到到Y(jié)的一個關(guān)系，如果對于每一個的一個關(guān)系，如果對于每一個x X,有唯一的有唯一的y Y，使得，使得 f，稱關(guān)系，稱關(guān)系f 為函數(shù)，記作為函數(shù)，記作f : XY或或 X Y。原象和象：原象和象：如果如果 f，則則x稱為自變元（原象），稱為自變元（原象），y稱為在稱為在f 作用下作用下x的象的象(image)， f 亦可記作亦可記作y=f(x)，且記，且記f(X)= f(x)| x X

16、。20鴿巢原理鴿巢原理p函數(shù)基本知識函數(shù)基本知識定義域：定義域：函數(shù)函數(shù)f : XY的定義域的定義域(domain) dom f 定義為：定義為： dom f = x | 存在某個存在某個y Y使得使得 f =X 。值域：值域：函數(shù)函數(shù)f : XY的值域的值域(range) ran f 定義為：定義為： ran f = y | ( x)(x X) f Y。全函數(shù)：全函數(shù)：f 是全函數(shù)是全函數(shù)(total function)若若dom f=X， f 是全函數(shù)是全函數(shù),否則稱否則稱f是偏函數(shù)是偏函數(shù)(partial function)。21鴿巢原理鴿巢原理p函數(shù)基本知識函數(shù)基本知識滿射：滿射： f

17、 是滿射是滿射( surjection, 或說或說f maps X onto Y )如果如果ran f = Y，即對任意的，即對任意的y Y都有原像。都有原像。設(shè)設(shè)f : XY是滿射，即對任意的是滿射，即對任意的y Y，必存在，必存在x X，使得，使得f(x) = y成立。成立。入射：入射：f 是入射是入射(injection，或說，或說f is one to one 是一對一是一對一)設(shè)設(shè)f : XY是入射，即對任意的是入射，即對任意的x1, x2 X，如果，如果f (x1) = f (x2), 則則x1 = x2，或者，或者 如果如果x1x2，則得，則得f (x1) f (x2)。22鴿巢

18、原理鴿巢原理p從函數(shù)角度來分析鴿巢原理的含義從函數(shù)角度來分析鴿巢原理的含義設(shè)設(shè)X和和Y是兩個有限集，并令是兩個有限集，并令f :XY是一個從是一個從X到到Y(jié)的函數(shù)。的函數(shù)。如果如果X的元素多于的元素多于Y的元素，那么的元素，那么f 就不是一對一的。就不是一對一的。如果如果X和和Y含有相同個數(shù)的元素，并且含有相同個數(shù)的元素，并且f 是映上是映上(onto)的，那么的，那么f 就是一對一的。就是一對一的。如果如果X和和Y含有相同個數(shù)的元素，并且含有相同個數(shù)的元素，并且f是一對一的，那么是一對一的，那么f 就就是映上的。是映上的。23鴿巢原理鴿巢原理例例3：給定給定m個整數(shù)個整數(shù)a1,a2,am,存

19、在整數(shù)存在整數(shù)k和和l，0klm， 使使得得ak+1,ak+2,al能夠被能夠被m整除。也就是說，在序列整除。也就是說，在序列a1,a2,am中中存在連續(xù)個元素，它們的和能被存在連續(xù)個元素，它們的和能被m整除。整除?？紤]m個和：a1,a1+a2,a1+a2+a3,a1+a2+a3+.+am如果這些和中存在一個可以被m整除，那么結(jié)論就成立。否則，這些和中的任意一個都不能被m整除，即，這些和中的每一個除以m都有一個非零余數(shù)，余數(shù)等于1,2,m-1。由于m個和而只有m-1個余數(shù)，如果我們將和看成是物體，余數(shù)看成是盒子，根據(jù)鴿巢原理，那么必有兩個和除以m有相同的余數(shù)。因此，存在整數(shù)k和l，kl，使得a

20、1+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整除。24鴿巢原理鴿巢原理例例4：一位國際象棋大師有一位國際象棋大師有11周的時間備戰(zhàn)一場錦標賽，他決周的時間備戰(zhàn)一場錦標賽，他決定每天至少下一盤棋，但是為了使自己不過分疲勞他還決定在定每天至少下一盤棋，但是為了使自己不過分疲勞他還決定在每周不能下棋超過每周不能下棋超過12盤。證明存在連續(xù)若干天，期間這位大師盤。證明存在連續(xù)若干天，期間這位大師恰好下了恰好下了21盤棋。盤棋。

21、一共備戰(zhàn)117=77天。令x1,x2,x77分別為第1,2,77天下的棋數(shù)，則xi1(i=1,2,77)。我們構(gòu)造如下嚴格遞增序列：a1=x1, a2=x1+x2, a3=x1+x2+x3,a77=x1+x2+x3+x77，其中，ai表示前i (i=1,2,77)天下棋的總數(shù)，并且1a1a2a3,a77 1112=132 。則序列a1+21, a2+21,a3+21,a77+21 也是一個嚴格遞增序列，并且22a1+21a2+21a3+21,a77+21 153 。25鴿巢原理鴿巢原理于是，這154個數(shù)：a1,a2,a77,a1+21,a2+21,a77+21中的每一個都是1到153中的一個整

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

23、數(shù)分解知識：任何一個整數(shù)都可以寫成2ka的形式，其中，k0，a為奇數(shù)。對于1,2,3,200之間的一個整數(shù)，a是100個數(shù)1,3,199中的一個。因此，如果我們將所選擇的101個數(shù)作為物體，1,3,199這100個奇數(shù)作為盒子，根據(jù)鴿巢原則，在這101中存在兩個整數(shù)，當寫成上述形式時這兩個數(shù)具有相同的a值。令這兩個數(shù)是2ra和2sa。如果rs，那么第二個數(shù)就能被第一個數(shù)整除。27鴿巢原理鴿巢原理例例6(中國乘余定理中國乘余定理)：令令m和和n是兩個互素的整數(shù)，并令是兩個互素的整數(shù)，并令a和和b為兩個整數(shù)，且為兩個整數(shù)，且0am-1以及以及0bn-1 。于是存在一個整數(shù)。于是存在一個整數(shù)x，使得

24、使得x除以除以m的余數(shù)為的余數(shù)為a，并且，并且x除以除以n的余數(shù)為的余數(shù)為b，即，即，x既可以既可以寫成寫成x=pm+a的同時又可以寫成的同時又可以寫成x=qn+b的形式，在這里，的形式，在這里，p和和q為兩個整數(shù)。為兩個整數(shù)。素數(shù)定義：素數(shù)定義：如果兩個整數(shù)m和n的最大公約數(shù)為1，我們稱m和n為互素。為了證明這個結(jié)論，我們需要構(gòu)造出x，那么如何構(gòu)造？我們首先按照x=pm+a的形式構(gòu)造x(p取0,1,n-1)，考慮如下n個整數(shù)：a, m+a, 2m+a, (n-1)m+a。這些整數(shù)中的每個除以m的余數(shù)都為a，即x可以寫成pm+a的形式。如果我們能夠證明a, m+a, 2m+a, (n-1)m+

25、a這n個數(shù)中存在一個數(shù)能夠?qū)懗蓂n+b的形式，則即可證明本題結(jié)論。28鴿巢原理鴿巢原理如果a, m+a, 2m+a, (n-1)m+a中的每個數(shù)除以n的余數(shù)都不相等，則我們將這n個數(shù)作為物體，n的余數(shù)0,1,2,n-1作為盒子，根據(jù)鴿巢原理(定理3)， 0,1,2,n-1中的每個數(shù)作為余數(shù)都會出現(xiàn)，特別是數(shù)b作為余數(shù)也會出現(xiàn)。令p為整數(shù)，滿足0 p n-1，且使數(shù)x=pm+a除以n的余數(shù)為b，則對某個適當?shù)膓，有x=qn+b，因此，x=pm+a且x=qn+b，從而x具有所要求的性質(zhì)。否則，如果這n個數(shù)存在兩個數(shù)除以n有相同的余數(shù)r，我們令這兩個數(shù)分別為im+a和jm+a，其中，0ijn-1，因

26、此，存在兩個整數(shù)qi和qj，使得29鴿巢原理鴿巢原理im+a=qin+r, jm+a=qjn+r，用第二個方程減去第一個方程，得到(j-i)m=(qj-qi)n，這說明n是(j-i)m的一個因子。由于n與m沒有除了1之外的公因子，因此n是j-i的一個因子，然而， 0j-in-1，也就是說，n不可能是j-i的一個因子。這個矛盾產(chǎn)生于我們假設(shè)a, m+a, 2m+a, (n-1)m+a中有兩個除以n會有相同的余數(shù)。因此，我們斷言，這n個數(shù)中的每一個除以n都會有不同的余數(shù)，這樣根據(jù)前述結(jié)論即可證明本題正確性。30鴿巢原理鴿巢原理n鴿巢原理：加強形式鴿巢原理：加強形式定理定理4. 令令q1,q2,qn

27、為為n個正整數(shù)。如果將個正整數(shù)。如果將q1+q2+qn-n+1個物體放入個物體放入n個盒子內(nèi)，那么，或者第一個盒子至少含有個盒子內(nèi)，那么，或者第一個盒子至少含有q1個物個物體，或者第二個盒子至少含有體，或者第二個盒子至少含有q2個物體個物體,或者第或者第n個盒子至少個盒子至少含有含有qn個物體。個物體。 證明：證明：采用反證法，設(shè)將q1+q2+qn-n+1個物體放入到n個盒子中，如果對于每個i=1,2,n，第i個盒子含有少于qi個物體，那么所有盒子中的物體總數(shù)不超過(q1-1)+(q2-1)+(qn-1)=q1+q2+qn-n這與物體的總數(shù)為q1+q2+qn-n+1相矛盾，所以或者第一個盒子至

28、少含有q1個物體，或者第二個盒子至少含有q2個物體,或者第n個盒子至少含有qn個物體。 31鴿巢原理鴿巢原理鴿巢原理的簡單形式是其加強形式通過鴿巢原理的簡單形式是其加強形式通過q1=q2=qn=2來實現(xiàn)來實現(xiàn)的。這時，的。這時， q1+q2+qn-n+1=2n-n+1=n+1。q1=2q2=3q3=4q1+q2+q3-3+1=7b12或或或或b1b2b3b13b1432鴿巢原理鴿巢原理推論推論1. m個物體，個物體，n個盒子，則至少有一個盒子里有不少于個盒子，則至少有一個盒子里有不少于(m-1)/n+1個物體。個物體。 證明：證明：采用反證法，設(shè)所有盒子了最多有(m-1)/n個物體，則n個盒子

29、中的物體數(shù)最多為n(m-1)/n m-1，與假設(shè)矛盾。推論推論2：若取若取n(m-1)+1個物體放入個物體放入n個盒子中，則至少有個盒子中，則至少有1個個盒子有盒子有m個物體。個物體。 這個推論相當于q1=q2=qn=m時的特殊情況。采用著色的術(shù)語來表述：采用著色的術(shù)語來表述：如果如果q1+q2+qn-n+1個物體中的每個物體中的每一個物體被指定用一個物體被指定用n種顏色中的一種著色，那么，存在這樣一個種顏色中的一種著色，那么，存在這樣一個i，使得第，使得第i種顏色的物體至少有種顏色的物體至少有qi個。個。33鴿巢原理鴿巢原理推論推論3：若m1,m2,mn是n個正整數(shù)，而且1.21rnmmmn

30、則m1,m2,mn中至少有1個數(shù)不小于r。證明證明：將該問題與推論2建立聯(lián)系。取n(r-1)+1個物體放入n個盒子中，設(shè)mi (i=1,2,n)是第i個盒子中的物體個數(shù)，于是，這n個數(shù)m1,m2,mn的平均數(shù)為11) 1(1) 1(.21rnrnrnnmmmn由于這個平均數(shù)大于r-1，故而有一個整數(shù)mi至少是r。34鴿巢原理鴿巢原理練習(xí)練習(xí)1：如果n個非負整數(shù)m1,m2,mn的平均數(shù)小于r+1，即1.21rnmmmn則m1,m2,mn中至少有1個數(shù)不超過r。練習(xí)練習(xí)2：如果n個非負整數(shù)m1,m2,mn的平均數(shù)小于r+1，即1.21rnmmmn則m1,m2,mn中至少有1個數(shù)不超過r。35鴿巢原

31、理鴿巢原理例例7. 一籃子水果裝有蘋果、香蕉和橘子。為了保證籃子內(nèi)或一籃子水果裝有蘋果、香蕉和橘子。為了保證籃子內(nèi)或者至少者至少8個蘋果或者至少個蘋果或者至少6個香蕉或者至少個香蕉或者至少9個橘子，則放入籃個橘子，則放入籃子中的水果的最小件數(shù)是多少？子中的水果的最小件數(shù)是多少？例例8. 兩個碟子，其中一個比另一個小，它們均被分成兩個碟子，其中一個比另一個小，它們均被分成200個恒個恒等的扇形。在大碟子中任選等的扇形。在大碟子中任選100個扇形并涂成紅色，而其余的個扇形并涂成紅色，而其余的100個扇形則涂成藍色。在小碟子中，每一個扇形或者涂成紅個扇形則涂成藍色。在小碟子中，每一個扇形或者涂成紅色

32、，或者涂成藍色，所涂紅色和藍色扇形的數(shù)目沒有限制。然色，或者涂成藍色，所涂紅色和藍色扇形的數(shù)目沒有限制。然后將小蝶子放到大碟子上面是兩個碟子的中心重合。證明，能后將小蝶子放到大碟子上面是兩個碟子的中心重合。證明，能夠?qū)蓚€碟子的扇形對齊使得小碟子和大碟子上相同顏色重合夠?qū)蓚€碟子的扇形對齊使得小碟子和大碟子上相同顏色重合的扇形數(shù)目至少是的扇形數(shù)目至少是100個。個。36鴿巢原理鴿巢原理kiiibbb,.,21kiiibbb.21例例8：證明每個由證明每個由n2+1個實數(shù)構(gòu)成的序列個實數(shù)構(gòu)成的序列a1,a2,an2+1或者含或者含有長度為有長度為n+1的遞增子序列，或者含有長度為的遞增子序列，或

33、者含有長度為n+1的遞減子序列。的遞減子序列。證明：證明：我們首先了解一下什么是子序列的概念。子序列：子序列：如果b1,b2,bm是一個序列，那么，則是一個子序列，其中，1i1 i2 ik m。例如，b2,b4,b5是序列b1,b2,b3,b4,b5,b6的一個子序列，而b2,b6,b5則不是。遞增遞增/減子序列：減子序列：子序列 若滿足條件則稱為遞增子序列，而滿足 則稱為遞減子序列。kiiibbb,.,21kiiibbb.2137鴿巢原理鴿巢原理1iikkaa我們假設(shè)不存在長度為n+1的遞增子序列，則需要證明必然存在長度為n+1的遞減子序列。對于每一個k=1,2,n2+1，令mk為從ak開始

34、的最長遞增子序列長度。由于假設(shè)不存在長度為n+1的遞增子序列，則對每個k=1,2, n2+1，有1 mkn。 如果將m1,m2, mn2+1這n2+1個數(shù)作為物體，最長子序列的長度1,2,n作為n個盒子，其中，第i個盒子代表長度為i的序列。根據(jù)鴿巢原理的加強形式，在m1,m2, mn2+1中有n+1個是相等的。令121.nkkkmmm其中，1k1k2kn+1。設(shè)對于某個i=1,2,n，有于是，由于kin-1。1)如果我們把Kn的邊或者涂成紅色或者涂成藍色，那么，或者Kn的某條邊是紅色的，因此我們得到了一個紅K2，或者Kn的所有邊都是藍色的，因此我們得到了一個藍Kn。即，KnK2,Kn，由于r(

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

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

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

38、是使得KNKm,Kn成立的最小整數(shù)N，所以，r(m,n)KN=r(m-1,n)+r(m,n-1)。50鴿巢原理鴿巢原理pRamsey定理的推廣情況：定理的推廣情況： 如果如果n1,n2和和n3是大于或等于是大于或等于2的的3個整數(shù)，則存在一個整數(shù)個整數(shù)，則存在一個整數(shù)p使得使得KpKn1,Kn2,Kn3，也就是說，也就是說，如果如果Kp的每條邊被涂上紅色或藍色或綠色，那么或者存在一個的每條邊被涂上紅色或藍色或綠色，那么或者存在一個紅紅Kn1，或者存在一個藍，或者存在一個藍Kn2，或者存在一個綠，或者存在一個綠Kn3。pRamsey數(shù)的推廣情況：數(shù)的推廣情況：Ramsey數(shù)數(shù)r(n1,n2,n3

39、)是使得是使得KpKn1,Kn2,Kn3成立的最小整數(shù)成立的最小整數(shù)p。Ramsey定理的任意推廣情況：定理的任意推廣情況： KpKn1,Kn2,Kn3,Kns。Ramsey數(shù)的任意推廣情況數(shù)的任意推廣情況：r(n1,n2,ns)。51鴿巢原理鴿巢原理證明證明r(3,3,3)17。證明：證明：考慮用3種顏色進行著色的完全圖K17，設(shè)p是K17的一個頂點。由鴿巢原理可知，以p為端點連接其余16個頂點的16條線中必有6條顏色相同(比如都是紅色)?？疾爝@6條線的除p外的6個頂點所形成的完全圖K6。如果K6中有一條是紅色，則這條邊的兩個頂端加上p就形成了一個紅色三角形，結(jié)論成立。否則，K6中沒有一條紅

40、色邊，則K6為用兩種顏色著色的完全圖，此時K6必含有一個同色的三角形。因此，K17中必含有一個同色的三角形，從而r(3,3,3)17。52鴿巢原理鴿巢原理pRamsey定理的一般形式：定理的一般形式： 在這種形式中點對在這種形式中點對(兩個元素的子兩個元素的子集集)由由t個元素的子集代替，其中個元素的子集代替，其中t1為某個整數(shù)。令為某個整數(shù)。令Knt表示表示n個個元素的集合中所有的元素的集合中所有的t個元素的子集的集合。個元素的子集的集合。定理定理6(Ramsey定理一般形式定理一般形式)： 給定整數(shù)給定整數(shù)t2及整數(shù)及整數(shù)q1,q2,qkt，存在一個整數(shù)，存在一個整數(shù)p使得使得KptKq1

41、t,Kq2t,Kqkt，也就，也就是說，存在一個整數(shù)是說，存在一個整數(shù)p使得如果將使得如果將p元素集合中的每一個元素集合中的每一個t元素子元素子集指定集指定k種顏色種顏色c1,c2,ck中的一種，那么或者存在中的一種，那么或者存在q1個元素，個元素，這些元素的所有這些元素的所有t元素子集都被指定顏色元素子集都被指定顏色c1，或者存在，或者存在q2個元素，個元素，這些元素的所有這些元素的所有t元素子集都被指定顏色元素子集都被指定顏色c2,或者存在或者存在qk個元個元素，這些元素的所有素，這些元素的所有t元素子集都被指定顏色元素子集都被指定顏色ck。Ramsey數(shù)的一般形式：數(shù)的一般形式：滿足上述

42、條件的最小整數(shù)滿足上述條件的最小整數(shù)p被稱為被稱為Ramsey數(shù)數(shù)rt(qk,q1,q2,qk)。53鴿巢原理鴿巢原理r1(q1,q2,qk)=q1+q2+qk-q+1。設(shè)t=1，于是，r1(q1,q2,qk)就是最小的數(shù)p，它滿足如果p個元素集合的元素用顏色c1,c2,ck中的一種顏色涂色，那么或者存在q1個涂成顏色c1的元素，或者存在q2個涂成顏色c2的元素，或者存在qk個涂成顏色ck的元素。因此，由鴿巢原理的加強形式，有r1(q1,q2,qk)=q1+q2+qk-q+1。這說明Ramsey定理是鴿巢原理的加強形式的推廣。54鴿巢原理鴿巢原理若令若令R(m)=r(3,3,3)目前已知目前已

43、知R(1)=3, R(2)=6, R(3,3,3)=17。m思考題：證明思考題：證明R(m) mR(m-1)-1+2。55主要內(nèi)容主要內(nèi)容 n概述概述n鴿巢原理鴿巢原理 n排列與組合排列與組合 n生成排列和組合生成排列和組合n二項式系數(shù)二項式系數(shù) n容斥原理及應(yīng)用容斥原理及應(yīng)用 n遞推關(guān)系和生成函數(shù)遞推關(guān)系和生成函數(shù)n特殊計數(shù)序列特殊計數(shù)序列 n二分圖匹配二分圖匹配nPolya計數(shù)法計數(shù)法 56排列與組合排列與組合n四個計數(shù)原理四個計數(shù)原理加法原理加法原理 集合劃分：集合劃分：令令S為給定的非空集合，為給定的非空集合，A=S1,S2,Sn，若，若1)Si S, Si ，i=1,2,n;2)Si

44、Sj= , ij, i,j=1,2,n；3)S=S1S2 Sn.則稱則稱A為集合為集合S的劃分，其中的劃分，其中Si(i=1,2,n)稱為該劃分的部分。稱為該劃分的部分。例：例：對對08級的研究生按照性別、年齡、專業(yè)進行劃分。級的研究生按照性別、年齡、專業(yè)進行劃分。57排列與組合排列與組合 加法原理：加法原理：設(shè)設(shè)S1,S2,Sn為集合為集合S的劃分，則的劃分，則S的元素的個的元素的個數(shù)可以通過找出它的每一個部分的元素的個數(shù)來確定，我們把數(shù)可以通過找出它的每一個部分的元素的個數(shù)來確定，我們把這些數(shù)相加，得到這些數(shù)相加，得到|S|=|S1|+|S2|+|Sn|。加法原理的另一表述方式：加法原理的

45、另一表述方式：如果有如果有p種方法能夠從一堆物品中種方法能夠從一堆物品中選擇一個物品，而有選擇一個物品，而有q種方法也能夠從另一堆物品中選擇一個物種方法也能夠從另一堆物品中選擇一個物品，那么從這兩堆物品中選擇一個物品的方法共有品，那么從這兩堆物品中選擇一個物品的方法共有p+q種。種。例：例：從從ICES中心中心(9人人)和信息安全中心和信息安全中心(6人人)選擇一名研究生的選擇一名研究生的方法數(shù)是多少？方法數(shù)是多少？ 58排列與組合排列與組合乘法原理：乘法原理：乘法原理：乘法原理：令令S是元素的序偶是元素的序偶(a,b)的集合，其中第一個元素的集合，其中第一個元素a來自大小為來自大小為p的一個

46、集合，而對于的一個集合，而對于a的每個選擇，元素的每個選擇，元素b存在著存在著q種選擇，于是，種選擇，于是，S的大小為的大小為pq，即，即，|S|=pq。 乘法原理的另一種表述方式：乘法原理的另一種表述方式：一項任務(wù)有一項任務(wù)有p個結(jié)果，而不論第個結(jié)果，而不論第一項任務(wù)的結(jié)果如何，第二項任務(wù)都有一項任務(wù)的結(jié)果如何，第二項任務(wù)都有q個結(jié)果，那么，這兩項個結(jié)果，那么，這兩項任務(wù)連續(xù)執(zhí)行就有任務(wù)連續(xù)執(zhí)行就有pq個結(jié)果。個結(jié)果。12abS1S21a1b2a2bc1c2c59排列與組合排列與組合乘法原理是加法原理的一個推論。乘法原理是加法原理的一個推論。令令a1,a2,ap是對元素是對元素a的的p個不同

47、的選擇。我們將個不同的選擇。我們將S劃分成部分劃分成部分S1,S2,Sp，其中，其中Si是是S內(nèi)內(nèi)第一個元素為第一個元素為ai(i=1,2,p)的序偶的集合。每個的序偶的集合。每個Si的大小為的大小為q，因此由加法原理有因此由加法原理有|S|=|S1|+|S2|+|Sp|=q+q+q=pq。1a1b2a2b1c2c集合集合1：第一個元素為：第一個元素為1，集合大小為，集合大小為3集合集合2：第一個元素為：第一個元素為2，集合大小為，集合大小為3|S|=3+3=23=660排列與組合排列與組合例：例：從從ICES中心中心(9人人)和信息安全中心和信息安全中心(6人人)各選擇一名研究生各選擇一名研

48、究生的方法數(shù)是多少？的方法數(shù)是多少？ 12abICES中心中心c3456789efgij信息安全中心信息安全中心123456789|S|=|S1|+|S2|+|S9|=89=7261排列與組合排列與組合思考題：思考題：從從08級研究生選擇兩名屬于不同中心的學(xué)生方法數(shù)級研究生選擇兩名屬于不同中心的學(xué)生方法數(shù)是多少？是多少？08級研究生情況：級研究生情況：(1)ICES：9人；人；(2)信息安全：信息安全：6人；人；(3)生物信息：生物信息：4人；人；(4)嵌入式：嵌入式：2人；人；(5)醫(yī)學(xué)圖像：醫(yī)學(xué)圖像：2人；人；(6)在職：在職：1人。人。62排列與組合排列與組合減法原理：減法原理：令令A(yù)是

49、一個集合，而是一個集合，而U是包含是包含A的更大的集合。設(shè)的更大的集合。設(shè) :AxUxA是是A在在U中的補。那么中的補。那么A中的元素個數(shù)中的元素個數(shù)|A|由下列法則給出：由下列法則給出：|AUA63排列與組合排列與組合除法原理：除法原理：令令S是一個有限集，它以下述方式方式被劃分成是一個有限集，它以下述方式方式被劃分成k部分，每一部分，每一部分包含相同數(shù)目的元素。此時，劃分中的部分數(shù)目由下述公部分包含相同數(shù)目的元素。此時，劃分中的部分數(shù)目由下述公式給出：式給出：數(shù)在一個部分中的元素個| Sk 64排列與組合排列與組合例例1：確定數(shù)確定數(shù)34 52 117 138的正整數(shù)因子的個數(shù)？的正整數(shù)因

50、子的個數(shù)？例例2：兩位數(shù)字有多少兩個位互異且非零的兩位數(shù)？兩位數(shù)字有多少兩個位互異且非零的兩位數(shù)？例例3：計算口令字計劃由計算口令字計劃由0,1,2,9和小寫字母和小寫字母a, b, c,z中取中取出的出的6個字符構(gòu)成的一個串組成。具有重復(fù)字符的計算機口令共個字符構(gòu)成的一個串組成。具有重復(fù)字符的計算機口令共有多少？有多少？例例4：在在1000和和9999之間有多少具有不同數(shù)字的奇數(shù)？之間有多少具有不同數(shù)字的奇數(shù)？例例5：在在0和和10000之間有多少個整數(shù)恰好有一位數(shù)字是之間有多少個整數(shù)恰好有一位數(shù)字是5？65排列與組合排列與組合n集合的排列集合的排列S的的r排列：排列：令令r為正整數(shù)，我們把

51、為正整數(shù)，我們把n個元素的集合個元素的集合S的一個的一個r排排列定義為列定義為n個元素中的個元素中的r個元素的有序擺放。個元素的有序擺放。例如，例如，S=a, b, c，則，則S的的1排列為：排列為：abcS的的2排列為：排列為：abacbabccacbS的的3排列為：排列為：abcacbbacbcacabcba66排列與組合排列與組合r-排列數(shù)目：排列數(shù)目：我們用我們用P(n,r)表示表示n個元素集合的個元素集合的r-排列的數(shù)目。排列的數(shù)目。如果如果rn，P(n,r)=0； 如果如果r=1，P(n,1)=n；定理定理1：對于正整數(shù)：對于正整數(shù)n和和r，rn，有，有P(n,r)=n(n-1)

52、(n-r+1)。證明：證明：在構(gòu)建n-元素集的一個r排列時，我們可以用n種方法選擇第一項，不論第一項如何選出，都可以用n-1種方法選擇第二項，以及不論前r-1項如何選出，都可以用n-(r-1)種方法選擇第r項。根據(jù)乘法原理，這r項可以用n(n-1) (n-r+1)種方法選出。67排列與組合排列與組合123n第一項第一項有有n種種方法方法第二項第二項有有n-1種方法種方法12r第第r項有項有n-r+1種種方法方法S68排列與組合排列與組合例：例：將將08級的級的24個研究生排列使得個研究生排列使得ICES中心中心(9個學(xué)生個學(xué)生)的任意的任意兩個學(xué)生都不能相繼出現(xiàn)，這種排列的方法總數(shù)是多少？兩個

53、學(xué)生都不能相繼出現(xiàn)，這種排列的方法總數(shù)是多少？例：例：有多少種方法從有多少種方法從08級的級的24個研究生中取個研究生中取7個人進行排列，個人進行排列，并且使得王偉和謝冬輝不能以任何順序相繼出現(xiàn)？并且使得王偉和謝冬輝不能以任何順序相繼出現(xiàn)？69排列與組合排列與組合n循環(huán)排列：循環(huán)排列：例：例：6個孩子沿圓圈行進，他們能夠以多少種不同的方式形成個孩子沿圓圈行進，他們能夠以多少種不同的方式形成一個圓？一個圓？12345661234556123445612334561223456112345661234556123445612334561223456170排列與組合排列與組合如果兩個循環(huán)排列通過一個

54、旋轉(zhuǎn)，即一個循環(huán)移位，從其中的如果兩個循環(huán)排列通過一個旋轉(zhuǎn)，即一個循環(huán)移位，從其中的一個變到另一個，那么可以將它們看成是相同的。一個變到另一個，那么可以將它們看成是相同的。這樣，在這樣，在6個孩子的線性排列和個孩子的線性排列和6個孩子的循環(huán)排列之間就存在個孩子的循環(huán)排列之間就存在著著6到到1的對應(yīng)。因此，要想求得循環(huán)排列的數(shù)目，我們只要用的對應(yīng)。因此，要想求得循環(huán)排列的數(shù)目，我們只要用6去除線性排列的數(shù)目即可。所以，去除線性排列的數(shù)目即可。所以，6個孩子的循環(huán)排列數(shù)目等個孩子的循環(huán)排列數(shù)目等于于6!/6=5!71排列與組合排列與組合定理定理2：n個元素的集合的循環(huán)個元素的集合的循環(huán)r-排列的個

55、數(shù)為排列的個數(shù)為)!(!),(rnrnrrnP特別地，特別地，n個元素的循環(huán)排列的個數(shù)是個元素的循環(huán)排列的個數(shù)是(n-1)!。證明：證明：可以把線性r-排列的集合劃分成一些部分，使得兩個線性r-排列對應(yīng)同一個循環(huán)r-排列當且僅當它們在同一個部分中。于是，循環(huán)r-排列的個數(shù)等于部分的個數(shù)。既然每一個部分都含有r個線性r-排列，根據(jù)除法原理，部分的數(shù)目等于)!(!),(rnrnrrnP72排列與組合排列與組合例：例：ICES中心中心08級的級的9個研究生要圍坐一個圓桌，其中有兩個研究生要圍坐一個圓桌，其中有兩個人不愿意彼此挨著就座，共有多少循環(huán)座位排放方法？個人不愿意彼此挨著就座，共有多少循環(huán)座位

56、排放方法？例：例：6男男6女圍坐一個圓桌，如果男女交替圍坐，可以有多少女圍坐一個圓桌，如果男女交替圍坐，可以有多少圍坐方式？圍坐方式？73排列與組合排列與組合n集合的組合集合的組合S的的r組合：組合：令令r為非負整數(shù)，我們把為非負整數(shù)，我們把n個元素的集合個元素的集合S的的r-組合組合可以定義為從可以定義為從S的的n個元素中對個元素中對r個元素的無序選擇。個元素的無序選擇。例如，例如，S=a, b, c, d 的的3的組合為的組合為a, b, c，a, b, d，a, c, d，b, c, dr-組合數(shù)目：組合數(shù)目：我們用我們用 表示表示n-元素集的元素集的r-組合的個數(shù)。組合的個數(shù)。如果如果

57、rn， =0；如果；如果r0， =0。nrnr0rn0=1n1=nnn=100=174排列與組合排列與組合定理定理3：對于對于0rn，rnrrnP!),(因此，因此，)!( !rnrnrn證明：證明：令S是一個n-元素集。S的每個r-排列都是由下面的兩個任務(wù)執(zhí)行結(jié)果產(chǎn)生。1)從S中選出r個元素。2)將所選出的r個元素以某種順序排列。執(zhí)行第一個任務(wù)的方法數(shù)根據(jù)定義可知為組合數(shù) 。nr75排列與組合排列與組合執(zhí)行第二個任務(wù)的方法數(shù)則是P(r,r)=r!。 根據(jù)乘法原理我們有rnrrnP!),(所以，)!( !),(rnrnrrnPrn76排列與組合排列與組合定理定理4：nnnnnn2.210證明：

58、通過對證明：通過對n-元素集元素集S的組合計數(shù)來證明。的組合計數(shù)來證明。1)S的每一個組合是的每一個組合是S對于對于r(r=0,1,2,n)的一個的一個r-組合。由于組合。由于nr等于等于S的的r-組合數(shù)，由加法原理組合數(shù)，由加法原理nnnnn.210等于等于S的所有組合的總個數(shù)。的所有組合的總個數(shù)。77排列與組合排列與組合2)把一個組合的選取分成把一個組合的選取分成n個任務(wù)來完成。令個任務(wù)來完成。令S的元素為的元素為x1,x2,xn。在選擇。在選擇S的一個組合時，對的一個組合時，對n個元素的每一個都個元素的每一個都有兩種選擇：有兩種選擇：xi(i=1,2,n)要么在這個組合里；要么在這個組合

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

60、元素的多重集，其中，有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(1i n)，稱稱ki為為ai的重數(shù)，的重數(shù)，ki是正整數(shù)，也可以是是正整數(shù)，也可以是，表示，表示S中有無限多個中有無限多個ai。79排列與組合排列與組合多重集排列多重集排列設(shè)設(shè)S=3 a,1 b,2 c,4 d ，那么，那么acbc，cbcc為為S的的4排列，而排列，而