組合學檢視原始碼討論檢視歷史
| 組合學 | |
|---|---|
組合學，簡稱組態的數學分支，也稱組合數學，它研究的是滿足各種附加條件的有限個對象的集合。組合學所研究的問題有:計數問題、存在性問題、枚舉、構造和算法問題、優化問題等。組合學分為幾大部分:圖論、組合計數、組合設計、組合最優化和組合幾何等。
基本信息
中文名 組合學 [1]
外文名 Combinatorics [2]
由來
組合學研究的是數(shǔ)的技巧.雖然數(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世紀數學家們提出的一個新的挑戰.
數學家
在中國當代的數學家中，較早地在組合學中的不同方面作出過貢獻的有華羅庚、吳文俊、柯召、萬哲先、張里千和陸家羲等.其中，萬哲先和他領導的研究組在有限幾何方面的系統工作不僅對於組合設計而且對於圖的對稱性的研究都有影響.陸家羲的有關不交斯坦納三元系大集的一系列的文章不僅解決了組合設計方面的一個難題，而且他所創立的方法對於其後的研究者也產生了和正產生着積極的作用.
排列組合問題基本概念是什麼
中公事業單位為幫助各位考生順利通過事業單位招聘考試！今天為大家帶來數量關係解題技巧：排列組合問題基本概念是什麼？
1.排列：從n個不同元素中任取m個按照一定的順序排成一列，叫作從n個元素中取出m個元素的一個排列。所有不同排列的個數，稱為從n個不同元素中取出m個元素的排列數，一般我們記作。
舉例說明：從編號為a、b、c、d的4個孩子中選出2個孩子排成一行，有多少種排法?顯然，列舉出來有ab、ac、ad、ba、bc、bd、ca、cb、cd、da、db、dc，共12種。這裡，即便是選出來的孩子一樣，但排列順序不一樣，排法也就不一樣，因此要考慮孩子的順序，所以是排列問題。排法應該是=4×3=12(種)。
2.全排列：n個不同的元素全部取出的一個排列，叫作n個不同元素的一個全排列，即當m=n時，全排列數=n(n-1)(n-2)×…×3×2×1=n!。
3.組合：從n個不同元素中取出m個元素拼成一組，稱為從n個元素取出m個元素的一個組合。不同組合的個數稱為從n個不同元素取出m個元素的組合數，一般我們記作。
舉例說明：從編號為a、b、c、d的4個孩子中選出3個孩子去參加運動會，有多少種選法?列舉出來，有abc、abd、bcd、acd這4種情況。abc與acb、bca表明選出的都是a、b、c，是一種選法，不需要考慮孩子的順序，所以是組合問題，選法為=4(種)。
考慮順序用排列，不考慮順序用組合。
數學問題：排列與組合的概念與區別
排列與組合的共同點是從n個不同的元素中，任取m（m≤n）個元素，而不同點是排列是按照一定的順序排成一列，組合是無論怎樣的順序並成一組，因此「有序」與「無序」是區別排列與組合的重要標誌．下面通過實例來體會排列與組合的區別．
【例題】 判斷下列問題是排列問題還是組合問題？並計算出種數．
（1） 高二年級學生會有11人：①每兩人互通一封信，共通了多少封信？②每兩人互握了一次手，共握了多少次手？
（2） 高二數學課外活動小組共10人：①從中選一名正組長和一名副組長，共有多少種不同的選法？②從中選2名參加省數學競賽，有多少種不同的選法？
（3） 有2、3、5、7、11、13、17、19八個質數：①從中任取兩個數求它們的商，可以有多少個不同的商？②從中任取兩個求它的積，可以得到多少個不同的積？
（4） 有8盆花：①從中選出2盆分別給甲、乙兩人每人一盆，有多少種不同的選法？②從中選出2盆放在教室有多少種不同的選法？
【思考與分析】 （1） ①由於每兩人互通一封信，甲給乙的信與乙給甲的信是不同的兩封信，所以與順序有關，是排列；②由於每兩人互握一次手，甲與乙握手、乙與甲握手是同一次握手，與順序無關，所以是組合問題．其他類似分析．
解： （1） ①是排列問題，共通了=110（封）；②是組合問題，共需握手==55（次）
（2） ①是排列問題，共有=10×9=90（種）不同的選法；②是組合問題，共=45（種）不同的選法；
（3） ①是排列問題，共有=8×7=56（個）不同的商；②是組合問題，共有=28（個）不同的積；
（4） ①是排列問題，共有=56（種）不同的選法；②是組合問題，共有=28（種）不同的選法．
【反思】 區分排列與組合的關鍵是「有序」與「無序