組合數(shù)學(xué)課件

1、組合數(shù)學(xué)1 組合數(shù)學(xué)組合數(shù)學(xué) RichardA.Brualdi 著著 馮舜璽馮舜璽 等等 編譯編譯 機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社 任課教師任課教師： 廖廖 虎虎組合數(shù)學(xué)2 辦公室：軟件學(xué)院四樓專業(yè)教研室辦公室：軟件學(xué)院四樓專業(yè)教研室 辦公電話：辦公電話：8 8 4 5 1 1 2 88 8 4 5 1 1 2 8 住宅電話：住宅電話：8 2 4 9 5 8 7 48 2 4 9 5 8 7 4 移動(dòng)電話：移動(dòng)電話：1 3 0 9 6 9 8 1 1 8 21 3 0 9 6 9 8 1 1 8 2 電子郵件：電子郵件：xaLiaohxaLiaoh 組合數(shù)學(xué)3緒緒 論論 組合數(shù)學(xué)是一門古老的數(shù)學(xué)

2、分支，其思想組合數(shù)學(xué)是一門古老的數(shù)學(xué)分支，其思想在社會(huì)科學(xué)、信息論、生物科學(xué)以及其他傳統(tǒng)在社會(huì)科學(xué)、信息論、生物科學(xué)以及其他傳統(tǒng)自然科學(xué)領(lǐng)域得到了廣泛的應(yīng)用。自然科學(xué)領(lǐng)域得到了廣泛的應(yīng)用。組合數(shù)學(xué)在組合數(shù)學(xué)在計(jì)算機(jī)出現(xiàn)以后得以迅速發(fā)展。計(jì)算機(jī)科學(xué)就計(jì)算機(jī)出現(xiàn)以后得以迅速發(fā)展。計(jì)算機(jī)科學(xué)就是算法的科學(xué)，而計(jì)算機(jī)所處理的對(duì)象是離散是算法的科學(xué)，而計(jì)算機(jī)所處理的對(duì)象是離散的數(shù)據(jù)，所以離散對(duì)象的處理就成了計(jì)算機(jī)的數(shù)據(jù)，所以離散對(duì)象的處理就成了計(jì)算機(jī)組合數(shù)學(xué)4 科學(xué)的核心，而研究離散對(duì)象的科學(xué)恰恰就科學(xué)的核心，而研究離散對(duì)象的科學(xué)恰恰就是離散數(shù)學(xué)和組合數(shù)學(xué)；組合數(shù)學(xué)的發(fā)展改是離散數(shù)學(xué)和組合數(shù)學(xué)；組合數(shù)學(xué)

3、的發(fā)展改變了傳統(tǒng)數(shù)學(xué)中分析和代數(shù)占統(tǒng)治地位的局變了傳統(tǒng)數(shù)學(xué)中分析和代數(shù)占統(tǒng)治地位的局面?，F(xiàn)代數(shù)學(xué)可以分為兩大類：一類是研究面?，F(xiàn)代數(shù)學(xué)可以分為兩大類：一類是研究連續(xù)對(duì)象的，如分析、方程等，另一類就是連續(xù)對(duì)象的，如分析、方程等，另一類就是研究離散對(duì)象的組合數(shù)學(xué)。組合數(shù)學(xué)不僅在研究離散對(duì)象的組合數(shù)學(xué)。組合數(shù)學(xué)不僅在基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其它的學(xué)科中也有重要的應(yīng)用，如計(jì)算機(jī)科學(xué)、它的學(xué)科中也有重要的應(yīng)用，如計(jì)算機(jī)科學(xué)、編碼和編碼和組合數(shù)學(xué)5 密碼學(xué)、物理、化學(xué)、生物等學(xué)科中均有重要密碼學(xué)、物理、化學(xué)、生物等學(xué)科中均有重要應(yīng)用。微積分和近代數(shù)學(xué)的發(fā)展

4、為近代的工業(yè)應(yīng)用。微積分和近代數(shù)學(xué)的發(fā)展為近代的工業(yè)革命奠定了基礎(chǔ)。而組合數(shù)學(xué)的發(fā)展則是奠定革命奠定了基礎(chǔ)。而組合數(shù)學(xué)的發(fā)展則是奠定了本世紀(jì)的計(jì)算機(jī)革命的基礎(chǔ)。計(jì)算機(jī)之所以了本世紀(jì)的計(jì)算機(jī)革命的基礎(chǔ)。計(jì)算機(jī)之所以可以被稱為可以被稱為電腦電腦，就是因?yàn)橛?jì)算機(jī)被人編寫了，就是因?yàn)橛?jì)算機(jī)被人編寫了程序，而程序就是算法，在絕大多數(shù)情況下，程序，而程序就是算法，在絕大多數(shù)情況下，計(jì)算機(jī)的算法是針對(duì)離散的對(duì)象計(jì)算機(jī)的算法是針對(duì)離散的對(duì)象，而不是在作而不是在作數(shù)值計(jì)算。數(shù)值計(jì)算。 組合數(shù)學(xué)6 正是因?yàn)橛辛私M合算法才使人感到，計(jì)算機(jī)正是因?yàn)橛辛私M合算法才使人感到，計(jì)算機(jī)好象是有思維的。好象是有思維的。 組合數(shù)

