組合數(shù)學(xué)第1章

1、組合數(shù)學(xué),主講教師：馮子玹,關(guān)于教材,內(nèi)部試用版本 地點：計算機(jī)大樓 A413 價格：每本20元 組織：請各班班長帶著本班的教材費前來領(lǐng)取 參考書： 機(jī)械工業(yè)出版社：組合數(shù)學(xué)，布魯?shù)?(Brualdi R.A.) (作者), 馮舜璽 (譯者) 清華大學(xué)出版社：組合數(shù)學(xué)，盧開澄等,引言,組合數(shù)學(xué)(簡稱組合學(xué))是數(shù)學(xué)的一個分支, 它起源于古代的娛樂和休閑游戲. 后來這些問題逐漸與數(shù)論、概率統(tǒng)計、拓?fù)鋵W(xué)、線性規(guī)劃等學(xué)科的問題交織在一起，逐漸形成一種理論. 計算機(jī)出現(xiàn)以后，由于離散對象的處理是計算機(jī)科學(xué)的核心，研究離散對象的組合數(shù)學(xué)得到迅猛發(fā)展.,怎樣學(xué)好組合數(shù)學(xué),主要方法：數(shù)學(xué)歸納法、反證法、計數(shù)時

2、的合理分類、組合模型的轉(zhuǎn)換、組合分析. 要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進(jìn)行相當(dāng)?shù)挠?xùn)練.,主要內(nèi)容 基本介紹 鴿巢原理和Ramsey定理（存在性問題） 基本計數(shù)方法 容斥原理 生成函數(shù) 遞推關(guān)系 Plya定理,計 數(shù),組合數(shù)學(xué)的應(yīng)用,地圖著色問題：對世界地圖著色，每一個國家使用一種顏色.如果要求相鄰國家的顏色相異，是否總共只需四種顏色？這是圖論問題. 船夫過河問題：船夫要把一匹狼、一只羊和一棵白菜運過河. 只要船夫不在場，羊就會吃白菜、狼就會吃羊.船夫的船每次只能運送一種東西.怎樣把所有東西都運過河？這是線性規(guī)劃問題.,中國郵差問題：由中國組合數(shù)學(xué)家管梅谷教授提出.郵遞員從郵

3、局出發(fā)送信，要求對轄區(qū)內(nèi)每條街，都至少通過一次，再回郵局.怎樣行走走過的路程最短？ 著名的組合數(shù)學(xué)家 Thomas Tutte 從德軍的兩條情報密碼出發(fā)，用組合數(shù)學(xué)的方法,重建了敵人的密碼機(jī)，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報.,8,組合數(shù)學(xué)的主要問題,將一些物體安排成滿足一定規(guī)則的模式或形態(tài). 存在性問題:滿足一定條件的安排的存在性. 如果某種安排不一定總存在，我們就需要研究存在的條件. 計數(shù)和分類問題:如果所要求的安排存在，則可能有多種不同的安排. 需要計數(shù)不同的方案數(shù)，并對它們進(jìn)行分類.,構(gòu)造性問題: 當(dāng)所要求的模式存在，而且進(jìn)行了計數(shù)和分類，有時我們更希望程序化的方法把

4、相應(yīng)的模式枚舉或構(gòu)造出來. 優(yōu)化問題: 在給定的優(yōu)化條件下從所有的安排方案中找出最優(yōu)的安排方案.,第一章 引言,將一些物體安排成滿足一定規(guī)則的模式或形態(tài). 存在性問題 計數(shù)和分類問題 構(gòu)造性問題 優(yōu)化問題 1.1 幻方問題 1.2 拉丁方問題 1.3 涂色問題,1.1 幻方問題,公元前23世紀(jì)大禹治水時，在洛水中，浮現(xiàn)出一只大烏龜，甲上背有9種花點的圖案，正巧是19這9個數(shù)，其橫的3行、縱的3列以及兩對角線上各自的數(shù)字之和都為15.,幻方：一個n階幻方是由整數(shù)1，2，3，n2按下述方式組成的nn方陣：該方陣每行上的整數(shù)的和、每列上的整數(shù)的和以及兩條對角線中每條對角線上的整數(shù)的和都等于同一個數(shù).

5、 幻和S：每一行（或列或?qū)蔷€）數(shù)字的和.,幻方的問題: 存在性問題 對任意的正整數(shù)n，n階幻方是否存在？ 組合計數(shù)問題 如果存在，那么應(yīng)該有多少個不同的 n階幻方？ 構(gòu)造問題 奇數(shù)階幻方：連續(xù)擺放法 雙偶數(shù)(4k)階幻方：對稱法 單偶數(shù)(4k+2)階幻方：斯特雷奇法（1918）,14,幻方的存在性問題 例1.1 證明不存在2階幻方.,根據(jù)幻方的定義，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因為a1，a2，a3， a4必定彼此不同，矛盾.,證明：反證法. 假定存在2階幻方：,15,幻方的構(gòu)造性問題,奇數(shù)階幻方的構(gòu)造：連續(xù)擺放法. 將1放在(n+1)/2列第1行的方

