1. 組合數學概述

組合數學，又稱為離散數學，但有時人們也把組合數學和圖論加在一起算成是離散數學。組合數學是計算機出現以後迅速發展起來的一門數學分支。計算機科學就是算法的科學，而計算機所處理的對象是離散的數據，所以離散對象的處理就成了計算機科學的核心，而研究離散對象的科學恰恰就是組合數學。組合數學的發展改變了傳統數學中分析和代數占統治地位的局面。現代數學可以分為兩大類：一類是研究連續對象的，如分析、方程等，另一類就是研究離散對象的組合數學。組合數學不僅在基礎數學研究中具有極其重要的地位，在其它的學科中也有重要的應用，如計算機科學、編碼和密碼學、物理、化學、生物等學科中均有重要應用。微積分和近代數學的發展為近代的工業革命奠定了基礎。而組合數學的發展則是奠定了本世紀的計算機革命的基礎。計算機之所以可以被稱為電腦，就是因為計算機被人編寫了程序，而程序就是算法，在絕大多數情況下，計算機的算法是針對離散的對象，而不是在作數值計算。正是因為有了組合算法才使人感到，計算機好象是有思維的。

組合數學不僅在軟件技術中有重要的應用價值，在企業管理，交通規劃，戰爭指揮，金融分析等領域都有重要的應用。在美國有一家用組合數學命名的公司，他們用組合數學的方法來提高企業管理的效益，這家公司辦得非常成功。此外，試驗設計也是具有很大應用價值的學科，它的數學原理就是組合設計。用組合設計的方法解決工業界中的試驗設計問題，在美國已有專門的公司開發這方面的軟件。最近，德國一位著名組合數學家利用組合數學方法研究藥物結構，為製藥公司節省了大量的費用，引起了製藥業的關注。

在1997年11月的南開大學組合數學研究中心成立大會上，吳文俊院士指出，每個時代都有它特殊的要求，使得數學出現一個新的面貌，產生一些新的數學分支，組合數學這個新的分支也是在時代的要求下產生的。最近，吳文俊院士又指出，信息技術很可能會給數學本身帶來一場根本性的變革，而組合數學則將顯示出它的重要作用。楊樂院士也指出組合數學無論在應用上和理論上都具有越來越重要的位置，它今後的發展是很有生命力，很有前途的，中國應該倡導這個方面的研究工作。萬哲先院士甚至舉例說明了華羅庚，許寶祿，吳文俊等中國老一輩的數學家不僅重視組合數學，同時還對組合數學中的一些基本問題作了重大貢獻。迫於中國組合數學發展自身的需要，以及中國信息產業發展的需要，在中國發展組合數學已經迫在眉睫，刻不容緩。

2. 組合數學與計算機軟件

隨着計算機網絡的發展，計算機的使用已經影響到了人們的工作，生活，學習，社會活動以及商業活動，而計算機的應用根本上是通過軟件來實現的。我在美國聽到過一種說法，將來一個國家的經濟實力可以直接從軟件產業反映出來。我國在軟件上的落後，要說出根本的原因可能並不是很簡單的事，除了技術和科學上的原因外，可能還跟我們的文化，管理水平，教育水平，思想素質等諸多因素有關。除去這些人文因素以外，一個最根本的原因就是我國的信息技術的數學基礎十分薄弱，這個問題不解決，我們就難成為軟件強國。然而問題決不是這麼簡單，信息技術的發展已經涉及到了很深的數學知識，而數學本身也已經發展到了很深、很廣的程度並不是單憑几個聰明的頭腦去想想就行了，而更重要的是需要集體的合作和力量，就象軟件的開發需要多方面的人員的合作。美國的軟件之所以能領先，其關鍵就在於在數學基礎上他們有很強的實力，有很多傑出的人才。一般人可能會認為數學是一門純粹的基礎科學，1+1的解決可能不會有任何實際的意義。如果真是這樣，一門純粹學科的發展落後幾年，甚至十年，關係也不大。然而中國的軟件產業的發展已向數學基礎提出了急切的需求：網絡算法和分析，信息壓縮，網絡安全，編碼技術，系統軟件，並行算法，數學機械化和計算機推理，等等。此外，與實際應用有關的還有許多許多需要數學基礎的算法，如運籌規劃，金融工程，計算機輔助設計等。如果我們的軟件產業還是把眼光一直盯在應用軟件和第二次開發，那麼我們在應用軟件這個領域也會讓國外的企業搶去很大的市場。如果我們現在在信息技術的數學基礎上，大力支持和投入，那將是亡羊補牢，猶未為晚；只要我們能搶回信息技術的數學基地，那麼我們還有可能在軟件產業的競爭中，扭轉局面，甚至反敗為勝。吳文俊院士開創和領導的數學機械化研究，為中國在信息技術領域占領了一個重要的陣地，有了雄厚的數學基礎，自然就有了軟件開發的競爭力。這樣的陣地多幾個，我們的軟件產業就會產生新的局面。值得注意的是，印度有很好的統計和組合數學基礎，這可能也是印度的軟件產業近幾年有很大發展的原因。

3. 組合數學在國外的狀況

