組合學簡稱組態的數學分支，也稱組合數學，它研究的是滿足各種附加條件的有限個對象的集合。組合學所研究的問題有：計數問題、存在性問題、枚舉、構造和算法問題、最佳化問題等。組合學分為幾大部分：圖論、組合計數、組合設計、組合最最佳化和組合幾何等。
基本介紹
- 中文名：組合學
- 外文名：Combinatorics
- 也稱：組合數學
- 研究對象：滿足各種附加條件有限對象的集合
- 包含：圖論、組合計數、組合設計等
- 套用學科：數學
簡介,由來,歷史發展,發展現狀,
簡介
現代數學可以分為兩大類：一類是研究連續對象的，如分析學、方程等，另一類就是研究離散對象的組合學。組合學不僅在基礎數學研究中具有極其重要的地位，在其它的學科中也有重要的套用，如計算機科學、編碼和密碼學、物理、化學、生物學等學科中均有重要套用。微積分和近代數學的發展為近代的工業革命奠定了基礎。而組合學的發展則是奠定了本世紀的計算機革命的基礎。計算機之所以可以被稱為電腦，就是因為計算機被人編寫了程式，而程式就是算法，在絕大多數情況下，計算機的算法是針對離散的對象，而不是在作數值計算。正是因為有了組合算法才使人感到，計算機好像是有思維的。
組合學不僅在軟體技術中有重要的套用價值，在企業管理，交通規劃，戰爭指揮，金融分析等領域都有重要的套用。在美國有一家用組合數學命名的公司，他們用組合學的方法來提高企業管理的效益，這家公司辦得非常成功。此外，試驗設計也是具有很大套用價值的學科，它的數學原理就是組合設計。用組合設計的方法解決工業界中的試驗設計問題，在美國已有專門的公司開發這方面的軟體。
由來
組合學研究的是數(shǔ)的技巧。雖然數(shǔ)數始於以結計數的遠古時代，由於那時人的智力的發展尚處於低級階段，談不上有什麼技巧。隨著人們對於數的了解和研究，在形成與數密切相關的數學分支的過程中，如數論、代數、函式論以至泛函的形成與發展，逐步地從數的多樣性發現數(shǔ)的多樣性，產生了各種數(shǔ)數的技巧。同時，在人們對於形有了深入的了解和研究的基礎上，在形成與形密切相關的各種數學分支的過程中，如幾何學、拓撲學以至範疇論的形成與發展，逐步地從形的多樣性也發現了數(shǔ)形的多樣性，產生了各種數(shǔ)形的技巧.近代的集合論、數理邏輯等反映了潛在的數與形之間的結合。而現代的代數拓撲和代數幾何等則將數與形密切地聯繫在一起了。這些，對於以數的技巧為中心課題的近代組合學的形成與發展都產生了而且還將會繼續產生深刻的影響。
歷史發展
由此觀之，組合學與其他數學分支有著必然的密切聯繫.它的一些研究內容與方法來自各個分支也套用於各個分支。當然，組合學與其他數學分支一樣也有其獨特的研究問題與方法，它源於人們對於客觀世界中存在的數與形及其關係的發現和認識。例如，中國古代的《易經》中用十個天干和十二個地支以六十為周期來記載月和年，以及在洛書河圖中關於幻方的記載，是人們至今所了解的最早發現的組合問題。於11和12世紀間，賈憲就發現了二項式係數，楊輝將它整理記載在他的《續古抉奇法》一書中。這就是中國通常稱的楊輝三角.事實上，於12世紀印度的婆什迦羅第二(Bhāskara，Ⅱ)也發現了這種組合數。13世紀波斯的哲學家曾講授過此類三角。而在西方，帕斯卡(Pascal，B.)發現這個三角形是在17世紀中期。這個三角形在其他數學分支的套用也是屢見不鮮的。同時，帕斯卡和費馬均發現了許多與機率論有關的經典組合學的結果。因此，西方人認為組合學開始於17世紀。組合學一詞是德國數學家萊布尼茨(Leibniz，G.W.)在數學的意義下首次套用。也許，在那時他已經預感到了其將來的蓬勃發展。然而只有到了18世紀歐拉(Euler，L.)所處時代，組合學才可以說開始了作為一門科學的發展，因為那時，他解決了哥尼斯堡七橋問題，發現了多面體(首先是凸多面體，即平面圖的情形)的頂點數、邊數和面數之間的簡單關係。已被人們稱為歐拉公式。甚至，當今人們所稱的哈密頓圈的首創者也應該是歐拉。這些不但使歐拉成為組合學的一個重要組成部分——圖論而且也成為占據現代數學舞台中心的拓撲學發展的先驅。同時，他對導致當今組合學中的另一個重要組成部分——組合設計中的拉丁方的研究所提出的猜想，人們稱為歐拉猜想，直到1959年才得到完全的解決。於19世紀初，高斯(Gauss，C.F.)提出的組合係數，今稱高斯係數，在經典組合學中也占有重要地位。同時，他還研究過平面上的閉曲線的相交問題，由此所提出的猜想稱為高斯猜想，它直到20世紀才得到解決。這個問題不僅貢獻於拓撲學，而且也貢獻於組合學中圖論的發展。同在19世紀，由布爾(Boole，G.)發現且被當今人們稱為布爾代數的分支已經成為組合學中序理論的基石。當然，在這一時期，人們還研究其他許多組合問題，它們中的大多數是娛樂性的。
楊輝三角
楊輝三角20世紀初期，龐加萊(Poincaré，(J.-)H.)聯繫多面體問題發展了組合學的概念與方法，導致了近代拓撲學從組合拓撲學到代數拓撲學的發展。於20世紀的中、後期，組合學發展之迅速也許是人們意想不到的。首先，於1920年費希爾(Fisher，R.A.)和耶茨(Yates，F.)發展了實驗設計的統計理論，其結果導致後來的資訊理論，特別是編碼理論的形成與發展。於1939年，坎托羅維奇(Канторович，Л.В.)發現了線性規劃問題並提出解乘數法。於1947年丹齊克(Dantzig，G.B.)給出了一般的線性規劃模型和理論，他所創立的單純形方法奠定了這一理論的基礎，闡明了其解集的組合結構。直到今天它仍然是套用得最廣泛的數學方法之一。這些又導致以網路流為代表的運籌學中的一系列問題的形成與發展。開拓了人們目前稱為組合最最佳化的一個組合學的新分支。在20世紀50年代，中國也發現並解決了一類稱為運輸問題的線性規劃的圖上作業法，它與一般的網路流理論確有異曲同工之妙。在此基礎上又出現了國際上通稱的中國郵遞員問題。
法國數學家龐加萊
法國數學家龐加萊另一方面，自1940年以來，生於英國的塔特(Tutte，W.T.)在解決拼方問題中取得了一系列有關圖論的結果，這些不僅開闢了現今圖論發展的許多新研究領域，而且對於20世紀30年代，惠特尼(Whitney，H.)提出的擬陣論以及人們稱之為組合幾何的發展都起到了核心的推動作用.應該特別提到的是在這一時期，隨著電子技術和計算機科學的發展愈來愈顯示出組合學的潛在力量。同時，也為組合學的發展提出了許多新的研究課題。例如，以大規模和超大規模積體電路設計為中心的計算機輔助設計提出了層出不窮的問題。其中一些問題的研究與發展正在形成一種新的幾何，人們稱之為組合計算幾何.關於算法複雜性的研究，自1961年庫克(Cook，S.A.)提出NP完全性理論以來，已經將這一思想滲透到組合學的各個分支以至數學和計算機科學中的一些分支。
四色猜想已被證明
四色猜想已被證明近20年來，用組合學中的方法已經解決了一些即使在整個數學領域也是具有挑戰性的難題。例如，范·德·瓦爾登(Van der Waerden，B.L.)於1926年提出的關於雙隨機矩陣積和式猜想的證明；希伍德(Heawood，P.J.)於1890年提出的曲面地圖著色猜想的解決；著名的四色定理的計算機驗證和扭結問題的新組合不變數發現等。在數學中已經或正在形成著諸如組合拓撲、組合幾何、組合數論、組合矩陣論、組合群論等與組合學密切相關的交叉學科。此外，組合學也正在滲透到其他自然科學以及社會科學的各個方面，例如，物理學、力學、化學、生物學、遺傳學、心理學以及經濟學、管理學甚至政治學等。
發展現狀
根據組合學研究與發展的現狀，它可以分為如下五個分支：經典組合學、組合設計、組合序、圖與超圖和組合多面形與最最佳化。由於組合學所涉及的範圍觸及到幾乎所有數學分支，也許和數學本身一樣不大可能建立一種統一的理論。然而，如何在上述的五個分支的基礎上建立一些統一的理論，或者從組合學中獨立出來形成數學的一些新分支將是對21世紀數學家們提出的一個新的挑戰。
