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