组合学查看源代码讨论查看历史
| 组合学 | |
|---|---|
组合学，简称组态的数学分支，也称组合数学，它研究的是满足各种附加条件的有限个对象的集合。组合学所研究的问题有:计数问题、存在性问题、枚举、构造和算法问题、优化问题等。组合学分为几大部分:图论、组合计数、组合设计、组合最优化和组合几何等。
基本信息
中文名 组合学 [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（种）不同的选法．
【反思】 区分排列与组合的关键是“有序”与“无序