5、學(xué)不僅在軟件技術(shù)中有重要的應(yīng)用價(jià)組合數(shù)學(xué)不僅在軟件技術(shù)中有重要的應(yīng)用價(jià)值，在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭(zhēng)指揮，金融分值，在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭(zhēng)指揮，金融分析等領(lǐng)域都有重要的應(yīng)用。在美國(guó)有一家用組合析等領(lǐng)域都有重要的應(yīng)用。在美國(guó)有一家用組合數(shù)學(xué)命名的公司，他們用組合數(shù)學(xué)的方法來提高數(shù)學(xué)命名的公司，他們用組合數(shù)學(xué)的方法來提高企業(yè)管理的效益，這家公司辦得非常成功。企業(yè)管理的效益，這家公司辦得非常成功。 組合數(shù)學(xué)7 此外，試驗(yàn)設(shè)計(jì)也是具有很大應(yīng)用價(jià)值的此外，試驗(yàn)設(shè)計(jì)也是具有很大應(yīng)用價(jià)值的學(xué)科，它的數(shù)學(xué)原理就是組合設(shè)計(jì)。用組合設(shè)學(xué)科，它的數(shù)學(xué)原理就是組合設(shè)計(jì)。用組合設(shè)計(jì)的方法解決工業(yè)界中的試驗(yàn)設(shè)計(jì)問題，

6、在美計(jì)的方法解決工業(yè)界中的試驗(yàn)設(shè)計(jì)問題，在美國(guó)已有專門的公司開發(fā)這方面的軟件。最近，國(guó)已有專門的公司開發(fā)這方面的軟件。最近，德國(guó)一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研德國(guó)一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用，究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用，引起了制藥業(yè)的關(guān)注。引起了制藥業(yè)的關(guān)注。組合數(shù)學(xué)8 組合數(shù)學(xué)與計(jì)算機(jī)軟件 隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，計(jì)算機(jī)的使用已隨著計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，計(jì)算機(jī)的使用已經(jīng)影響到了人們的工作，生活，學(xué)習(xí)，社會(huì)活動(dòng)經(jīng)影響到了人們的工作，生活，學(xué)習(xí)，社會(huì)活動(dòng)以及商業(yè)活動(dòng)，而計(jì)算機(jī)的應(yīng)用根本上是通過軟以及商業(yè)活動(dòng)，而計(jì)算機(jī)的應(yīng)用根本上是通過軟件

7、來實(shí)現(xiàn)的。在美國(guó)有一種說法：將來一個(gè)國(guó)家件來實(shí)現(xiàn)的。在美國(guó)有一種說法：將來一個(gè)國(guó)家的經(jīng)濟(jì)實(shí)力可以直接從軟件產(chǎn)業(yè)反映出來。的經(jīng)濟(jì)實(shí)力可以直接從軟件產(chǎn)業(yè)反映出來。 組合數(shù)學(xué)9 我國(guó)在軟件上的落后，要說出根本的原因可我國(guó)在軟件上的落后，要說出根本的原因可能并不是簡(jiǎn)單的事，除了技術(shù)和科學(xué)上的原能并不是簡(jiǎn)單的事，除了技術(shù)和科學(xué)上的原因外，可能還跟我們的文化因外，可能還跟我們的文化( (漢字漢字) )，管理水，管理水平，教育水平，思想素質(zhì)等諸多因素有關(guān)。平，教育水平，思想素質(zhì)等諸多因素有關(guān)。除去這些人文因素以外，一個(gè)最根本的原因除去這些人文因素以外，一個(gè)最根本的原因就是我國(guó)的信息技術(shù)的數(shù)學(xué)基礎(chǔ)十分薄弱，就

8、是我國(guó)的信息技術(shù)的數(shù)學(xué)基礎(chǔ)十分薄弱，這個(gè)問題不解決，我們就難成為軟件強(qiáng)國(guó)。這個(gè)問題不解決，我們就難成為軟件強(qiáng)國(guó)。 組合數(shù)學(xué)10 然而問題決不是這么簡(jiǎn)單，信息技術(shù)的發(fā)然而問題決不是這么簡(jiǎn)單，信息技術(shù)的發(fā)展已經(jīng)涉及到了很深的數(shù)學(xué)知識(shí)，而數(shù)學(xué)本身展已經(jīng)涉及到了很深的數(shù)學(xué)知識(shí)，而數(shù)學(xué)本身發(fā)展程度并不是單憑幾個(gè)聰明的頭腦去想想就發(fā)展程度并不是單憑幾個(gè)聰明的頭腦去想想就行了，而更重要的是需要集體的合作和力量，行了，而更重要的是需要集體的合作和力量，就象軟件的開發(fā)需要多方面的人員的合作。美就象軟件的開發(fā)需要多方面的人員的合作。美國(guó)的軟件之所以能領(lǐng)先，其關(guān)鍵就在于在數(shù)學(xué)國(guó)的軟件之所以能領(lǐng)先，其關(guān)鍵就在于在數(shù)學(xué)

