1、組合數學1 組合數學組合數學 RichardA.Brualdi 著著 馮舜璽馮舜璽 等等 編譯編譯 機械工業出版社機械工業出版社 任課教師任課教師： 廖廖 虎虎組合數學2 辦公室：軟件學院四樓專業教研室辦公室：軟件學院四樓專業教研室 辦公電話：辦公電話：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 移動電話：移動電話：1 3 0 9 6 9 8 1 1 8 21 3 0 9 6 9 8 1 1 8 2 電子郵件：電子郵件：xaLiaohxaLiaoh 組合數學3緒緒 論論 組合數學是一門古老的數學

2、分支，其思想組合數學是一門古老的數學分支，其思想在社會科學、信息論、生物科學以及其他傳統在社會科學、信息論、生物科學以及其他傳統自然科學領域得到了廣泛的應用。自然科學領域得到了廣泛的應用。組合數學在組合數學在計算機出現以后得以迅速發展。計算機科學就計算機出現以后得以迅速發展。計算機科學就是算法的科學，而計算機所處理的對象是離散是算法的科學，而計算機所處理的對象是離散的數據，所以離散對象的處理就成了計算機的數據，所以離散對象的處理就成了計算機組合數學4 科學的核心，而研究離散對象的科學恰恰就科學的核心，而研究離散對象的科學恰恰就是離散數學和組合數學；組合數學的發展改是離散數學和組合數學；組合數學

3、的發展改變了傳統數學中分析和代數占統治地位的局變了傳統數學中分析和代數占統治地位的局面。現代數學可以分為兩大類：一類是研究面。現代數學可以分為兩大類：一類是研究連續對象的，如分析、方程等，另一類就是連續對象的，如分析、方程等，另一類就是研究離散對象的組合數學。組合數學不僅在研究離散對象的組合數學。組合數學不僅在基礎數學研究中具有極其重要的地位，在其基礎數學研究中具有極其重要的地位，在其它的學科中也有重要的應用，如計算機科學、它的學科中也有重要的應用，如計算機科學、編碼和編碼和組合數學5 密碼學、物理、化學、生物等學科中均有重要密碼學、物理、化學、生物等學科中均有重要應用。微積分和近代數學的發展

4、為近代的工業應用。微積分和近代數學的發展為近代的工業革命奠定了基礎。而組合數學的發展則是奠定革命奠定了基礎。而組合數學的發展則是奠定了本世紀的計算機革命的基礎。計算機之所以了本世紀的計算機革命的基礎。計算機之所以可以被稱為可以被稱為電腦電腦，就是因為計算機被人編寫了，就是因為計算機被人編寫了程序，而程序就是算法，在絕大多數情況下，程序，而程序就是算法，在絕大多數情況下，計算機的算法是針對離散的對象計算機的算法是針對離散的對象，而不是在作而不是在作數值計算。數值計算。 組合數學6 正是因為有了組合算法才使人感到，計算機正是因為有了組合算法才使人感到，計算機好象是有思維的。好象是有思維的。 組合數

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

6、在美計的方法解決工業界中的試驗設計問題，在美國已有專門的公司開發這方面的軟件。最近，國已有專門的公司開發這方面的軟件。最近，德國一位著名組合數學家利用組合數學方法研德國一位著名組合數學家利用組合數學方法研究藥物結構，為制藥公司節省了大量的費用，究藥物結構，為制藥公司節省了大量的費用，引起了制藥業的關注。引起了制藥業的關注。組合數學8 組合數學與計算機軟件 隨著計算機網絡的發展，計算機的使用已隨著計算機網絡的發展，計算機的使用已經影響到了人們的工作，生活，學習，社會活動經影響到了人們的工作，生活，學習，社會活動以及商業活動，而計算機的應用根本上是通過軟以及商業活動，而計算機的應用根本上是通過軟件

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

8、是我國的信息技術的數學基礎十分薄弱，這個問題不解決，我們就難成為軟件強國。這個問題不解決，我們就難成為軟件強國。 組合數學10 然而問題決不是這么簡單，信息技術的發然而問題決不是這么簡單，信息技術的發展已經涉及到了很深的數學知識，而數學本身展已經涉及到了很深的數學知識，而數學本身發展程度并不是單憑幾個聰明的頭腦去想想就發展程度并不是單憑幾個聰明的頭腦去想想就行了，而更重要的是需要集體的合作和力量，行了，而更重要的是需要集體的合作和力量，就象軟件的開發需要多方面的人員的合作。美就象軟件的開發需要多方面的人員的合作。美國的軟件之所以能領先，其關鍵就在于在數學國的軟件之所以能領先，其關鍵就在于在數學

9、基礎上他們有很強的實力，有很多杰出的人才。基礎上他們有很強的實力，有很多杰出的人才。組合數學11 一般人可能會認為數學是一門純粹的基礎科學，一般人可能會認為數學是一門純粹的基礎科學，1+1的解決可能不會有任何實際的意義。如果真的解決可能不會有任何實際的意義。如果真是這樣，一門純粹學科的發展落后幾年，甚至是這樣，一門純粹學科的發展落后幾年，甚至十年，關系也不大。然而中國的軟件產業的發十年，關系也不大。然而中國的軟件產業的發展已向數學基礎提出了急切的需求：網絡算法展已向數學基礎提出了急切的需求：網絡算法和分析、信息壓縮、網絡安全、編碼技術、系和分析、信息壓縮、網絡安全、編碼技術、系統軟件、并行算法