6、格中； 按照副對角線方向（即行號減1，列號加1）依次把從小到大的各個數(shù)字放入相應(yīng)的方格中； 如果行號變成0（第1行上面一行），則改成第n行相應(yīng)列對應(yīng)的方格； 如果列號變成n+1（第n列右面一列），則改成第1列相應(yīng)行對應(yīng)的方格； 如果輪到的方格已經(jīng)填有數(shù)字或者到了第0行第n+1列對應(yīng)的方格，則退到前一個方格正下方的方格.,16,例1.2 利用連續(xù)擺放法構(gòu)造5階幻方,即行號減1，列號加1,17,偶數(shù)階幻方的構(gòu)造：n=4k 對稱法. 把nn的方陣分成上、下、左、右四個2k2k的方陣； 處理左上的2k2k方陣，每行每列任意取一半(k個)的方格做標(biāo)記，涂成陰影； 按對稱軸將陰影向下和向右作對稱圖形，使得

7、nn的方陣的每一行和每一列都有一半(n/2)的方格被涂成陰影； 從1開始依次填入方格中，第一遍：從第1行第1列的方格開始往右，不是陰影則填數(shù)字，是陰影的方格不填數(shù)字，但相應(yīng)的數(shù)字加1. 第1行填完后填第2行依次到第n行第n列的方格；,18,第二遍：從第n行第n列的方格開始依次往左，規(guī)則同前，從1開始的數(shù)字依次填入，第n行結(jié)束之后是第n-1行第n列的方格，直到第1行第1列的方格.,例1.3 利用對稱法構(gòu)造4階幻方,19,單偶數(shù)階幻方 n=4k+2. 把nn的方陣分成上、下、左、右四個(2k+1)(2k+1)的方陣，編為左上A、右下B、右上C、左下D； 把1(2k+1)2放在A中做成第一個幻方；

8、把 (2k+1)2 12(2k+1)2放在B中成第二個幻方； 把2(2k+1)213(2k+1)2放在C中成第三個幻方； 把3(2k+1)214(2k+1)2放在D中成第四個幻方； 在A的各行從第1列開始向右取m個(m=(n-2)/4)方格，但中間一行（k+1行）從第2列開始；把這些方格中的數(shù)字與D中相應(yīng)位置的數(shù)字對換； 在C中各行最后一列右起向左各取m-1個方格，把這些方格中的數(shù)字與B中相應(yīng)位置的數(shù)字對換.,20,例1.4 構(gòu)造6階幻方,A,B,C,D,21,A,D,B,C,22,幻方的計數(shù)問題,3階幻方: 基本形式只有一種， 經(jīng)過旋轉(zhuǎn)和翻轉(zhuǎn)可獲得8種變形.,1 6 6 1 8 5 7 7

9、5 3 9 2 2 9 4,4階幻方：基本形式有880個，變形有7040個. 5階幻方：基本形式有275305224個. 6階及以上幻方：難以獲得精確的數(shù)字，目前只能估出它取值范圍.,1.2 拉丁方問題,23,n階拉丁方: 由數(shù)字1,2,n構(gòu)成的nn的方陣,使得在每1行、每1列中每個數(shù)字都恰好出現(xiàn)一次. 存在性問題：2階拉丁方存在.,24,n階拉丁方的構(gòu)造方法： 第1行為 1,2,3,n 第2行是 2,3,n,1 第k行為 k,k+1,n,1, ,k-1 第n行為 n,1,2,3,n-1.,25,例1.5 設(shè)計一個藥物臨床試驗以測試五種藥物對人體的藥效. 這五種藥物編號1,2,3,4,5. 然

10、后選取5個人，并給每人不同的藥. 為了消除個體對藥物的反應(yīng)偏差，要求在連續(xù)5天里進(jìn)行測試，每人每天吃一種藥物. 而為了消除服藥時間造成藥效的偏差，要求2個人不能在同1 天吃相同的藥. 解：滿足要求的實驗：由1,2,3,4,5構(gòu)成的55的方陣，其中每行每列中沒有相同的數(shù)字，即5階拉丁方.,26,行（人） 列（天）,n階拉丁方的構(gòu)造方法： 第1行為 1,2,3,n 第2行是 2,3,n,1 第k行為 k,k+1,n,1, ,k-1 第n行為 n,1,2,3,n-1.,5階拉丁方有161280個.,正交拉丁方,例 36軍官問題(Euler) 有36名軍官來自6個不同的軍團(tuán)，共有6種不同的軍銜，他們能否排成一個66的方陣，使得每行每列恰有各種軍銜，并且每行和每列上的不同軍銜的6名軍官還分別來自不同的軍團(tuán)？ 解： (i :軍銜, j :軍團(tuán)), i, j1,6. (1,1) (1,2) (1,3) (1,6) (2,1) (2,2) (2,6) . (6,1) (6,2) (6,6),正交拉丁方： 設(shè)A=(aij)nn, B=(bij)nn是兩個nn拉丁方，令 C=(aij, bij)nn, 若C的n2對數(shù)組互不相同, 則稱A與B正交.,不存在2階正交拉丁方. 36軍官問題即不存在6階正交拉丁方.,30,1.3 涂色問題,實際應(yīng)用中，很多計數(shù)問題都可抽象成涂色問題.