组合数学

研究离散结构性质的一个数学分支
(重定向自組合數學

广义的组合数学(英語:Combinatorics)相当于离散数学,狭义的组合数学组合计数图论代数结构数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之,组合数学是一门研究可數或离散对象的科学。随着计算机科学日益发展,组合数学的重要性也日渐凸显,因为计算机科学的核心内容是使用算法处理离散数据

狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数组合设计(Combinatorial design英语Combinatorial design)、组合矩阵(Combinatorial matrix theory英语Combinatorial matrix theory)、组合最佳化最佳組合)等。

歷史

编辑
 
An example of change ringing (with six bells), one of the earliest nontrivial results in graph theory.

最基本的組合數學的思想和枚舉的方法在古老時代就已經出現。西元前6世紀的古印度外科醫生妙聞指出可以由6種相異味道組合出63種相異結果(每種味道都可以選擇或不選擇,但不能都不選擇,因此有26−1=63種組合);古羅馬時期,希臘史學家普魯塔克克律西波斯喜帕恰斯討論了後來顯示與Schröder–Hipparchus數英语Schröder–Hipparchus number有關的枚舉問題[1][2];西元前3世紀的阿基米德在其數學文章Ostomachion英语Ostomachion中講述拼接拼圖的智力遊戲(tiling puzzle)。

中世紀時,組合數學持續發展(主要是歐洲外的文明)。西元850年的印度數學家Mahāvīra英语Mahāvīra (mathematician)提供了關於排列數與組合的公式[3][4],甚至可能早在6世紀的印度數學家就對這些公式熟悉[5] 。西元1140年哲學家天文學家阿伯拉罕·伊本·埃茲拉確認了二項式係數的對稱性,而二項式係數公式則是由猶太人數學家吉尔松尼德在西元1321年得到[6]楊輝三角形最早可追溯至10世紀的數學論文,在中國則首現於13世紀南宋楊輝詳解九章算法》。在英格蘭則出現與哈密頓迴路相關的例子[7]

文藝復興時期,與其他數學或科學領域一樣,組合數學再現生機。帕斯卡牛頓雅各布·白努利歐拉等人的研究為此新興領域打下基礎。在更近代,西爾維斯特馬克斯·馬奧尼也在組合計數代數組合學有貢獻。数学家也對四色問題圖論有極大興趣。

在20世紀下半葉,組合數學成長相當迅速,甚至出現數十種新的期刊和會議[8],這種成長某程度上是由與其他領域的連結與應用所帶動,如代數機率論泛函分析數論

组合数学中的著名问题

编辑
  • 計算一些物品在特定條件下分組的方法數目。這些是關於排列組合整數分拆
  • 地图着色问题:為地图填色,每區用一色。如果要邻區颜色相异,是否只需四色?這是圖論題。
  • 船夫过河问题:船夫要把一匹狼、一只羊和一棵菜运过河。只要船夫不在场,羊就会吃白菜、狼就会吃羊,但船每次只能运送一种东西。怎样把所有东西运过河?這是線性規劃題。
  • 中国邮差问题:由中华民国组合数学家管梅谷教授提出。邮差要穿过城市的每一条路至少一次,怎样行走走过的路程最短?这不是NP完全问题,存在多项式复杂度算法:先求出度为奇数的点,用匹配算法算出这些点间的连接方式,然后再用欧拉路径算法求解。也是圖論題。
  • 任务分配问题(也称分配问题):有一些员工要完成一些任务。各员工完成不同任务用的时间都不同。每个员工只分配一项任务。每项任务只分给一个员工。怎样分配员工与任务以使所花费的时间最少?也是線性規劃題。
  • 如何構造幻方幻方為一方陣,填入不重複之自然數,並使其中每一縱列、橫列、對角線內數字之和皆相同。
  • 數獨:遊戲一般由9個3×3個的九宫格組成。每一列的數字均須包含 1~9,不能缺少,也不能重複。每一宮(粗黑線圍起來的區域,通常是 3x3 的九宮格)的數字均須包含 1~9,不能缺少,也不能重複。參見Mathematics_of_Sudoku英语Mathematics_of_Sudoku

排列

编辑

 个元素取出 个元素, 个元素的排列數量為:

 

賽馬為例,有8匹马参赛,玩家需在彩票上填入前三匹胜出的马匹号码,從8匹馬取出3匹來排前3名,排列數量為:

 

因为有336种排列,因此玩家在一次填入中中奖的概率是:

  (假設每匹馬贏的機會相等)

不過,中國大陸的教科書則是把從n取k的情況記作  (A代表Arrangement,即排列[9])。

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

 个元素取出 个元素, 个元素可以重复出现,這排列數量為:

 [10]

四星彩為例,10個數取4個,因可能重複所以排列數量為:

 

这时的一次性添入中奖的概率就是:

 

组合

编辑

和排列不同的是,组合不考虑取出元素的顺序。

 个元素取出 个, 个元素的组合數量为:

 

中國大陸的教科書則是把從  的情況記作 [11]

以香港六合彩為例,六合彩49顆球選6顆的组合數量为:

 

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

 个元素取出 个元素, 個元素可以重複出現,组合數量为:

 

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

 

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

 

另外 也可以記為 [12]

 

总结

编辑
 中取  直線排列
(考慮順序)
环状排列 组合
(不考慮順序)
不重复出现
(不放回去)
 
OEIS數列A008279
 
OEIS數列A111492
 
OEIS數列A007318
可重复出现
(再放回去)
 
OEIS數列A004248
 
OEIS數列A075195
 
OEIS數列A097805

参见

编辑

參考文獻

编辑
  1. ^ Stanley, Richard P.; "Hipparchus, Plutarch, Schröder, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344–350.
  2. ^ Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; "On the Second Number of Plutarch", American Mathematical Monthly 105 (1998), no. 5, 446.
  3. ^ 約翰·J·奧康納; 埃德蒙·F·羅伯遜, Mahavira, MacTutor数学史档案 (英语) 
  4. ^ 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) 
  5. ^ Biggs, Norman L. The Roots of Combinatorics. Historia Mathematica. 1979, 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0. 
  6. ^ 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.)
  7. ^ 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.
  8. ^ See Journals in Combinatorics and Graph Theory页面存档备份,存于互联网档案馆
  9. ^ 普通高中课程标准实验教科书 数学 选修2-3 B版. 人民教育出版社. : 10. ISBN 9787107187544. 
  10. ^ 組合數學 ─算法與分析─. 九章出版社. : 29.  OCLC:44527392
  11. ^ 普通高中课程标准实验教科书 数学 选修2-3 B版. 人民教育出版社. : 16. ISBN 9787107187544. 
  12. ^ 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392

外部連結

编辑