縱觀全世界軟件產業的情況，易見一個奇特的現象：美國處於絕對的壟斷地位。造成這種現象的一個根本的原因就是計算機科學在美國的飛速發展。當今計算機科學界的最權威人士很多都是研究組合數學出身的。美國最重要的計算機科學系（MIT，Princeton，Stanford，Harvard，Yale，….）都有第一流的組合數學家。計算機科學通過對軟件產業的促進，帶來了巨大的效益，這已是不爭之事實。組合數學在國外早已成為十分重要的學科，甚至可以說是計算機科學的基礎。一些大公司，如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的結構和生物現象與組合數學有密切的聯繫，各國對生物信息學的研究都很重視，這也是組合數學可以發揮作用的一個重要領域。前不久召開的北京香山會議就體現了國家對生物信息學的高度重視。據說IBM也將成立一個生物信息學研究中心。由於DNA就是組合數學中的一個序列結構，美國科學院院士，近代組合數學的奠基人Rota教授預言，生物學中的組合問題將成為組合數學的一個前沿領域。

美國的大學，國家研究機構，工業界，軍方和情報部門都有許多組合數學的研究中心，在研究上投入了大量的經費。但他們得到的收益遠遠超過了他們的投入，更主要的是他們還聚集了組合數學領域全世界最優秀的人才。高層次的軟件產品處處用到組合數學，更確切地說就是組合算法。傳統的計算機算法可以分為兩大類，一類是組合算法，一類是數值算法（包括計算數學和與處理各種信息數據有關的信息學）。依我個人的淺見，近年來計算機算法又多了一類：那就是符號計算算法。吳文俊院士開創的機器證明方法就屬於符號計算，引起了國際上的高度評價，被稱為吳方法。而國際上還有專門的符號計算雜誌。符號算法和吳方法跟代數組合學也有十分密切的聯繫。組合數學，數值計算（包括計算數學，科學計算，非線性科學，和與處理各種信息數據有關的信息學）和統計學可能是應用最廣的數學分支，而組合數學的價值甚至不亞於統計學和數值計算。由於數學機械化近年來的發展和在計算機科學中的重要性，把數學機械化，科學計算和組合數學組合起來，就可以說是中國信息產業的基礎。組合數學家H. Wilf和D. Zeilberger1998因為在組合恆等式的機械化證明方面的成果，獲得1998年美國數學會的Steele獎。

Gian-Carlo Rota教授在他去年不幸逝世之前，還專門向我提出，希望我向中國有關部門和領導人呼籲，組合數學是計算機軟件產業的基礎，中國最終一定能成為一個軟件大國，但是要實現這個目標的一個突破點就是發展組合數學。中國在軟件技術上遠遠落後於美國，而在組合數學上則更是落後於美國和歐洲。如果中國只是想在軟件技術上跟着西方走，而不在組合數學上下功夫，那麼中國的軟件將一直處於落後的狀態。他特別強調組合數學在計算機科學中的作用，以及在大學計算機系加強組合數學教學和人才培養。

最近Thomson Science公司創刊的一份電子刊物《離散數學和理論計算機科學》即是一個很好的說明。它的內容涉及離散數學和計算機科學的眾多方面。由於計算機軟件的促進和需求，組合數學已成為一門既廣博又深奧的學科，需要很深的數學基礎，逐漸成為了數學的主流分支。本世紀公認的偉大數學家蓋爾芳德預言組合數學和幾何學將是下一世紀數學研究的前沿陣地。這一觀點不僅得到國際數學界的贊同，也得到了中國數學界的贊同和響應。

加拿大在Montreal成立了試驗數學研究中心，他們的思路可能和吳文俊院士的數學機械化研究中心的發展思路類似，使數學機械化，算法化，不僅使數學為計算機科學服務，同時也使計算機為數學研究服務。吳文俊院士指出，中國傳統數學中本身就有濃厚的算法思想。

今後的計算機要向更加智能化的方向發展，其出路仍然是數學的算法，和數學的機械化。另外的一個有說服力的現象是，組合數學家總是可以在大學的計算機系或者在計算機公司找到很好的工作，一個優秀的組合數學家自然就是一個優秀的計算機科學家。相反，美國所有大學計算機系都有組合數學的課程。

除上述以外，歐洲也在積極發展組合數學，英國、法國、德國、荷蘭、丹麥、奧地利、瑞典、意大利、西班牙等國家都建立了各種形式的組合數學研究中心。近幾年，南美國家也在積極推動組合數學的研究。澳大利亞，新西蘭也組建了很強的組合數學研究機構。值得一提的是亞洲的發達國家也十分重視組合數學的研究。日本有組合數學研究中心，並且從美國引進人才，不僅支持日本國內的研究，還出資支持美國的有關課題的研究，這樣使日本的組合數學這幾年的發展極為迅速。台灣、香港兩地也從美國引進人才，大力發展組合數學。新加坡，韓國，馬來西亞也在積極推動組合數學的研究和人才培養。台灣的數學研究中心也正在考慮把組合數學作為重點方向來發展。世界各地對組合數學的如此鍾愛顯然是有原因的，那就是沒有組合數學就沒有計算機科學，沒有計算機軟件。

