組合數(shù)學(xué)-第一章-排列組合

1、組合數(shù)學(xué)Combinatorial Mathematics 第四版盧開澄 盧華明蘇建忠辦公地點(diǎn)：系統(tǒng)生物學(xué)教研室（基礎(chǔ)醫(yī)學(xué)院三樓3001）郵箱：講課用書： 組合數(shù)學(xué)，盧開澄等編參考書目： 組合數(shù)學(xué)，Richard A.Brualdi 組合數(shù)學(xué) 姜建國等編 組合數(shù)學(xué)及其算法 楊振生等編組合數(shù)學(xué)的問題無處不在 排課表（教師、學(xué)生、時間、教室）體育比賽 ：淘汰賽、循環(huán)賽、混合賽制訪問路徑 ：巡回售貨員（郵遞員）、網(wǎng)絡(luò)路由、實(shí)驗(yàn)設(shè)計(jì) ：新藥（減少人為因素）、計(jì)量（降低儀器誤差）、組合數(shù)學(xué)分類組合數(shù)學(xué)是研究離散結(jié)構(gòu)的存在、計(jì)數(shù)、分析和優(yōu)化問題的學(xué)科組合分析：研究計(jì)數(shù)和枚舉的基本方法: 數(shù)學(xué)歸納法，母函數(shù)

2、法， 組合設(shè)計(jì)：構(gòu)造特殊的離散結(jié)構(gòu) 幻方，區(qū)組設(shè)計(jì)，實(shí)驗(yàn)設(shè)計(jì)，編碼， 組合算法：組合問題涉及的算法（搜索法、算法復(fù)雜度、NPC、）圖論：頂點(diǎn)和邊的連接關(guān)系 ：同構(gòu)，路徑，流量，連通，著色， 前言 組合數(shù)學(xué)是一個古老而又年輕的數(shù)學(xué)分支。 據(jù)傳說，大禹在4000多年前就觀察到神龜背上的幻方.前言 幻方可以看作是一個3階方陣，其元素是1到9的正整數(shù)。519734268公元1275年，我國宋代大數(shù)學(xué)家楊輝對“洛書”進(jìn)行了深入研究，在他所著的“續(xù)古摘奇算經(jīng)”中寫道：“九子斜排，上下對易，左右相更，四維挺進(jìn)，戴九履一，左三右七，二四為肩，六八為足。前言 1666年萊布尼茲所著組合學(xué)論文一書問世，這是組合數(shù)

3、學(xué)的第一部專著。書中首次使用了組合論（Combinatorics）一詞。 組合數(shù)學(xué)，有人把它稱為離散數(shù)學(xué)，但有時人們也把組合數(shù)學(xué)、圖論、數(shù)理邏輯、和代數(shù)結(jié)構(gòu)加在一起算成是離散數(shù)學(xué)。組合數(shù)學(xué)是計(jì)算機(jī)出現(xiàn)以后迅速發(fā)展起來的一門數(shù)學(xué)分支。計(jì)算機(jī)科學(xué)實(shí)質(zhì)上是一門算法的科學(xué)，而計(jì)算機(jī)所處理的對象是離散的數(shù)據(jù)，所以離散對象的處理就成了計(jì)算機(jī)科學(xué)的核心，而研究離散對象的科學(xué)恰恰就是組合數(shù)學(xué)。 組合數(shù)學(xué)不僅在基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其它的學(xué)科中也有重要的應(yīng)用，如計(jì)算機(jī)科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等學(xué)科中均有重要應(yīng)用。微積分和近代數(shù)學(xué)的發(fā)展為近代的工業(yè)革命奠定了基礎(chǔ)。而組合數(shù)學(xué)的發(fā)展則是奠定