9、基礎(chǔ)上他們有很強(qiáng)的實(shí)力，有很多杰出的人才。基礎(chǔ)上他們有很強(qiáng)的實(shí)力，有很多杰出的人才。組合數(shù)學(xué)11 一般人可能會(huì)認(rèn)為數(shù)學(xué)是一門純粹的基礎(chǔ)科學(xué)，一般人可能會(huì)認(rèn)為數(shù)學(xué)是一門純粹的基礎(chǔ)科學(xué)，1+1的解決可能不會(huì)有任何實(shí)際的意義。如果真的解決可能不會(huì)有任何實(shí)際的意義。如果真是這樣，一門純粹學(xué)科的發(fā)展落后幾年，甚至是這樣，一門純粹學(xué)科的發(fā)展落后幾年，甚至十年，關(guān)系也不大。然而中國(guó)的軟件產(chǎn)業(yè)的發(fā)十年，關(guān)系也不大。然而中國(guó)的軟件產(chǎn)業(yè)的發(fā)展已向數(shù)學(xué)基礎(chǔ)提出了急切的需求：網(wǎng)絡(luò)算法展已向數(shù)學(xué)基礎(chǔ)提出了急切的需求：網(wǎng)絡(luò)算法和分析、信息壓縮、網(wǎng)絡(luò)安全、編碼技術(shù)、系和分析、信息壓縮、網(wǎng)絡(luò)安全、編碼技術(shù)、系統(tǒng)軟件、并行算法

10、、數(shù)學(xué)機(jī)械化和計(jì)算機(jī)推理統(tǒng)軟件、并行算法、數(shù)學(xué)機(jī)械化和計(jì)算機(jī)推理組合數(shù)學(xué)12 等等。此外，與實(shí)際應(yīng)用有關(guān)的還有許多許多等等。此外，與實(shí)際應(yīng)用有關(guān)的還有許多許多需要數(shù)學(xué)基礎(chǔ)的算法，如運(yùn)籌規(guī)劃，金融工程，需要數(shù)學(xué)基礎(chǔ)的算法，如運(yùn)籌規(guī)劃，金融工程，計(jì)算機(jī)輔助設(shè)計(jì)等。如果我們的軟件產(chǎn)業(yè)還是計(jì)算機(jī)輔助設(shè)計(jì)等。如果我們的軟件產(chǎn)業(yè)還是把眼光一直盯在應(yīng)用軟件和第二次開發(fā)，那么把眼光一直盯在應(yīng)用軟件和第二次開發(fā)，那么我們?cè)趹?yīng)用軟件這個(gè)領(lǐng)域也會(huì)讓國(guó)外的企業(yè)搶我們?cè)趹?yīng)用軟件這個(gè)領(lǐng)域也會(huì)讓國(guó)外的企業(yè)搶去很大的市場(chǎng)。如果我們現(xiàn)在在信息技術(shù)的數(shù)去很大的市場(chǎng)。如果我們現(xiàn)在在信息技術(shù)的數(shù)學(xué)基礎(chǔ)上，大力支持和投入，那將是亡羊補(bǔ)

11、牢，學(xué)基礎(chǔ)上，大力支持和投入，那將是亡羊補(bǔ)牢，猶未為晚；猶未為晚； 組合數(shù)學(xué)13 胡錦濤同志在胡錦濤同志在19981998年接見年接見“五四五四”青年獎(jiǎng)青年獎(jiǎng)?wù)芦@得者時(shí)發(fā)表的講話中指出：組合數(shù)學(xué)是不章獲得者時(shí)發(fā)表的講話中指出：組合數(shù)學(xué)是不同于傳統(tǒng)的純數(shù)學(xué)的一個(gè)分支，它還是一門應(yīng)同于傳統(tǒng)的純數(shù)學(xué)的一個(gè)分支，它還是一門應(yīng)用學(xué)科，一門交叉學(xué)科。他希望中國(guó)的組合數(shù)用學(xué)科，一門交叉學(xué)科。他希望中國(guó)的組合數(shù)學(xué)研究能夠?yàn)閲?guó)家的經(jīng)濟(jì)建設(shè)服務(wù)。學(xué)研究能夠?yàn)閲?guó)家的經(jīng)濟(jì)建設(shè)服務(wù)。 如果如果2121世紀(jì)是信息社會(huì)的世紀(jì)，那么世紀(jì)是信息社會(huì)的世紀(jì)，那么2121世世紀(jì)也必將是組合數(shù)學(xué)大有可為的世紀(jì)。紀(jì)也必將是組合數(shù)學(xué)大有

12、可為的世紀(jì)。組合數(shù)學(xué)14 組合數(shù)學(xué)組合數(shù)學(xué)課每周上課兩次，課每周上課兩次，4 4學(xué)時(shí)，安學(xué)時(shí)，安排排1414周，共周，共5656學(xué)時(shí)。根據(jù)教學(xué)計(jì)劃和培養(yǎng)目標(biāo)學(xué)時(shí)。根據(jù)教學(xué)計(jì)劃和培養(yǎng)目標(biāo)要求，我們學(xué)習(xí)以下內(nèi)容：要求，我們學(xué)習(xí)以下內(nèi)容：第一章第一章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué) 第二章第二章 鴿巢原理鴿巢原理 第三章第三章 排列與組合排列與組合 第四章第四章 生成排列與組生成排列與組合合 第五章第五章 二項(xiàng)式系數(shù)二項(xiàng)式系數(shù) 第六章第六章 容斥原理及其應(yīng)容斥原理及其應(yīng)用用 第七章第七章 遞推關(guān)系與生成函數(shù)遞推關(guān)系與生成函數(shù)第八章第八章特殊計(jì)數(shù)序列特殊計(jì)數(shù)序列組合數(shù)學(xué)15 考核方式：期末筆試占考核方式

