组合数学

维基百科,自由的百科全书
跳转至: 导航搜索

组合数学(combinatorics),亦称組合論组合学数学的一个分支,亦即離散數學中的排列組合研究,所研究的是計数的技巧[1]

广义与狭义的组合数学[编辑]

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

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

历史及发展[编辑]

虽然数数始于以结计数的远古时代,由于那时人的智力的发展尚处于低级阶段,谈不上有什么技巧。随着人们对于数的了解和研究,在形成与数密切相关的数学分支的过程中,如数论代数函数论以至泛函的形成与发展,逐步地从数的多样性发现数数的多样性,产生了各种数数的技巧。

同时,在人们对于形有了深入的了解和研究的基础上,在形成与形密切相关的各种数学分支的过程中,如几何学拓扑学以至范畴论的形成与发展,逐步地从形的多样性也发现了数形的多样性,产生了各种数形的技巧。近代的集合论数理逻辑等反映了潜在的数与形之间的结合。而现代的代数拓扑代数几何等则将数与形密切地联系在一起了。这些,对于以数的技巧为中心课题的近代组合学的形成与发展都产生了而且还将会继续产生深刻的影响。

由此观之,组合学与其他数学分支有着必然的密切联系。它的一些研究内容与方法来自各个分支也应用于各个分支。当然,组合学与其他数学分支一样也有其独特的研究问题与方法,它源于人们对于客观世界中存在的数与形及其关系的发现和认识。例如,中国古代的《易经》中用十个天干和十二个地支以六十为周期来记载月和年,以及在洛书河图(又称河圖洛書)中关于幻方的记载,是人们至今所了解的最早发现的组合问题

于11和12世纪间,贾宪就发现了二项式系数杨辉将它整理记载在他的《续古抉奇法》一书中。这就是中国通常称的杨辉三角。事实上,于12世纪印度的婆什迦罗第二也发现了这种组合数。13世纪波斯的哲学家曾讲授过此类三角。而在西方,布萊茲·帕斯卡发现这个三角形是在17世纪中期。这个三角形在其他数学分支的应用也是屡见不鲜的。同时,帕斯卡和费马均发现了许多与概率论有关的经典组合学的结果。因此,西方人认为组合学开始于17世纪。组合学一词是德国数学家莱布尼茨在数学的意义下首次应用。也许,在那时他已经预感到了其将来的蓬勃发展。然而只有到了18世纪欧拉所处时代,组合学才可以说开始了作为一门科学的发展,因为那时,他解决了柯尼斯堡七桥问题,发现了多面体(首先是凸多面体,即平面图的情形)的顶点数、边数和面数之间的简单关系。现在已被人们称为欧拉公式。甚至,当今人们所称的哈密顿圈的首创者也应该是欧拉。这些不但使欧拉成为组合学的一个重要组成部分——图论而且也成为占据现代数学舞台中心的拓扑学发展的先驱。同时,他对导致当今组合学中的另一个重要组成部分——组合设计中的拉丁方的研究所提出的猜想,人们称为欧拉猜想,直到1959年才得到完全的解决。

于19世纪初,高斯提出的组合系数,今称高斯二项式系数,在经典组合学中也占有重要地位。同时,他还研究过平面上的闭曲线的相交问题,由此所提出的猜想称为高斯猜想,它直到20世纪才得到解决。这个问题不仅贡献于拓扑学,而且也贡献于组合学中图论的发展。同在19世纪,由喬治·布爾发现且被当今人们称为布尔代数的分支已经成为组合学中序理论的基石。当然,在这一时期,人们还研究其他许多组合问题,它们中的大多数是娱乐性的。

20世纪初期,庞加莱联系多面体问题发展了组合学的概念与方法,导致了近代拓扑学从组合拓扑学到代数拓扑学的发展。于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年提出的关于Van der Waerden猜想的证明;希伍德(Heawood,P.J.)于1890年提出的曲面地图着色猜想的解决;著名的四色定理的计算机验证和扭结问题的新组合不变量发现等。在数学中已经或正在形成着诸如组合拓扑组合几何组合数论组合矩阵论组合群论等与组合学密切相关的交叉学科。此外,组合学也正在渗透到其他自然科学以及社会科学的各个方面,例如,物理学、力学、化学、生物学、遗传学、心理学以及经济学、管理学甚至政治学等。[1]

分支[编辑]

根据组合学研究与发展的现状,它可以分为如下五个分支:经典组合学组合设计组合序图与超图组合多面形与最优化。由于组合学所涉及的范围触及到几乎所有数学分支,也许和数学本身一样不大可能建立一种统一的理论。然而,如何在上述的五个分支的基础上建立一些统一的理论,或者从组合学中独立出来形成数学的一些新分支将是对21世纪数学家们提出的一个新的挑战。[1]

中国的研究者[编辑]

