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

組 合 數(shù) 學(xué)吉 林 大 學(xué)計 算 機 科 學(xué) 與 技 術(shù) 學(xué) 院2009年 9月 2021年5月3日2 參 考 教 材組合數(shù)學(xué)，屈婉玲編。北京大學(xué)出版社，1989年11月。組合數(shù)學(xué)（第四版），盧開澄等。清華大學(xué)出版社， 2006年12月。組合數(shù)學(xué)(英文版第5版) ，(美)布魯?shù)?Brualdi,R.A.)著。機械工業(yè)出版社，2009年3月。 2021年5月3日3 第一章 引言計算機算法數(shù)值計算如： 解方程組， 求積分等非數(shù)值計算 如：搜索，排序， 組合優(yōu)化等高等數(shù)學(xué)組合數(shù)學(xué) 2021年5月3日4 一、什么是組合數(shù)學(xué) 二、組合數(shù)學(xué)的主要內(nèi)容 三、組合數(shù)學(xué)的幾個例子 四、組合數(shù)學(xué)的學(xué)習(xí)方法 四色問題對世界地圖著色，每一個國家使用一種顏色，那么只需要四種顏色就能保證每兩個相鄰的國家的顏色不同 2021年5月3日5 裝箱問題當(dāng)你裝一個箱子時，你會發(fā)現(xiàn)要使箱子盡可能裝滿不是一件很容易的事，你往往需要做些調(diào)整。從理論上講，裝箱問題是一個很難的組合數(shù)學(xué)問題，即使用計算機也是不容易解決的。 2021年5月3日6 過河問題一個船夫要把一只狼，一只羊和一棵白菜運過河。問題是當(dāng)人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個。他怎樣才能把三者都運過河呢？ 2021年5月3日7 2021年5月3日8 一個郵遞員從郵局出發(fā) ，再返回郵局，如果他必須走過他所管轄的每條街道至少一次，問如何選擇路線，使得路程最短？中國郵路問題 2021年5月3日9 n階幻方 把1，2，n2這n2個數(shù)字排成nn的方陣，并使得每一行、每一列、每一條對角線上的n個數(shù)字之和都相等，稱這樣的方陣為n階幻方，又稱為縱橫圖。 棋盤完美覆蓋問題 2021年5月3日10 2021年5月3日11 Combinatorics 1666年萊布尼茲所著組合學(xué)論文一書問世，這是組合數(shù)學(xué)第一部專著。一、什么是組合數(shù)學(xué) 2021年5月3日12 組合數(shù)學(xué)是研究事物在給定模式下的配置，研究這種配置的存在性，所有可能配置的計數(shù)和分類，以及配置的各種性質(zhì)。 2021年5月3日13 二、組合數(shù)學(xué)的主要內(nèi)容 (1)組合分析，基礎(chǔ)，為后面的討論作準備。主要研究存在性問題、組合計數(shù)問題、構(gòu)造或枚舉問題。(2)組合優(yōu)化，討論線性規(guī)劃及整數(shù)規(guī)劃問題。(3)組合設(shè)計， 是將集合的元素分成滿足某些所述性質(zhì)的子集的排列方法。 (4)組合算法，如：搜索法。動態(tài)規(guī)劃。優(yōu)先策略與分治策略。分類與查找，重點在于算法的分析。 2021年5月3日14 本學(xué)期涉及到的內(nèi)容：鴿巢原理和Ramsey定理（存在性問題）排列和組合二項式系數(shù)包含排斥原理遞推關(guān)系生成函數(shù)Polya定理組合計數(shù)問題 2021年5月3日15 組合數(shù)學(xué)應(yīng)用領(lǐng)域 1，計算機科學(xué) 2，管理科學(xué) 3，信息科學(xué) 4，電子工程 5，人工智能 6，生命科學(xué) 2021年5月3日16 2021年5月3日17 (1) 存在性問題對于模式要證明或否定它的存在(2)計數(shù)和分類問題 討論對不同的方案進行計數(shù)，并對它們進行分類問題 2021年5月3日18 (3) 構(gòu)造性問題 通過程序化的方法把相應(yīng)的模式枚舉或構(gòu)造出來(4) 優(yōu)化問題 尋找滿足某種標(biāo)準下“最好”或“最優(yōu)”的一個模式 2021年5月3日19 一個3階方陣，其元素是1到9的正整數(shù)，每行、每列以及兩條對角線的和都是15。 楊 輝 稱其 為 縱 橫 圖 ， 在 著 詳 解 九 章算 法 （ 1261年 ） 中 曾 研 究 三階 幻 方 ， 并 給 出 它 的 構(gòu) 造 方 法還 給 出 了 4至 10階 的 幻 方 。 5193 7248 6三、組合數(shù)學(xué)的幾個例子l1.1 幻方問題 1 2 35 647 8 9 9 2 75 643 8 19 275 6438 1 9 2 75 643 8 1九 子 斜 排 ， 上 下 對 易 ，左 右 相 更 ， 四 維 挺 出 ，戴 九 履 一 ， 左 三 右 七 ，二 四 為 肩 ， 六 八 為 足 2021年5月3日21 一個n階幻方是由整數(shù)1，2，3，n2按下述方式組成的nn方陣：該方陣每行上的整數(shù)的和、每列上的整數(shù)的和以及兩條對角線中每條對角線上的整數(shù)的和都等于同一個數(shù)s 2021年5月3日22 3階幻方的所有整數(shù)和為15； 2階幻方的所有整數(shù)和為5； 每一行（或列或?qū)蔷€）數(shù)字的和稱為幻方的和（幻和）： S= n (n2+1)/2 。 2021年5月3日23 關(guān)于幻方的問題歸結(jié)為：（1）存在性問題 對任意的正整數(shù)n，n階幻方存在嗎？（2）組合計數(shù)問題 如果存在，那么應(yīng)該有多少個不同的n階幻方。（3）構(gòu)造問題 怎樣構(gòu)造n階幻方？ 2021年5月3日24 幻方的存在性問題 例1.1 證明不存在2階幻方。對其余的正整數(shù)n，由于n階幻方都能構(gòu)造出來，當(dāng)然就證明了（正整數(shù)）階幻方的存在性。 2021年5月3日25 例 1.1 證明不存在2階幻方證明：反證法。假定存在2階幻方，如圖所示：a1 a2a3 a4根據(jù)幻方的定義，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因為a1，a2，a3， a4必定彼此不同，所以不可能，矛盾。因此不存在2階幻方。 2021年5月3日26 幻方的構(gòu)造性問題（1）奇數(shù)階幻方的構(gòu)造連續(xù)擺放法（de la Loubre法）。規(guī)則為：假定構(gòu)造n階（n為奇數(shù)）幻方。首先將1放在 (n+1)/2列第1行的方格中，然后按照副對角線方向（即行號減1，列號加1）依次把從小到大的各個數(shù)字放入相應(yīng)的方格中。 2021年5月3日27 如果行號變成0（第1行上面一行），則改成第n行相應(yīng)列對應(yīng)的方格。如果列號變成n+1（第n列右面一列），則改成第1列相應(yīng)行對應(yīng)的方格。如果輪到的方格已經(jīng)填有數(shù)字或者到了第0行第n+1列對應(yīng)的方格，則退到前一個方格正下方的方格。 2021年5月3日28 例1.2 利用連續(xù)擺放法構(gòu)造5階幻方 17 24 1 8 1523 5 7 14 164 6 13 20 2210 12 19 21 311 18 25 2 9 2021年5月3日29 2021年5月3日30 2021年5月3日31 2021年5月3日32 214 315 81259 211714 310615 13812116594 2021年5月3日33 2021年5月3日34 352021年5月3日 2021年5月3日36 192832 6723334 2621221712 192327101433530 36 29 13 1831 242520151611 2021年5月3日37 1329285 6723334 2621221712 1923271014353313830 36 29 13 184 242520151611 2021年5月3日38 幻方的計數(shù)問題 3階幻方 基本形式只有一種 經(jīng)過旋轉(zhuǎn)和翻轉(zhuǎn)可獲得8種變形 4階幻方 分類枚舉 基本形式有880個 變形有7040個 5階幻方 基本形式有275305224個 6階及以上幻方 即使通過大型計算機的計算仍然難以獲得精確的數(shù)字，目前只能估計出它的取值范圍 392021年5月3日 1.2 拉丁方問題 2021年5月3日40 n階拉丁方定義為由數(shù)字1,2,n構(gòu)成的nn的方陣，使得在每1行、每1列中每個數(shù)字都恰好出現(xiàn)1次。 拉丁方是另一類典型的組合數(shù)學(xué)問題 拉丁方存在性問題 2021年5月3日41 2階拉丁方是存在的 1 22 1 2021年5月3日42 n階拉丁方是存在的 構(gòu)造方法如下：第1行為（1,2,3,n）第2行是(2,3,n,1)，第k行為(k,k+1,n,1, ,k-1)，第n行為（n,3, 2, 1）。 2021年5月3日43 2021年5月3日44 最后滿足要求的實驗是要形成由1,2,3,4,5構(gòu)成的55的方陣，其中每行每列中沒有相同的數(shù)字，即5階拉丁方的構(gòu)造問題。 2021年5月3日45 23451 34512 45123 5123412345 正交拉丁方 2021年5月3日46 將兩個n階拉丁方重疊在一起時，所有t2個組合各出現(xiàn)一次，則稱這兩個拉丁方是相互正交的。 2021年5月3日47 )2,1()1,3()3,2( )1,2()3,1()2,3( )3,3()2,2()1,1( 213 132 321132 213 321 2021年5月3日48 36軍官問題 2021年5月3日49 6個軍團6種軍銜36名軍官能否編成方陣，使得每行每列的軍銜不重復(fù)，每行每列的軍團不重復(fù) 2021年5月3日50 2021年5月3日51 )2,1()1,3()3,2( )1,2()3,1()2,3( )3,3()2,2()1,1( 213 132 321132 213 321 2021年5月3日52 2021年5月3日53 )2,1()1,3()3,2( )1,2()3,1()2,3( )3,3()2,2()1,1(213 132 321132 213 321 2021年5月3日54 1.3 涂色問題 在實際應(yīng)用中，很多計數(shù)問題都可抽象成涂色問題。作為典型的組合計數(shù)問題，根據(jù)涂色問題難度的不同，將反映出各種不同的計數(shù)技術(shù)。 2021年5月3日55 例1.6 對正三角形的三個頂點涂以紅、藍（r和b）兩種顏色，求有多少種不同的涂色方案？ 解 由于只有兩種顏色，我們可以采用枚舉方法分類討論。 2021年5月3日56 涂色方案可分成四類：（1）三點全涂紅色，只有一種方案 rrr（2）三點全涂紅色，只有一種方案 bbb（3）兩點涂紅色，一點涂藍色，因藍色可分別涂于三個頂點之一，故有3種方案 brr，rbr，rrb（4）由對稱性可知，兩點涂藍色，一點染紅的方案也有3種： 2021年5月3日57紅色, 藍色 2021年5月3日58 如果考慮正三角形可以旋轉(zhuǎn)，則(3),(4),(5)顯然是同一個涂色方案，(6),(7),(8)也是同一個涂色方案，這樣涂色方案數(shù)就變成了4種。如果變成了空間的四面體了，即加上空間的旋轉(zhuǎn)之后，涂色方法的計算將更加復(fù)雜。要涂色的點和可選顏色的數(shù)目如再增加的話，枚舉方法就不奏效了 一筆畫問題 2021年5月3日59 四、組合數(shù)學(xué)的學(xué)習(xí)方法組合數(shù)學(xué)經(jīng)常使用的方法并不高深復(fù)雜。最主要的方法是計數(shù)時的合理分類和組合模型的轉(zhuǎn)換（一一對應(yīng)）。要學(xué)好組合數(shù)學(xué)并非易事，既需要一定的數(shù)學(xué)修養(yǎng)，也要進行相當(dāng)?shù)挠?xùn)練?？蓮囊?guī)模小的模型著手，從實際出發(fā)分析它，從中找到規(guī)律性的東西，再推及一般。 2021年5月3日60 解題方法一類是常規(guī)方法 從組合學(xué)基本概念、基本定理出發(fā)解題 鴿巢原理、相異代表系定理解存在性問題等等。 利用容斥原理、二項式定理、Polya定理解計數(shù)問題； 特征根方法、生成函數(shù)方法解遞推關(guān)系式； 這類方法通常比較容易掌握， 將在以后各章里分別學(xué)到并學(xué)會它們， 2021年5月3日61 另一類方法，通常與問題所涉及的組合學(xué)概念無關(guān) 1數(shù)學(xué)歸納法， 2. 反證法, 3一一對應(yīng)技術(shù)。把一個組合問題轉(zhuǎn)化成另一個組合問題。 4數(shù)論方法，特別是利用整數(shù)的奇偶性、整除性等效論性質(zhì)進行分析推理的方法。 5殊途同歸方法，即從不同角度討論計數(shù)問題以建立組合等式。 2021年5月3日62 特殊技巧的例子：一一對應(yīng)例1 有101名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問產(chǎn)生冠軍需要進行多少場比賽？ 解2： 因為每場比賽都要產(chǎn)生一個失敗者，而每個失敗者只能失敗一次，所以比賽的場數(shù)與失敗者的人數(shù)相等又因為冠軍是唯一的勝利者，其它100個人都失敗過，所以要比賽100場。解1： 50+25+13+6+3+2+1=100 2021年5月3日63 例2 有一個邊長為3的立方體木塊，要把它切割成27個邊長為1的小立方體，如果在切割的過程中可以重新排列被切割的木塊，證明至少需要6次才能完成任務(wù)？ （分析）設(shè)具有最少切割次數(shù)的方案是最優(yōu)，如果我們先列出所有可能的切割方案，然后從中由出最優(yōu)的方案，這是相當(dāng)麻煩的，我們采用另一種解法 2021年5月3日64 解 首先可以看到6次是可以完成整個切割的左圖就給出了這樣的一種方案； 其次，我們來證明少于6次是不能完成整個切割的因為在27個小立方體中有一個處在原來大立方體的中心，它的每一個面都是由切割而產(chǎn)生的又因為每切一次只能產(chǎn)生一個面，所以切割次數(shù)不能少于它的面數(shù)，因此至少要6次切割才能完成。