4、了本世紀(jì)的計(jì)算機(jī)革命的基礎(chǔ)。什么是組合數(shù)學(xué) 對于一門學(xué)科來說，我們很難下一個明確的定義，我們只能從組合數(shù)學(xué)的主要研究對象是什么這個側(cè)面來回答這個問題。 組合數(shù)學(xué)研究的主要內(nèi)容 組合數(shù)學(xué)研究的主要內(nèi)容是依據(jù)一定的規(guī)則來安排某些事物的有關(guān)數(shù)學(xué)問題。 我們主要從以下四個方面研究這些問題問題： 1.這種安排是否存在。（存在性問題）2.如果符合要求得安排存在，那么這樣的安排有多少種. 即計(jì)數(shù)問題。3.怎樣構(gòu)造這樣的安排，即算法構(gòu)造問題。4.如果給出了最優(yōu)化標(biāo)準(zhǔn)，又怎樣得到最優(yōu)化安排，即最優(yōu)化問題。船夫過河問題 一個船夫要把一只狼，一只羊和一棵白菜運(yùn)過河。而他的船每趟只能運(yùn)其中的一個。問題是當(dāng)人不在場時，

5、狼要吃羊，羊要吃白菜，問他怎樣才能把三者安全的運(yùn)過河呢？ 從組合數(shù)角度看船夫過河問題1）存在性2）計(jì)數(shù)3）算法的構(gòu)造4）優(yōu)化問題36 軍官問題從不同的6個軍團(tuán)各選6種不同軍階的6名軍官共36人，排 成一個6行6列的方隊(duì)，使得各行各列的6名軍官恰好來自不同的軍團(tuán)而且軍階各不相同，應(yīng)如何 排這個方隊(duì)？ 組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計(jì)數(shù)時的合理分類和組合模型的轉(zhuǎn)換。 但是，要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練。第一章排列組合（1) 2個互異的球放入3個互異的盒子，每個盒子至多一個球，有多少方案？（2） 2個互異的球放入3個互異的盒子，每個盒子球數(shù)不限

6、，有多少方案？（3） 2個相同的球放入3個互異的盒子，每個盒子至多一個球，有多少方案？（4）3個人圍成一圈，有多少方案？（5） 5個人（每人都會開車）分乘2輛小轎車（每車4座），有多少方案？1.1 加法法則與乘法法則 加法法則 設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件A或B之一有m+n種產(chǎn)生方式。集合論語言：若 |A| = m , |B| = n , AB = , 則 |AB| = m + n 。1.1 加法法則與乘法法則 例 某班選修企業(yè)管理的有 18 人，不選的有 10 人，則該班共有 18 + 10 = 28 人。 例 北京每天直達(dá)上海的客車有 5 次，客機(jī)有 3 次， 則每

7、天由北京直達(dá)上海的旅行方式有 5 + 3 = 8 種。1.1 加法法則與乘法法則 乘法法則 設(shè)具有性質(zhì)A的事件有m個，具有性質(zhì)B的事件有m個，則具有性質(zhì)A與B的事件有 m n個。集合論語言：若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 則 |A B| = m n 。1.1 加法法則與乘法法則例 某種字符串由兩個字符組成，第一個字符可選自a，b，c，d，e，第二個字符可選自1，2，3，則這種字符串共有5 3 = 15 個。例 從A到B有三條道路，從B到C有兩條道路，則從A經(jīng)B到C有32=6 條道路。1.1 加法法則與乘法法則例 某種樣式的運(yùn)動服的著色由底

8、色和裝飾條紋的顏色配成。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42 = 8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色的話，則，方案數(shù)就不是4 4 = 16， 而只有 4 3 = 12 種。在乘法法則中要注意事件 A 和 事件 B 的相互獨(dú)立性。1.1 加法法則與乘法法則例 1)求小于10000的含1的正整數(shù)的個數(shù) 2)求小于10000的含0的正整數(shù)的個數(shù)1)小于10000的不含1的正整數(shù)可看做4位數(shù),但0000除外. 故有999916560個. 含1的有：99996560=3439個另: 全部4位數(shù)有10 個,不含1的四位數(shù)有9 個, 含1的4位數(shù)為兩個的差: 10 9 = 3439個4 44 42)“含0”和“含1”不可直接套用。0019含1但不含0。 在組合的習(xí)題中有許多類似的隱含的規(guī)定，要特別留神。 不含0的1位數(shù)有9個，2位數(shù)有9 個，3位數(shù)有9 個，4位數(shù)有9 個 不含0小于10000的正整數(shù)有 9+9 +9 +9 =(9 9)/(91)=7380個含0小于