13、：期末筆試占70%70%，平時(shí)作業(yè)占，平時(shí)作業(yè)占30%30%， 每星期一交一次作業(yè)。由各個(gè)班長(zhǎng)送到四每星期一交一次作業(yè)。由各個(gè)班長(zhǎng)送到四樓辦公室。樓辦公室。 本課件制作由廖虎獨(dú)立完成，該課件幾乎本課件制作由廖虎獨(dú)立完成，該課件幾乎可以取代教材，已經(jīng)公布在學(xué)院公共實(shí)驗(yàn)室網(wǎng)可以取代教材，已經(jīng)公布在學(xué)院公共實(shí)驗(yàn)室網(wǎng)上，同學(xué)們可以自己下載瀏覽。上，同學(xué)們可以自己下載瀏覽。組合數(shù)學(xué)16 第第1章章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué) 組合數(shù)學(xué)是一門古老的數(shù)學(xué)分支，其思組合數(shù)學(xué)是一門古老的數(shù)學(xué)分支，其思想在社會(huì)科學(xué)、信息論、生物科學(xué)以及其他想在社會(huì)科學(xué)、信息論、生物科學(xué)以及其他傳統(tǒng)自然科學(xué)領(lǐng)域得到了廣泛的應(yīng)用。

14、傳統(tǒng)自然科學(xué)領(lǐng)域得到了廣泛的應(yīng)用。組合組合學(xué)問題在生活中隨處可見。學(xué)問題在生活中隨處可見。在計(jì)算機(jī)科學(xué)領(lǐng)在計(jì)算機(jī)科學(xué)領(lǐng)域，組合數(shù)學(xué)是域，組合數(shù)學(xué)是算法設(shè)計(jì)理論算法設(shè)計(jì)理論以及以及算法分析算法分析理論理論的重要數(shù)學(xué)工具。的重要數(shù)學(xué)工具。組合數(shù)學(xué)17 例如，計(jì)算下列賽制下總的例如，計(jì)算下列賽制下總的比賽次數(shù)比賽次數(shù)：n個(gè)個(gè)球隊(duì)參賽，每隊(duì)只和其他隊(duì)比賽一次球隊(duì)參賽，每隊(duì)只和其他隊(duì)比賽一次;創(chuàng)建創(chuàng)建幻方幻方;在紙上畫一個(gè)網(wǎng)絡(luò)，用鉛筆沿著網(wǎng)絡(luò)的線路走，在紙上畫一個(gè)網(wǎng)絡(luò)，用鉛筆沿著網(wǎng)絡(luò)的線路走，在筆不離開紙面且不重復(fù)線路的條件下，筆畫在筆不離開紙面且不重復(fù)線路的條件下，筆畫出出網(wǎng)絡(luò)圖網(wǎng)絡(luò)圖(一筆畫一筆畫)

15、;在玩撲克牌游戲中，計(jì)算滿在玩撲克牌游戲中，計(jì)算滿堂紅堂紅(fullhoue)牌的手?jǐn)?shù)，以確定出現(xiàn)一手滿堂牌的手?jǐn)?shù)，以確定出現(xiàn)一手滿堂紅牌的紅牌的幾率幾率。所有這些。所有這些都是組合學(xué)問題。都是組合學(xué)問題。組合數(shù)學(xué)18 正如人們想到的，組合數(shù)學(xué)的歷史淵源正如人們想到的，組合數(shù)學(xué)的歷史淵源扎根于數(shù)學(xué)扎根于數(shù)學(xué)娛樂娛樂和和游戲游戲之中。過去研究過的之中。過去研究過的許多問題，不論出于消遣還是出于對(duì)其美學(xué)許多問題，不論出于消遣還是出于對(duì)其美學(xué)的考慮，如今在純科學(xué)和應(yīng)用科學(xué)中都具有的考慮，如今在純科學(xué)和應(yīng)用科學(xué)中都具有高度的重要性。今天，組合數(shù)學(xué)是數(shù)學(xué)的一高度的重要性。今天，組合數(shù)學(xué)是數(shù)學(xué)的一門重要分

16、支，而且它的影響還在繼續(xù)擴(kuò)大。門重要分支，而且它的影響還在繼續(xù)擴(kuò)大。組合數(shù)學(xué)自組合數(shù)學(xué)自6060年代以來急速發(fā)展的部分原因年代以來急速發(fā)展的部分原因組合數(shù)學(xué)19 就在于計(jì)算機(jī)在我們的社會(huì)中所發(fā)揮的重要就在于計(jì)算機(jī)在我們的社會(huì)中所發(fā)揮的重要影響，而且這種影響還在繼續(xù)發(fā)揮。影響，而且這種影響還在繼續(xù)發(fā)揮。 組合數(shù)學(xué)近期發(fā)展的另一個(gè)原因是它對(duì)于組合數(shù)學(xué)近期發(fā)展的另一個(gè)原因是它對(duì)于那些過去很少與數(shù)學(xué)正式接觸的學(xué)科的適用性。那些過去很少與數(shù)學(xué)正式接觸的學(xué)科的適用性。由此我們發(fā)現(xiàn)，組合數(shù)學(xué)的思想和技巧不僅正在由此我們發(fā)現(xiàn)，組合數(shù)學(xué)的思想和技巧不僅正在用于數(shù)學(xué)應(yīng)用的傳統(tǒng)自然科學(xué)領(lǐng)域，而且也用于用于數(shù)學(xué)應(yīng)用的