10、、數學機械化和計算機推理統軟件、并行算法、數學機械化和計算機推理組合數學12 等等。此外，與實際應用有關的還有許多許多等等。此外，與實際應用有關的還有許多許多需要數學基礎的算法，如運籌規劃，金融工程，需要數學基礎的算法，如運籌規劃，金融工程，計算機輔助設計等。如果我們的軟件產業還是計算機輔助設計等。如果我們的軟件產業還是把眼光一直盯在應用軟件和第二次開發，那么把眼光一直盯在應用軟件和第二次開發，那么我們在應用軟件這個領域也會讓國外的企業搶我們在應用軟件這個領域也會讓國外的企業搶去很大的市場。如果我們現在在信息技術的數去很大的市場。如果我們現在在信息技術的數學基礎上，大力支持和投入，那將是亡羊補

11、牢，學基礎上，大力支持和投入，那將是亡羊補牢，猶未為晚；猶未為晚； 組合數學13 胡錦濤同志在胡錦濤同志在19981998年接見年接見“五四五四”青年獎青年獎章獲得者時發表的講話中指出：組合數學是不章獲得者時發表的講話中指出：組合數學是不同于傳統的純數學的一個分支，它還是一門應同于傳統的純數學的一個分支，它還是一門應用學科，一門交叉學科。他希望中國的組合數用學科，一門交叉學科。他希望中國的組合數學研究能夠為國家的經濟建設服務。學研究能夠為國家的經濟建設服務。 如果如果2121世紀是信息社會的世紀，那么世紀是信息社會的世紀，那么2121世世紀也必將是組合數學大有可為的世紀。紀也必將是組合數學大有

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

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

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

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

16、支，而且它的影響還在繼續擴大。門重要分支，而且它的影響還在繼續擴大。組合數學自組合數學自6060年代以來急速發展的部分原因年代以來急速發展的部分原因組合數學19 就在于計算機在我們的社會中所發揮的重要就在于計算機在我們的社會中所發揮的重要影響，而且這種影響還在繼續發揮。影響，而且這種影響還在繼續發揮。 組合數學近期發展的另一個原因是它對于組合數學近期發展的另一個原因是它對于那些過去很少與數學正式接觸的學科的適用性。那些過去很少與數學正式接觸的學科的適用性。由此我們發現，組合數學的思想和技巧不僅正在由此我們發現，組合數學的思想和技巧不僅正在用于數學應用的傳統自然科學領域，而且也用于用于數學應用的

17、傳統自然科學領域，而且也用于社會科學、生物科學、信息論等領域。社會科學、生物科學、信息論等領域。組合數學20 組合數學涉及到將一個集合的物體排列成組合數學涉及到將一個集合的物體排列成滿足一些指定規則的格式。如下兩類一般性問滿足一些指定規則的格式。如下兩類一般性問題反復出現：題反復出現：排列的存在性：如果有人想要排列一個集合的排列的存在性：如果有人想要排列一個集合的成員使得某些條件得以滿足，那么這樣一種排成員使得某些條件得以滿足，那么這樣一種排列是否可行就顯而易見的。這是最根本的問題。列是否可行就顯而易見的。這是最根本的問題。如果這種排列不總是可能的，那么我們如果這種排列不總是可能的，那么我們要

18、問，要問，這種這種組合數學21排列在什么樣的排列在什么樣的(必要和充分必要和充分)條件下能夠實現？條件下能夠實現？ 排列的計數和分類：如果一個指定的排列是可排列的計數和分類：如果一個指定的排列是可能的，那么就會存在多種方法去實現它。此時，能的，那么就會存在多種方法去實現它。此時，人們就可以計數并將它們分類。人們就可以計數并將它們分類。 研究一個已知的排列：當人們建立起滿足某些研究一個已知的排列：當人們建立起滿足某些指定條件的一個排列指定條件的一個排列(可能不容易可能不容易)以后，可能要以后，可能要考察這個排列的性質和結構。考察這個排列的性質和結構。組合數學22 這樣的結構可能會涉及到分類問題，

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

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

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

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

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

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

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

26、證明少于6次不能完成題目要次不能完成題目要求的切割。事實上，對中心位置產生的小立求的切割。事實上，對中心位置產生的小立方體而言，因其也具有方體而言，因其也具有6個面且每個面都須被個面且每個面都須被獨立地切割一次才能出現。故至少需要獨立地切割一次才能出現。故至少需要6次才次才能切割完，見書中能切割完，見書中P5。組合數學32第一章第一章 什么是組合數學什么是組合數學 1.3 幻方幻方 1.3 幻方幻方 幻方也稱為幻方也稱為洛書洛書、河圖河圖等，傳說大禹治水時，等，傳說大禹治水時，從河中浮起一只烏龜，烏龜的背上畫有一個從河中浮起一只烏龜，烏龜的背上畫有一個33 的九個方格子，格子中填有從的九個方格

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

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

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

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

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

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

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

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