4. 組合數學花絮

** 在日常生活中我們常常遇到組合數學的問題。如果你仔細留心一張世界地圖，你會發現用一種顏色對一個國家着色，那麼一共只需要四種顏色就能保證每兩個相鄰的國家的顏色不同。這樣的着色效果能使每一個國家都能清楚地顯示出來。但要證明這個結論確是一個著名的世界難題，最終藉助計算機才得以解決，最近人們才發現了一個更簡單的證明。

** 我國古代的河洛圖上記載了三階幻方，即把從一到九這九個數按三行三列的隊行排列，使得每行，每列，以及兩條對角線上的三個數之和都是一十五。組合數學中有許多象幻方這樣精巧的結構。1977年美國旅行者1號、2號宇宙飛船就帶上了幻方以作為人類智慧的信號。

** 當你裝一個箱子時，你會發現要使箱子儘可能裝滿不是一件很容易的事，你往往需要做些調整。從理論上講，裝箱問題是一個很難的組合數學問題，即使用計算機也是不容易解決的。

** 在中小學的數學遊戲中，有這樣一個問題，一個船夫要把一隻狼，一隻羊和一棵白菜運過河。問題是當人不在場時，狼要吃羊，羊要吃白菜，而他的船每趟只能運其中的一個。他怎樣才能把三者都運過河呢？這就是一個很典型、很簡單的組合數學問題。

** 我們還會遇到更複雜的調度和安排問題。例如，在生產原子彈的曼哈頓計劃中，涉及到很多工序，許多人員的安排，很多元件的生產，怎樣安排各種人員的工作，以及各種工序間的銜接，從而使整個工期的時間儘可能短？這些都是組合數學典型例子。

** 航空調度和航班的設定也是組合數學的問題。怎樣確定各個航班以滿足 不同旅客轉機的需要，同時也使得每個機場的航班起落分布合理。此外，在一些航班有延誤等特殊情況下，怎樣作最合理的調整，這些都是 組合數學的問題。

** 對於城市的交通管理，交通規劃，哪些地方可能是阻塞要地，哪些地方 應該設單行道，立交橋建在哪裡最合適，紅綠燈怎樣設定最合理， 如此等等，全是組合數學的問題。

** 一個郵遞員從郵局出發，要走完他所管轄的街道，他應該怎樣選擇什麼樣的路徑，這就是著名的"中國郵遞員問題"，由中國組合數學家管梅谷教授提出，著名組合數學家，J. Edmonds和他的合作者給出了一個解答。

** 一個通訊網絡怎樣布局最節省？美國的貝爾實驗室和IBM公司都有世界一流的組合數學家在研究這個問題，這個問題直接關繫到巨大的經濟利益。

** 據說，假日飯店的管理中，也嚴格規定了有關的工序，如清潔工的第一步是換什麼，清洗什麼，第二步又做什麼，總之，他進出房間的次數應該最少。既然，這樣一個簡單的工作都需要講究工序，那麼一個複雜的工程就更不用說了。

** 庫房和運輸的管理也是典型的組合數學問題。怎樣安排運輸使得庫房充分發揮作用，進一步來說，貨物放在什麼地方最便於存取（如存儲時間短的應該放在容易存取的地方）。

** 我們知道，用形狀相同的方型磚塊可以把一個地面鋪滿（不考慮邊緣的情況），但是如果用不同形狀，而又非方型的磚塊來鋪一個地面，能否鋪滿呢？這不僅是一個與實際相關的問題，也涉及到很深的組合數學問題。

** 組合數學中有一個著名問題：是否存在穩定婚姻的問題。假如能找到兩對夫婦（如張（男）--李（女）和趙（男）--王（女）），如果張（男）更喜歡王（女），而王（女）也更喜歡張（男），那麼這樣就可能有潛在的不穩定性。組合數學的方法可以找到一種婚姻的安排方法，使得沒有上述的不穩定情況出現（當然這只是理論上的結論）。這種組合數學的方法卻有 一個實際的用途：美國的醫院在確定錄取住院醫生時，他們將考慮申請者的志願的先後次序，同時也給申請排序。按這樣的 次序考慮出的總的方案將沒有醫院和申請者兩者同時後悔的情況。 實際上，高考學生的最後錄取方案也可以用這種方法。

** 組合數學還可用於金融分析，投資方案的確定，怎樣找出好的投資組合以降低投資風險。南開大學組合數學研究中心開發出了"金沙股市風險分析系統"現已投放市場，為短線投資者提供了有效的風險防範工具。

總之，組合數學無處不在，它的主要應用就是在各種複雜關係中找出最優的方案。所以組合數學完全可以看成是一門量化的關係學，一門量化了的運籌學，一門量化了的管理學。

胡錦濤同志在1998年接見"五四"青年獎章時發表的講話中指出，組合數學不同於傳統的純數學的一個分支，它還是一門應用學科，一門交叉學科。他希望中國的組合數學研究能夠為國家的經濟建設服務。

如果21世紀是信息社會的世紀，那麼21世紀也必將是組合數學大有可為的世紀。