17、傳統(tǒng)自然科學(xué)領(lǐng)域，而且也用于社會(huì)科學(xué)、生物科學(xué)、信息論等領(lǐng)域。社會(huì)科學(xué)、生物科學(xué)、信息論等領(lǐng)域。組合數(shù)學(xué)20 組合數(shù)學(xué)涉及到將一個(gè)集合的物體排列成組合數(shù)學(xué)涉及到將一個(gè)集合的物體排列成滿足一些指定規(guī)則的格式。如下兩類一般性問滿足一些指定規(guī)則的格式。如下兩類一般性問題反復(fù)出現(xiàn)：題反復(fù)出現(xiàn)：排列的存在性：如果有人想要排列一個(gè)集合的排列的存在性：如果有人想要排列一個(gè)集合的成員使得某些條件得以滿足，那么這樣一種排成員使得某些條件得以滿足，那么這樣一種排列是否可行就顯而易見的。這是最根本的問題。列是否可行就顯而易見的。這是最根本的問題。如果這種排列不總是可能的，那么我們?nèi)绻@種排列不總是可能的，那么我們要

18、問，要問，這種這種組合數(shù)學(xué)21排列在什么樣的排列在什么樣的(必要和充分必要和充分)條件下能夠?qū)崿F(xiàn)？條件下能夠?qū)崿F(xiàn)？ 排列的計(jì)數(shù)和分類：如果一個(gè)指定的排列是可排列的計(jì)數(shù)和分類：如果一個(gè)指定的排列是可能的，那么就會(huì)存在多種方法去實(shí)現(xiàn)它。此時(shí)，能的，那么就會(huì)存在多種方法去實(shí)現(xiàn)它。此時(shí)，人們就可以計(jì)數(shù)并將它們分類。人們就可以計(jì)數(shù)并將它們分類。 研究一個(gè)已知的排列：當(dāng)人們建立起滿足某些研究一個(gè)已知的排列：當(dāng)人們建立起滿足某些指定條件的一個(gè)排列指定條件的一個(gè)排列(可能不容易可能不容易)以后，可能要以后，可能要考察這個(gè)排列的性質(zhì)和結(jié)構(gòu)?？疾爝@個(gè)排列的性質(zhì)和結(jié)構(gòu)。組合數(shù)學(xué)22 這樣的結(jié)構(gòu)可能會(huì)涉及到分類問題，

19、也許還這樣的結(jié)構(gòu)可能會(huì)涉及到分類問題，也許還涉及到一些潛在的應(yīng)用，它還可能牽扯到下面涉及到一些潛在的應(yīng)用，它還可能牽扯到下面的問題。的問題。 構(gòu)造一個(gè)最優(yōu)的排列：如果有可能存在多構(gòu)造一個(gè)最優(yōu)的排列：如果有可能存在多于一個(gè)的排列，人們也許想要確定滿足某些優(yōu)于一個(gè)的排列，人們也許想要確定滿足某些優(yōu)化準(zhǔn)則的一個(gè)排列，即找出某種規(guī)定意義下的化準(zhǔn)則的一個(gè)排列，即找出某種規(guī)定意義下的“最好的最好的”或或“最優(yōu)的最優(yōu)的”的排列的排列。組合數(shù)學(xué)23 因此，組合數(shù)學(xué)可以一般地描述為：組合數(shù)因此，組合數(shù)學(xué)可以一般地描述為：組合數(shù)學(xué)是研究離散結(jié)構(gòu)的學(xué)是研究離散結(jié)構(gòu)的存在、計(jì)數(shù)、分析和優(yōu)存在、計(jì)數(shù)、分析和優(yōu)化化等問題

20、的一門學(xué)科。等問題的一門學(xué)科。 雖然某些離散結(jié)構(gòu)是無限的，但本書一雖然某些離散結(jié)構(gòu)是無限的，但本書一般把離散視為般把離散視為有限的有限的。 組合數(shù)學(xué)24 一、問題描述一、問題描述 假設(shè)有一張普通國(guó)際假設(shè)有一張普通國(guó)際象棋棋盤和象棋棋盤和32張張domino牌，其形狀如下牌，其形狀如下:88象象棋棋盤棋棋盤, , 一張一張12格的格的多多米諾牌米諾牌 domino 牌。牌。第一章第一章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué) 1.1 棋盤的完美覆蓋棋盤的完美覆蓋組合數(shù)學(xué)25 每張牌恰好覆蓋棋盤上相鄰的兩個(gè)方格。每張牌恰好覆蓋棋盤上相鄰的兩個(gè)方格。 問題（棋盤的完美覆蓋問題）：是否能夠把問題（棋盤的完美覆蓋