在中国当代的数学家中,较早地在组合学中的不同方面作出过贡献的有华罗庚、吴文俊、柯召、万哲先、张里千和陆家羲等。其中,万哲先和他领导的研究组在有限几何方面的系统工作不仅对于组合设计而且对于图的对称性的研究都有影响。陆家羲的有关不交斯坦纳三元系大集的一系列的文章不仅解决了组合设计方面的一个难题,而且他所创立的方法对于其后的研究者也产生了和正产生着积极的作用。[1]

组合数学中的著名问题[编辑]

  • 計算一些物品在特定條件下分組的方法數目。這些是關於排列組合整數分拆的。
  • 地图着色问题:对世界地图着色,每一個国家使用一种颜色。如果要求相邻国家的颜色相异,是否总共只需四种颜色?這是圖論的問題。
  • 船夫过河问题:船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场,羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河?這是線性規劃的問題。
  • 中国邮差问题:由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次,怎样行走走过的路程最短?这不是一个NP完全问题,存在多项式复杂度算法:先求出度为奇数的点,用匹配算法算出这些点间的连接方式,然后再用欧拉路径算法求解。這也是圖論的問題。
  • 任务分配问题(也称分配问题):有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少?這是線性規劃的問題。
  • 如何構造幻方
  • 大樂透

排列[编辑]

3个彩球的排列(不重复出现)

排列的任务是确定n个不同的元素的排序的可能性。从右边的示意图可看出,3个不同颜色的彩球一共有6种不同的排列方式,因此有如下定理:「n个不同的元素可以有n !种不同的排列方式,即n阶乘。」因此上面的例子的算法是3 ! = 6。
另一个问题,如果从n个元素中取出k个元素,这k个元素的排列是多少呢?公式如下:

 P_n^k = \frac{n!}{(n-k)!}

例如,在赌马游戏中一共有8匹马参加比赛,玩家需要在彩票上填入前三位胜出的马匹的号码,按照上面的公式,n = 8,k = 3,玩家一共可以填出的3匹马号的排列数为:

 P_8^3 =\frac{8!}{(8-3)!}=336

因为一共存在336种可能性,因此玩家在一次填入中中奖的概率应该是:

 P = \frac{1}{336}= 0.00298

以上提到的都是在k不发生重复的情况下的排列。

如果在n个元素中取出k个元素进行排列,这k个元素可以重复出现,那么排列数则有如下公式:

n^k

还是上面的例子,k可以重复出现,这意味着玩家可以在前三名的位置上填入同一匹马号,因此在这种情况下可能出现的排列总数为:

83 = 512

另外,n^k也可以記為[2]

 U_n^k = n^k[2]

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

P=\frac{1}{512}=0.002(当然,同一匹马同时获得1,2,3名的情况在现实中是不存在的)

另一个来自数字技术的例子,在二进制中只有0和1两种状态,一个有x位的二进制数字可以有2x种排列方式,也即可以表达2x个不同的数字。

组合[编辑]

和排列不同的是,在组合中取出元素的顺序则不在考虑之中。从n个元素中取出k个元素,这k个元素可能出现的组合数为:

C_n^k ={n \choose k} = \frac{P_n^k}{k!} = \frac{n!}{k!(n-k)!}

六合彩游戏為例。在六合彩游戏中从49个球中取出6个进行组合的可能性一共有:

C_{49}^{6}  = {49 \choose 6} = \frac{49!}{6!43!} = 13983816

如同排列,上面的例子是建立在如下前提的(即球从摇奖机中出来后不再放回去,或者说组合不发生重复),但如果球摇出来后再放回摇奖机中,这时的组合的可能性则是:

H_n^k = C_{n+k-1}^{k} = {n+k-1 \choose k}

类似的例子比如连续掷两次骰子,获得的两个点数的组合可能性一共有:

H_6^2 = C_{6+2-1}^{2} = {6+2-1 \choose 2} = C_7^2 = \frac{7!}{2!5!} = 21

另外H_n^r也可以記為[3]

F_n^r = H_n^r = C_{n+r-1}^{r} = {n+r-1 \choose r}[3]

总结[编辑]

排列
{ a,b } ≠ { b,a }
(考慮順序)
组合
{ a,b } = { b,a }
(不考慮順序)
不重复出现(不放回去)
{ a,b,c }
P_n^k C_n^k
重复出现(再放回去)
{ a,a,b }
n^k \,  H_n^k

外部連結[编辑]

參考文獻[编辑]

  1. ^ 1.0 1.1 1.2 1.3 《数学辞海(第二卷)》山西教育出版社 中国科学技术出版社 东南大学出版社
  2. ^ 2.0 2.1 組合數學 ─算法與分析─. 九章出版社. : 29.  OCLC:44527392
  3. ^ 3.0 3.1 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392

参见[编辑]