组合数学：修订间差异

广义的'''组合数学'''（{{lang-en|Combinatorics}}）就是[[离散数学]]，狭义的'''组合数学'''是[[组合计数]]、[[图论]]、[[代数结构]]、[[数理逻辑]]等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究可數或离散对象的科学。随着[[计算机科学]]的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用[[算法]]处理[[离散数据]]。

组合数学的主要内容有[[组合计数]]、[[组合设计]]、[[组合矩阵]]、[[组合优化]]（[[最佳組合]]）等。

== 歷史 ==

最基本的組合數學的思想和枚舉的方法在古老時代就已經出現。西元前6世紀的古[[印度]]外科醫生[[妙闻|妙聞]]已經指出可以由6個相異的味道組合出63種相異的結果（每個味道都可以選擇或不選擇，但不能都不選擇，因此有2⁶&nbsp;−&nbsp;1=63種組合）；[[羅馬帝國|羅馬時代]]的[[希臘]][[史家]][[普魯塔克]]與[[克律西波斯]]、[[喜帕恰斯]]討論了後來顯示與{{link-en|Schröder–Hipparchus數|Schröder–Hipparchus number}}有關的枚舉問題<ref>[[Richard P. Stanley|Stanley, Richard P.]]; "Hipparchus, Plutarch, Schröder, and Hough", ''American Mathematical Monthly'' '''104''' (1997), no. 4, 344–350.</ref><ref>Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; "[http://search.proquest.com/openview/70485cece23ca51b18536b4422cc5586/1?pq-origsite=gscholar&cbl=47349 On the Second Number of Plutarch]", ''American Mathematical Monthly'' '''105''' (1998), no. 5, 446.</ref>；西元前3世紀的[[阿基米德]]在其數學文章''{{link-en|Ostomachion|Ostomachion}}''中考慮了一個拼接拼圖的智力遊戲（tiling puzzle）。

[[中世紀]]時，組合數學持續發展（主要是在[[歐洲]]外的文明）。西元850年的[[印度]]數學家{{link-en|Mahāvīra|Mahāvīra (mathematician)}}提供了關於[[排列]]數與[[組合]]的公式<ref>{{MacTutor|id=Mahavira}}</ref><ref>{{Citation|last=Puttaswamy|first=Tumkur K.|contribution=The Mathematical Accomplishments of Ancient Indian Mathematicians|editor-last=Selin|editor-first=Helaine|title=Mathematics Across Cultures: The History of Non-Western Mathematics|publisher=Kluwer Academic Publishers|location=Netherlands|url=https://books.google.com/books?id=2hTyfurOH8AC&printsec=frontcover|year=2000|isbn=978-1-4020-0260-1|page=417 <!-- pages 409–422 -->}}</ref>，甚至可能早在6世紀印度的數學家就對這些公式熟悉<ref>{{cite journal|title=The Roots of Combinatorics|url=|first1=Norman L.|journal=Historia Mathematica|issue=2|doi=10.1016/0315-0860(79)90074-0|year=1979|volume=6|pages=109–136|last1=Biggs}}</ref>。1140年[[哲學家]]與[[天文學家]][[阿伯拉罕·伊本·埃茲拉]]確認了二項式係數的對稱性，而二項式係數公式則是由[[猶太人]][[數學家]][[Gersonides]]在1321年得到的<ref>{{citation|title=Probability Theory: A Historical Sketch|first=L.E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=978-1-4832-1863-2|url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|page=35}}. (Translation from 1967 Russian ed.)</ref>。[[楊輝三角形]]最早可追溯至10世紀的數學論文，在[[中国|中國]]則首現於13世紀[[南宋]][[杨辉|楊輝]]的《[[詳解九章算法]]》。在[[英格蘭]]，則出現一些與[[哈密頓圖|哈密頓迴路]]相關的例子<ref>

[[文藝復興時期]]，與其他數學或[[科學]]領域一樣，組合數學再現生機。[[布萊茲·帕斯卡|帕斯卡]]、[[艾薩克·牛頓|牛頓]]、[[雅各布·白努利]]、[[李昂哈德·歐拉|歐拉]]等人的研究為此新興領域打下基礎。在更近代時，[[詹姆斯·約瑟夫·西爾維斯特|西爾維斯特]]和{{link-en|MacMahon|Percy Alexander MacMahon}}也對[[组合计数|組合計數]]和[[代數組合學]]作出貢獻。人們此時也對[[圖論]]有高度的興趣，例如關於[[四色定理|四色問題]]的領域。

在20世紀下半葉，組合數學成長相當快速，甚至出現數十種新的期刊和會議<ref>See [http://www.math.iit.edu/~kaul/Journals.html#CGT Journals in Combinatorics and Graph Theory]</ref>。 在某種程度上，這樣的成長是由對其他領域的連結與應用所帶動，包括[[代數]]、[[機率論]]、[[泛函分析]]和[[數論]]等。

* 計算一些物品在特定條件下分組的方法數目。這些是關於[[排列]]、[[組合]]和[[整數分拆]]的。

* [[四色定理|地图着色问题]]：对世界地图着色，每一個国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？這是[[圖論]]的問題。

* [[狼、羊、菜问题|船夫过河问题]]：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？這是[[線性規劃]]的問題。

* [[中国邮差问题]]：由中国组合数学家[[管梅谷]]教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个[[NP完全]]问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用[[欧拉路径]]算法求解。這也是[[圖論]]的問題。

* [[任务分配问题]]（也称[[分配问题]]）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？這是[[線性規劃]]的問題。

* 如何構造[[幻方]]。 [[幻方]]為一方陣，填入不重複之[[自然數]]，並使其中每一縱列、橫列、對角線內數字之總和皆相同。

从<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>个元素的排列數量為：

以[[賽馬]]為例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，從8匹馬中取出3匹馬來排前3名，排列數量為：

不過，中國大陸的教科書則是把從n取k的情況記作<math>P^k_n</math>或<math>A^k_n</math>（A代表Arrangement，即排列<ref>{{cite book|title=普通高中课程标准实验教科书 数学 选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=10}}</ref>）。

上面的例子是建立在取出元素不重複出現狀況。

從<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>个元素可以重复出现，這排列數量為：

:<math> U_k^n = n^k</math><ref name="組合數學">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 | pages=29}} OCLC:44527392</ref>

以[[中華民國公益彩券|四星彩]]為例，10個數字取4個數字，因可能重複所以排列數量為：

{{main|組合}}

从<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>个元素的组合數量为：

不過，中國大陸的教科書則是把從<math>n</math>取<math>k</math>的情況記作<math>C^k_n</math><ref>{{cite book|title=普通高中课程标准实验教科书 数学 选修2-3 B版|publisher=人民教育出版社|isbn=9787107187544|pages=16}}</ref>。

以[[六合彩]]為例。在六合彩中从49顆球中取出6顆球的组合數量为：

如同排列，上面的例子是建立在取出元素不重複出現狀況。

从<math>n</math>个元素中取出<math>k</math>个元素，<math>k</math>個元素可以重複出現，這组合數量为：

以取色球為例，每種顏色的球有無限多顆，從8種色球中取出5顆球，這組合數量為：

因為組合數量公式特性，重複組合轉換成組合有另一種公式為：

另外<math>H_k^n</math>也可以記為<math>F_k^n</math><ref name="組合數學P33">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 | pages=33}} OCLC:44527392</ref>

|直線排列<br>（考慮順序）

|组合<br>（不考慮順序）

== 參考文獻 ==

== 外部連結 ==