21、問題）：是否能夠把32張張domino牌擺放在棋盤上，使得任何兩張牌擺放在棋盤上，使得任何兩張domino牌均不重疊，每張牌均不重疊，每張domino牌覆蓋兩個(gè)牌覆蓋兩個(gè)方格，并且棋盤上所有方格都被覆蓋??？如果方格，并且棋盤上所有方格都被覆蓋??？如果存在這種完美覆蓋，那么總共有多少種不同的存在這種完美覆蓋，那么總共有多少種不同的完美覆蓋？完美覆蓋？結(jié)論：國(guó)際象棋棋盤的不同的完美結(jié)論：國(guó)際象棋棋盤的不同的完美覆蓋總共有：覆蓋總共有： 249012 = 12988816種種組合數(shù)學(xué)26 這種普通的國(guó)際象棋棋盤可以用排成這種普通的國(guó)際象棋棋盤可以用排成m行行n列的列的mn個(gè)方格的一般棋盤代替。此時(shí)，

22、這種個(gè)方格的一般棋盤代替。此時(shí)，這種棋盤的完美覆蓋就未必存在了。比如，棋盤的完美覆蓋就未必存在了。比如，3行行3列列的棋盤就確實(shí)不存在完美覆蓋。那么，對(duì)于什的棋盤就確實(shí)不存在完美覆蓋。那么，對(duì)于什么樣的么樣的m和和n存在完美覆蓋呢存在完美覆蓋呢?不難看出，當(dāng)且不難看出，當(dāng)且僅當(dāng)僅當(dāng)m和和n中至少有一個(gè)是偶數(shù)時(shí)中至少有一個(gè)是偶數(shù)時(shí),mn棋盤存棋盤存在完美覆蓋?；蛘哒f，當(dāng)且僅當(dāng)棋盤的方格數(shù)在完美覆蓋。或者說，當(dāng)且僅當(dāng)棋盤的方格數(shù)是偶數(shù)時(shí)，是偶數(shù)時(shí)， mn棋盤存在完美覆蓋。棋盤存在完美覆蓋。組合數(shù)學(xué)27 再來考查用再來考查用12格的格的多米諾多米諾骨牌覆蓋去掉骨牌覆蓋去掉了兩個(gè)對(duì)角處格子的了兩個(gè)對(duì)角

23、處格子的88殘缺棋盤，問能否殘缺棋盤，問能否用用31枚骨牌完美覆蓋？枚骨牌完美覆蓋？ 答案是否定的。證明方法很巧妙，可以答案是否定的。證明方法很巧妙，可以先將先將88棋盤黑白間隔染色，去掉的兩個(gè)對(duì)棋盤黑白間隔染色，去掉的兩個(gè)對(duì)角處格子不是同白，就是同黑。因此，角處格子不是同白，就是同黑。因此，88殘缺棋盤剩余的殘缺棋盤剩余的64-2=62個(gè)格子中黑格數(shù)與白個(gè)格子中黑格數(shù)與白格數(shù)相差為格數(shù)相差為2。反之，。反之，組合數(shù)學(xué)28白白白白白白白白白白白白白白白白白白黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑黑 若設(shè)能用若設(shè)能用31枚枚12格的骨牌，若每枚覆蓋格的骨牌，若每枚覆蓋相鄰的相鄰的2個(gè)方格，恰將殘

24、缺棋盤砌滿，個(gè)方格，恰將殘缺棋盤砌滿，組合數(shù)學(xué)29 則黑格數(shù)與白格數(shù)應(yīng)該相等。這就產(chǎn)生了則黑格數(shù)與白格數(shù)應(yīng)該相等。這就產(chǎn)生了矛盾。因此，不存在要求的覆蓋。如果對(duì)不矛盾。因此，不存在要求的覆蓋。如果對(duì)不去掉對(duì)角處格子的去掉對(duì)角處格子的64格格88完好棋盤，則存完好棋盤，則存在用在用32枚枚12格的骨牌恰將其覆蓋的許多方格的骨牌恰將其覆蓋的許多方法。這時(shí)要討論的就是確定有多少種不同覆法。這時(shí)要討論的就是確定有多少種不同覆蓋方法的計(jì)數(shù)問題。蓋方法的計(jì)數(shù)問題。 32 黑黑 +30白白31 黑黑 白白組合數(shù)學(xué)30第一章第一章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué) 1.2 切割立方體切割立方體 1.2 切割立方體

25、切割立方體 把一個(gè)把一個(gè)333的立方體木塊切割成的立方體木塊切割成27個(gè)個(gè)111的小立方塊。如果切割過程中允許重新的小立方塊。如果切割過程中允許重新排列已切割木塊的位置，求完成整個(gè)切割的最排列已切割木塊的位置，求完成整個(gè)切割的最 少次數(shù)。少次數(shù)。 這里的最優(yōu)即指具有最少切割次數(shù)的方案，這里的最優(yōu)即指具有最少切割次數(shù)的方案，組合數(shù)學(xué)31 采用窮舉方案并比較切割次數(shù)的方法一采用窮舉方案并比較切割次數(shù)的方法一般不可取。般不可取。 本例的解法是先指出本例的解法是先指出6次即可完成次即可完成全部切割，即水平切全部切割，即水平切2次，豎直、交叉各切次，豎直、交叉各切2次。其次，次。其次， 可以證明少于可以

