基本介紹
- 中文名：組合數學
- 外文名：combinatorics
- 核心內容：用算法處理離散對象
- 套用領域：計算機，程式設計
- 分類：數學
- 包括：廣義 狹義
介紹,國內現狀,國外狀況,主要學術會議,問題,
介紹
有人認為廣義的組合數學就是離散數學，也有人認為離散數學是狹義的組合數學和圖論、代數結構、數理邏輯等的總稱。但這只是不同學者在叫法上的區別，隨著計算機科學的日益發展，組合數學的重要性也日漸凸顯，因為計算機科學的核心內容是使用算法處理離散數據。
組合數學不僅在基礎數學研究中具有極其重要的地位，在其它的學科中也有重要的套用，如計算機科學、編碼和密碼學、物理、化學、生物學等學科中均有重要套用。微積分和近代數學的發展為近代的工業革命奠定了基礎。而組合數學的發展則是奠定了本世紀的計算機革命的基礎。計算機之所以可以被稱為電腦，就是因為計算機被人編寫了程式，而程式就是算法，在絕大多數情況下，計算機的算法是針對離散的對象，而不是在做數值計算。確切地說，組合數學是計算機出現以後迅速發展起來的一門數學分支，主要研究離散對象的存在、計數以及構造等方面問題。由於計算機軟體的促進和需求，組合數學已成為一門既廣博又深奧的學科，其發展奠定了本世紀的計算機革命的基礎，並且改變了傳統數學中分析和代數占統治地位的局面。正是因為有了組合算法才使人感到，計算機好像是有思維的。
組合數學不僅在軟體技術中有重要的套用價值，而且在企業管理、交通規劃、戰爭指揮、金融分析等領域都有重要的套用。在美國有一家用組合數學命名的公司，他們用組合數學的方法來提高企業管理的效益，這家公司辦得非常成功。此外，試驗設計也是具有很大套用價值的學科，它的數學原理就是組合數學。用組合數學的方法解決工業界中的試驗設計問題，在美國已有專門的公司開發這方面的軟體。
國內現狀
1985年9月，中國數學會組合數學與圖論專業委員會成立，標記著中國組合數學學科的形成和創立，並於2001年正式成為中國組合數學與圖論學會。隨著近年來組合數學理論體系的逐步完善和發展，越來越多的學者更加關注這一計算機與數學結合學科的發展。中國數學會組合數學與圖論專業委員會是中國數學會的分支機構，成立於1985年5月。專業委員會的成立得到吳文俊先生的直接關心與支持。首屆專業委員會由25人組成，主任為徐利治。專業委員會成立後，原有的全國組合數學研究會和全國圖論研究會繼續獨立存在，各自組織活動。
直到2001年，兩研究會正式合併成立中國組合數學與圖論學會，同時完成了專業委員會的調整和換屆。專業委員會委員即學會常務理事；專業委員會主任，副主任即學會理事長，副理事長。第一屆專業委員會（學會常務理事會）由26人組成，主任（理事長）為范更華。專業委員會於2004年在新疆烏魯木齊組織召開了首屆全國組合數學與圖論大會（首次以專業委員會的名義將各自舉辦了二十多年的全國性系列會議合二為一），200多位代表參加了這次會議。專業委員會於2004年在福州舉辦了為期三個月的全國性研究生班(由福州大學離散數學研究中心承辦)，邀請海外留學人員利用學術休假回國開設完整的研究生課程，有50多位來自國內14所院校的研究生參加了這期研究生班。專業委員會於2005年在福州舉辦了為期一個月的全國性青年教師研討班(由福州大學離散數學研究中心承辦)，旨在為組合數學與圖論培養後繼人才。
2005年3月在南京師範大學召開的理事長會議上草擬了學會的章程和關於舉辦學術會議的辦法及工作程式，2005年6月在金華召開的第三屆海峽兩岸圖論與組合數學會議上通過了這兩個檔案。2006年8月學會在南開大學召開了第二屆全國組合數學與圖論大會，有400多位代表參加了此次會議。由於第一屆理事會四年任期已滿，會議期間，學會根據章程進行了換屆選舉，南開大學陳永川當選為理事長（專業委員會主任）。
國外狀況
組合數學在國外早已成為十分重要的學科，甚至可以說是計算機科學的基礎。一些大公司，如IBM，AT&T都有全世界最強的組合研究中心。Microsoft的Bill Gates近來也在提倡和支持計算機科學的基礎研究。例如，Bell實驗室的有關線性規劃算法的實現，以及有關計算機網路的算法，由於有明顯的商業價值，顯然是沒有對外公開的。美國已經有一種趨勢，就是與新的算法有關的軟體是可以申請專利的。如果照這種趨勢發展，世界各國對組合數學和計算機算法的投入和競爭必然日趨激烈。美國政府也成立了離散數學及理論計算機科學中心DIMACS（與Princeton大學，Rutgers大學，AT&T 聯合創辦的，設在Rutgers大學），該中心已是組合數學及理論計算機科學的重要研究陣地。
美國國家數學科學研究所（Mathematical Sciences Research Institute，由陳省身先生創立）在1997年選擇了組合數學作為研究專題，組織了為期一年的研究活動。日本的NEC公司還在美國的設立了研究中心，理論計算機科學和組合數學已是他們重要的研究課題，該中心主任R. Tarjan即是組合數學的權威。美國重要的國家實際室（Los Alamos國家實驗室，以造出第一顆核子彈著稱於世），從曼哈頓計畫以來一直重視套用數學的研究，包括組合數學的研究。不僅如此，該實驗室最近還在積極充實組合數學方面的研究實力。美國另外一個重要的國家實驗室Sandia國家實驗室有一個專門研究組合數學和計算機科學的機構，主要從事組合編碼理論和密碼學的研究，在美國政府以及國際學術界都具有很高的地位。
由於生物學中的DNA的結構和生物現象與組合數學有密切的聯繫，各國對生物信息學的研究都很重視，這也是組合數學可以發揮作用的一個重要領域。由於DNA就是組合數學中的一個序列結構，美國科學院院士，近代組合數學的奠基人Rota教授預言，生物學中的組合問題將成為組合數學的一個前沿領域。
傳統的計算機算法可以分為兩大類，一類是組合算法，一類是數值算法（包括計算數學和與處理各種信息數據有關的信息學）。近年來計算機算法又多了一類：那就是符號計算算法。吳文俊院士開創的機器證明方法就屬於符號計算，引起了國際上的高度評價，被稱為吳方法。而國際上還有專門的符號計算雜誌。符號算法和吳方法跟代數組合學也有十分密切的聯繫。組合數學，數值計算（包括計算數學，科學計算，非線性科學，和與處理各種信息數據有關的信息學）和統計學可能是套用最廣的數學分支，而組合數學的價值甚至不亞於統計學和數值計算。由於數學機械化近年來的發展和在計算機科學中的重要性，把數學機械化，科學計算和組合數學組合起來，就可以說是中國信息產業的基礎。組合數學家H. Wilf和D. Zeilberger1998因為在組合恆等式的機械化證明方面的成果，獲得1998年美國數學會的Steele獎。
Thomson Science公司創刊的一份電子刊物《離散數學和理論計算機科學》即是一個很好的說明。它的內容涉及離散數學和計算機科學的眾多方面。由於計算機軟體的促進和需求，組合數學已成為一門既廣博又深奧的學科，需要很深的數學基礎，逐漸成為了數學的主流分支。
除上述以外，歐洲也在積極發展組合數學，英國、法國、德國、荷蘭、丹麥、奧地利、瑞典、義大利、西班牙等國家都建立了各種形式的組合數學研究中心。近幾年，南美國家也在積極推動組合數學的研究。澳大利亞，紐西蘭也組建了很強的組合數學研究機構。值得一提的是亞洲的已開發國家也十分重視組合數學的研究。日本有組合數學研究中心，並且從美國引進人才，不僅支持日本國內的研究，還出資支持美國的有關課題的研究，這樣使日本的組合數學這幾年的發展極為迅速。台灣、香港兩地也從美國引進人才，大力發展組合數學。新加坡，韓國，馬來西亞也在積極推動組合數學的研究和人才培養。台灣的數學研究中心也正在考慮把組合數學作為重點方向來發展。
主要學術會議
屆次 | 時間 | 地點 | 相關信息 | |
1 | 2004年8月6日-8月10日 | 烏魯木齊·新疆大學 | ||
2 | 2006年8月16日-8月18日 | 天津·南開大學 | 大會紀要 | |
3 | 2008年7月20日-7月23日 | 上海·華東師範大學 | ||
4 | 2010年8月16日-8月19日 | 徐州·徐州師範大學（2011年更名為江蘇師範大學） | 大會紀要 | |
5 | 2012年7月16日-7月18日 | 洛陽·洛陽師範學院 | ||
6 | 2014年11月8日-11月10日 | 廣州·華南師範大學 | 大會紀要 | |
7 | 2016年8月14日-8月17日 | 石家莊·河北師範大學 | ||
海峽兩岸圖論與組合數學會議 | ||||
1 | 2001年6月22日-6月27日 | 昆明·雲南大學 | ||
2 | 2002年6月15日-6月19日 | 台北·中研院數學所 | ||
3 | 2005年6月26日-6月30日 | 金華·浙江師範大學 | ||
4 | 2007年6月24日-6月29日 | 台北·台灣大學 | ||
5 | 2009年7月29日-7月31日 | 天津·南開大學 | 大會紀要 | |
6 | 2011年6月27日-6月30日 | 新竹·台灣交通大學 | ||
7 | 2013年6月28日-6月30日 | 長沙·湖南師範大學 | 大會紀要 | |
8 | 2015年6月23日-6月26日 | 高雄·中山大學 | ||
問題
四色問題
如果你仔細留心一張世界地圖，你會發現用一種顏色對一個國家著色，那么一共只需要四種顏色就能保證每兩個相鄰的國家的顏色不同。這樣的著色效果能使每一個國家都能清楚地顯示出來。但要證明這個結論確是一個著名的世界難題，1976年數學家通過計算機運算得到證明而成為四色定理，最近人們才發現了一個更簡單的證明。
中國郵差問題
由中國組合數學家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個NP完全問題。由中國組合數學家管梅谷教授提出，著名組合數學家，J. Edmonds和他的合作者給出了一個解答。
任務分配問題（也稱婚配問題）
有一些員工要完成一些任務。各個員工完成不同任務所花費的時間都不同。每個員工只分配一項任務。每項任務只被分配給一個員工。怎樣分配員工與任務以使所花費的時間最少？
河洛圖
我國古代的河洛圖上記載了三階幻方，即把從一到九這九個數按三行三列的隊行排列，使得每行，每列，以及兩條對角線上的三個數之和都是一十五。組合數學中有許多像幻方這樣精巧的結構。1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。（題圖）
裝箱問題
當你裝一個箱子時，你會發現要使箱子儘可能裝滿不是一件很容易的事，你往往需要做些調整。從理論上講，裝箱問題是一個很難的組合數學問題，即使用計算機也是不容易解決的。
過河問題
在中國小的數學遊戲中，有這樣一個問題，一個船夫要把一隻狼，一隻羊和一棵白菜運過河。問題是當人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個。他怎樣才能把三者都運過河呢？這就是一個很典型、很簡單的組合數學問題。
是否存在穩定婚姻的問題
假如能找到兩對夫婦（如張（男）--李（女）和趙（男）--王（女）），如果張（男）更喜歡王（女），而王（女）也更喜歡張（男），那么這樣就可能有潛在的不穩定性。組合數學的方法可以找到一種婚姻的安排方法，使得沒有上述的不穩定情況出現（當然這只是理論上的結論）。這種組合數學的方法卻有一個實際的用途：美國的醫院在確定錄取住院醫生時，他們將考慮申請者的志願的先後次序，同時也給申請排序。按這樣的次序考慮出的總的方案將沒有醫院和申請者兩者同時後悔的情況。 實際上，高考學生的最後錄取方案也可以用這種方法。
管理調度問題
我們還會遇到更複雜的調度和安排問題。例如，在生產核子彈的曼哈頓計畫中，涉及到很多工序，許多人員的安排，很多元件的生產，怎樣安排各種人員的工作，以及各種工序間的銜接，從而使整個工期的時間儘可能短？這些都是組合數學典型例子。又比如，假日飯店的管理中，也嚴格規定了有關的工序，如清潔工的第一步是換什麼，清洗什麼，第二步又做什麼，總之，他進出房間的次數應該最少。既然，這樣一個簡單的工作都需要講究工序，那么一個複雜的工程就更不用說了。
庫房和運輸的管理問題
怎樣安排運輸使得庫房充分發揮作用，進一步來說，貨物放在什麼地方最便於存取（如存儲時間短的應該放在容易存取的地方）。
鋪地磚問題
我們知道，用形狀相同的方型磚塊可以把一個地面鋪滿（不考慮邊緣的情況），但是如果用不同形狀，而又非方型的磚塊來鋪一個地面，能否鋪滿呢？這不僅是一個與實際相關的問題，也涉及到很深的組合數學問題。
組合數學還可用於金融分析
