【正文】 的。淺談組合數(shù)學 組合數(shù)學概述 ? 現(xiàn)代數(shù)學根據(jù)所研究的對象可分為兩類： 連續(xù)數(shù)學：以微積分為基礎(chǔ)，傳統(tǒng)主流； 離散數(shù)學：伴隨計算機科學，方興未艾。 ? 1666年 Leibniz著 《 Dissertatio de arte binatoria》 ,首次使用了組合一詞。 1 1， 1 1， 2， 1 1， 3， 3， 1 1， 4， 6， 4， 1 1， 5， 10， 10， 5， 1 1， 6， 15， 20， 15， 6， 1 七橋問題 ? 近代圖論的歷史可追溯到 18世紀的 七橋問題 —Pregel河橫穿 K246。 拉丁方陣與 正交拉丁方陣 每名軍官對應(yīng)一個有序?qū)Γㄜ妶F，軍銜） 以 9名軍官為例： 軍團陣列 軍銜陣列 并置陣列 （拉丁方陣） （拉丁方陣） （ 正交拉丁方陣） 1 2 3 1 2 3 ( 1 , 1 ) ( 2 , 2 ) ( 3 , 3 )3 1 2 2 3 1 ( 3 , 2 ) ( 1 , 3 ) ( 2 , 1 )2 3 1 3 1 2 ( 2 , 3 ) ( 3 , 1 ) ( 1 , 2 )? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? 36 軍官問題 (歐拉 1779) The Great Frederic的閱兵難題 歐拉的困惑 拉丁方陣 : 1221??????1 2 32 3 13 1 2????????1 2 4 32 3 1 43 4 2 14 1 3 2????????????正交拉丁方陣 : 1 2 33 1 22 3 1????????1 2 32 3 13 1 2????????1 2 33 1 2231 2 32 3 131 1 2????????Euler 猜想 ? 不存在 6階正交拉丁方 ? 不存在 4k+2階正交拉丁方 現(xiàn)在的結(jié)論 ? 對任正整數(shù) n≠2,6， 存在 n 階正交拉丁方 四色問題 ? 在日常生活中我們常?？梢杂龅浇M合數(shù)學的問題。五色定理。 ? 五個點的則不然。s ? 1997年 Fulkerson獎得主 Kim ? 1998年 Fields獎得主 Gowers ? 1999年 Wolf獎得主 Lovasz ? 2022年 Steele獎得主 Graham ? 2022年 G246。 穩(wěn)定的婚姻問題 ? 組合數(shù)學中有一個著名定理：如果一個村子里每一個女孩都恰好認識 k個男孩，并且每一個男孩也恰好認識 k個女孩，那么每一個女孩都可以嫁給她認識的一個男孩，并且每一個男孩都可以娶一個他認識的女孩。 ? 例如 914的模式為： 312 37925 的模式為： 24513 棧排序問題 (Knuth, 1960’s) ? 避免３１２排列 ：一個排列是避免３１２的，當且僅當它的任意子序列中沒有３１２模式。 應(yīng)用促進理論發(fā)展 ? 36個軍官問題這個純粹來自智力游戲的題目孕育著艱深的數(shù)學問題 。其本質(zhì)就是如何將一個集合中的元素組合成一定的子集系以滿足一定的要求。 網(wǎng)絡(luò)流問題 ? 1956年 Ford 和 Fulkerson 提出了關(guān)于網(wǎng)絡(luò)流問題的一個重要定理。最短新路徑之長 N比原來只連三點的最短路徑 O要短。asi et ，任意兩個網(wǎng)頁間的鏈接最多為 19次。 ? “ 二、九、四；七、五、三；六、一、八 ” 《 大戴禮記 楊輝三角 ? 楊輝（南宋）著 《 詳解九章算法 》 (1261年 )中曾引賈憲（北宋）的 “ 開方作法本源 ”圖。sKoRado定理 ? FranklGraham： Erd246。 中國郵遞員問題 ? 管梅谷（ 1960）： 郵遞員從郵局出發(fā)送信，要求對轄區(qū)內(nèi)每條街都至少通過一次再回郵局，怎樣選擇一條最短路線 ? ? 現(xiàn)實生活中很多問題可以轉(zhuǎn)化為中國郵遞員問題。 機器證明 —— 吳消元法 ? 1976年 吳文俊 教授開始進行研究幾何定理的機器證明，并在很短的時間內(nèi)取得重大突破。 ——當符合要求的安排并非顯然存在或不存在時，首要的問題是證明或否定它的存在 . ——當符合要求的安排顯然存在，或者已證明它存在時，求出這類安排的各抒己見，或者把它分類 . （組合設(shè)計） ——把滿足某種條件的安排構(gòu)造出來 . ——給出最優(yōu)標準，找出滿足給定條件的最優(yōu)安排 . 組合數(shù)學的分支 ? 組合分析 ? 代數(shù)組合 ? 極值集論 ? 圖 論 ? 組合設(shè)計 ? 組合優(yōu)化 ? 組合算法