26、證明少于6次不能完成題目要次不能完成題目要求的切割。事實(shí)上，對(duì)中心位置產(chǎn)生的小立求的切割。事實(shí)上，對(duì)中心位置產(chǎn)生的小立方體而言，因其也具有方體而言，因其也具有6個(gè)面且每個(gè)面都須被個(gè)面且每個(gè)面都須被獨(dú)立地切割一次才能出現(xiàn)。故至少需要獨(dú)立地切割一次才能出現(xiàn)。故至少需要6次才次才能切割完，見書中能切割完，見書中P5。組合數(shù)學(xué)32第一章第一章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué) 1.3 幻方幻方 1.3 幻方幻方 幻方也稱為幻方也稱為洛書洛書、河圖河圖等，傳說大禹治水時(shí)，等，傳說大禹治水時(shí)，從河中浮起一只烏龜，烏龜?shù)谋成袭嬘幸粋€(gè)從河中浮起一只烏龜，烏龜?shù)谋成袭嬘幸粋€(gè)33 的九個(gè)方格子，格子中填有從的九個(gè)方格

27、子，格子中填有從1,29九個(gè)數(shù)，填九個(gè)數(shù)，填寫的規(guī)則是：橫、豎、斜各自格子中數(shù)之和相等。寫的規(guī)則是：橫、豎、斜各自格子中數(shù)之和相等。組合數(shù)學(xué)33 左圖稱為左圖稱為幻方幻方，右圖右圖稱為稱為幻圓幻圓，觀察幻圓，觀察幻圓的數(shù)字結(jié)構(gòu)，的數(shù)字結(jié)構(gòu)，紫色紫色框里的數(shù)字之差的絕對(duì)值相框里的數(shù)字之差的絕對(duì)值相等；沿等；沿藍(lán)色線藍(lán)色線的數(shù)字之和相等。大家有精力也的數(shù)字之和相等。大家有精力也能再找出其他的數(shù)字關(guān)系來。能再找出其他的數(shù)字關(guān)系來。492357816組合數(shù)學(xué)34 一個(gè)一個(gè)n階幻方是由數(shù)字階幻方是由數(shù)字1，2，3，n2組組成的成的nn方陣，使得方陣中每行上的數(shù)字和、方陣，使得方陣中每行上的數(shù)字和、每列上

28、的數(shù)字和以及每條對(duì)角線上的數(shù)字和均每列上的數(shù)字和以及每條對(duì)角線上的數(shù)字和均等于同一個(gè)數(shù)等于同一個(gè)數(shù)S。稱。稱S為該幻方的為該幻方的幻和幻和。 中國(guó)歷史上研究中國(guó)歷史上研究33 = 9幻方也稱為幻方也稱為“九宮九宮填數(shù)填數(shù)”；組合數(shù)學(xué)35一個(gè)一個(gè)n階幻方中所有數(shù)字的和為：階幻方中所有數(shù)字的和為：1 + 2 + 3 + + n2 = =nS故它的幻和為故它的幻和為 S = 正好是一行正好是一行(列列)上數(shù)字的和，從而上數(shù)字的和，從而, 關(guān)于幻方的問題可歸結(jié)為關(guān)于幻方的問題可歸結(jié)為: 2) 1(22nn2) 1(2nn組合數(shù)學(xué)36(1) 對(duì)任意的正整數(shù)對(duì)任意的正整數(shù)n，n階幻方存在嗎？階幻方存在嗎？

29、(2) 對(duì)某個(gè)正整數(shù)對(duì)某個(gè)正整數(shù)n，如果，如果n階幻方存在，有多階幻方存在，有多少不同的形式？少不同的形式？(3) 構(gòu)造存在的構(gòu)造存在的n階幻方。階幻方。注意，給出一種算法，不僅要描述算法的步注意，給出一種算法，不僅要描述算法的步驟，而且要證明算法的正確性，并對(duì)算法驟，而且要證明算法的正確性，并對(duì)算法進(jìn)行時(shí)間分析。進(jìn)行時(shí)間分析。 組合數(shù)學(xué)37 下面是構(gòu)造的下面是構(gòu)造的7階幻方，幻和為階幻方，幻和為175 ：30394811019283847791827294668172635375141625343645131524334244421233241433122231404921120組合數(shù)學(xué)38

30、 不難看出，不可能存在不難看出，不可能存在2階幻方；階幻方； 夠成幻方的方陣轉(zhuǎn)置后仍然是個(gè)幻方。夠成幻方的方陣轉(zhuǎn)置后仍然是個(gè)幻方。 本書中給出了本書中給出了n為奇數(shù)時(shí)構(gòu)造幻方的方法為奇數(shù)時(shí)構(gòu)造幻方的方法和立體幻方的概念，由于時(shí)間和難度的關(guān)系，和立體幻方的概念，由于時(shí)間和難度的關(guān)系，我們就不用再討論。我們就不用再討論。3332(1+n )nn(1+n )n =22組合數(shù)學(xué)39第一章第一章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué) 1.4 四色問題四色問題 1.4 四色問題四色問題 在一張地圖中每個(gè)國(guó)家均是一個(gè)連通在一張地圖中每個(gè)國(guó)家均是一個(gè)連通的區(qū)域，現(xiàn)對(duì)地圖中的每個(gè)國(guó)家著色，使得的區(qū)域，現(xiàn)對(duì)地圖中的每個(gè)國(guó)

31、家著色，使得具有共同邊界的兩個(gè)國(guó)家涂成不同的顏色，具有共同邊界的兩個(gè)國(guó)家涂成不同的顏色，完成這項(xiàng)工作至少需要幾種顏色？在離散數(shù)完成這項(xiàng)工作至少需要幾種顏色？在離散數(shù)學(xué)中我們利用對(duì)偶圖已經(jīng)證明用學(xué)中我們利用對(duì)偶圖已經(jīng)證明用5種顏色可種顏色可以對(duì)地圖著色。以對(duì)地圖著色。組合數(shù)學(xué)40四色定理敘述起來簡(jiǎn)單，理解起來容易，它與四色定理敘述起來簡(jiǎn)單，理解起來容易，它與著名的三等分角問題一樣著名的三等分角問題一樣吸引著眾多的非專業(yè)人員。吸引著眾多的非專業(yè)人員。1890年年heawood證明了用證明了用5種顏色對(duì)任何地圖著色。種顏色對(duì)任何地圖著色。 42 31組合數(shù)學(xué)41第一章第一章 什么是組合數(shù)學(xué)什么是組合

32、數(shù)學(xué) 1.5 36軍官問題與拉丁方軍官問題與拉丁方 1.5 36軍官問題與拉丁方軍官問題與拉丁方 設(shè)有設(shè)有6個(gè)不同軍銜和來自個(gè)不同軍銜和來自6個(gè)不同團(tuán)隊(duì)的個(gè)不同團(tuán)隊(duì)的36名名軍官，問能否將他們排成軍官，問能否將他們排成66方陣，使得每行方陣，使得每行每列均有各種軍銜的軍官每列均有各種軍銜的軍官1名，并且每行和每列名，并且每行和每列上的不同軍銜的上的不同軍銜的6名軍官還分別來自不同的軍團(tuán)？名軍官還分別來自不同的軍團(tuán)？組合數(shù)學(xué)42 我們把一個(gè)軍官表示為一個(gè)序偶（我們把一個(gè)軍官表示為一個(gè)序偶（i，j），），其中其中i表示該軍官的軍銜（表示該軍官的軍銜（i1，2，6），），而而j表示他所在的軍團(tuán)（表示

33、他所在的軍團(tuán)（j1，2，6），于），于是上述是上述36軍官問題可用數(shù)學(xué)語言描述成：軍官問題可用數(shù)學(xué)語言描述成： 36個(gè)序偶（序偶（i，j）能否排成）能否排成66方陣，使得方陣，使得這這6個(gè)整數(shù)都能分別以某種順序出現(xiàn)在序偶的第個(gè)整數(shù)都能分別以某種順序出現(xiàn)在序偶的第一個(gè)或第二個(gè)元素位置上？一個(gè)或第二個(gè)元素位置上？組合數(shù)學(xué)43 或者：是否存在這樣的兩個(gè)或者：是否存在這樣的兩個(gè)66矩陣，其矩陣，其元素取自元素取自1，2，6，使得，使得 1整數(shù)整數(shù)1，2，6以某種順序出現(xiàn)在矩陣以某種順序出現(xiàn)在矩陣的每一行和每一列；的每一行和每一列； 2當(dāng)這兩個(gè)矩陣并置時(shí)，所有當(dāng)這兩個(gè)矩陣并置時(shí)，所有36序偶（序偶（i，

34、j） （i1，2，6）全部出現(xiàn)。）全部出現(xiàn)。組合數(shù)學(xué)44213132321132213321)2, 1)(1 , 3)(3,2()1 ,2)(3, 1)(2, 3()3, 3)(2,2)(1 , 1(軍團(tuán)矩陣軍團(tuán)矩陣軍銜矩陣軍銜矩陣 以以9名軍官為例，設(shè)名軍官為例，設(shè)i=1, 2, 3表示軍官的軍表示軍官的軍銜，銜，j=1, 2, 3 表示軍官的團(tuán)隊(duì)，則每個(gè)軍官對(duì)表示軍官的團(tuán)隊(duì)，則每個(gè)軍官對(duì)應(yīng)一個(gè)序偶應(yīng)一個(gè)序偶(i, j)。從而可以排出：。從而可以排出：組合數(shù)學(xué)45分別 我們把具有上述性質(zhì)我們把具有上述性質(zhì)1的兩個(gè)的兩個(gè)66矩陣均稱矩陣均稱為為6 6階階拉丁方拉丁方。這兩個(gè)。這兩個(gè)6階拉丁方若同時(shí)具有階拉丁方若同時(shí)具有上述性質(zhì)上述性質(zhì)2，則稱它們是，則稱它們是正交的正交的。 于是于是36軍官問題又可描述為：是否存在兩軍官問題又可描述為：是否存在兩個(gè)正交的個(gè)正交的6階拉丁方？階拉丁方？組合數(shù)學(xué)46第一章第一章 什么是組合數(shù)學(xué)什么是組合數(shù)學(xué) 1.6 最短路徑問題最短路徑問題 (14) 1.6 最短路徑問題