Revision 25312767 of "组合数学" on zhwiki

{{copyedit|time=2012-12-07T13:19:37+00:00}}
'''组合数学'''（combinatorics），亦称'''組合論'''、'''组合学'''，[[数学]]的一个分支，亦即[[離散數學]]中的[[排列組合]]研究，所研究的是[[計数]]的技巧<ref name="gzfjt">《数学辞海（第二卷）》山西教育出版社 中国科学技术出版社 东南大学出版社</ref>。

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

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

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

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

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

于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年提出的关于[[双随机矩阵积和式猜想]]的证明；[[希伍德]]（Heawood，P.J.）于1890年提出的[[曲面地图着色猜想]]的解决;著名的四色定理的计算机验证和扭结问题的新组合不变量发现等。在数学中已经或正在形成着诸如[[组合拓扑]]、[[组合几何]]、[[组合数论]]、[[组合矩阵论]]、[[组合群论]]等与组合学密切相关的交叉学科。此外，组合学也正在渗透到其他自然科学以及社会科学的各个方面，例如，物理学、力学、化学、生物学、遗传学、心理学以及经济学、管理学甚至政治学等。<ref name="gzfjt"/>

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

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

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

== 排列 ==
{{main|排列}}
[[File:Permutations RGB.svg|thumb|130px|3个彩球的排列（不重复出现）]]
排列的任务是确定<math>n</math>个不同的元素的排序的可能性。从右边的示意图可看出，3个不同颜色的彩球一共有6种不同的排列方式，因此有如下定理：「<math>n</math>个不同的元素可以有<math>n !</math>种不同的排列方式，即<math>n</math>的[[阶乘]]。」因此上面的例子的算法是3 ! = 6。<br />另一个问题，如果从<math>n</math>个元素中取出<math>k</math>个元素，这<math>k</math>个元素的排列是多少呢？公式如下：
:<math> P_n^k = \frac{n!}{(n-k)!}</math>
例如，在赌马游戏中一共有8匹马参加比赛，玩家需要在彩票上填入前三位胜出的马匹的号码，按照上面的公式，<math>n</math> ＝ 8，<math>k</math> ＝ 3，玩家一共可以填出的3匹马号的排列数为：<br />
:<math> P_8^3 =\frac{8!}{(8-3)!}=336</math><br />
因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：<br />
:<math> P = \frac{1}{336}= 0.00298</math>

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

如果在<math>n</math>个元素中取出<math>k</math>个元素进行排列，这<math>k</math>个元素可以重复出现，那么排列数则有如下公式：
:<math>n^k</math>
还是上面的例子，<math>k</math>可以重复出现，这意味着玩家可以在前三名的位置上填入同一匹马号，因此在这种情况下可能出现的排列总数为：<br />
:8<sup>3</sup> = 512<br />
另外，<math>n^k</math>也可以記為<ref name="組合數學">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 |  pages=29}} OCLC:44527392 </ref>
::<math> U_n^k = n^k</math><ref name="組合數學"/>
这时的一次性添入中奖的概率就应该是：
:<math>P=\frac{1}{512}=0.002</math>（当然，同一匹马同时获得1，2，3名的情况在现实中是不存在的）

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

== 组合 ==
{{main|組合}}
和排列不同的是，在组合中取出元素的顺序则不在考虑之中。从<math>n</math>个元素中取出<math>k</math>个元素，这<math>k</math>个元素可能出现的组合数为：
:<math>C_n^k ={n \choose k} = \frac{P_n^k}{k!} = \frac{n!}{k!(n-k)!}</math>

最常见的例子应该是六合彩游戏了。在六合彩游戏中从49个球中取出6个进行组合的可能性一共有：
:<math>C_{49}^{6}  = {49 \choose 6} = \frac{49!}{6!43!} = 13983816</math>

如同排列，上面的例子是建立在如下前提的（即球从摇奖机中出来后不再放回去，或者说组合不发生重复)，但如果球摇出来后再放回摇奖机中，这时的组合的可能性则是：
:<math>H_n^k = C_{n+k-1}^{k} = {n+k-1 \choose k}</math>
类似的例子比如连续掷两次骰子，获得的两个点数的组合可能性一共有：
:<math>H_6^2 = C_{6+2-1}^{2} = {6+2-1 \choose 2} = C_7^2 = \frac{7!}{2!5!} = 21</math>

另外<math>H_r^n</math>也可以記為<ref name="組合數學P33">{{cite book | title=組合數學 ─算法與分析─ | publisher=九章出版社 |  pages=33}} OCLC:44527392 </ref>
:<math>F_r^n = H_r^n = C_{r}^{n+k-1} = {n+k-1 \choose r}</math><ref name="組合數學P33"/>

== 总结 ==
{| class="wikitable" style="margin: 0 auto; text-align:center; width:50em;"
!style="background-color:#CCCCFF;"|
! style="background-color:#CCCCFF;"|'''排列''' <br /> { a,b } ≠ { b,a }<br />（考慮順序）
! style="background-color:#CCCCFF;"|'''组合''' <br /> { a,b } = { b,a } <br />（不考慮順序）
|-
| style="background-color:#CCCCFF;"| '''不重复出现（不放回去）''' <br />{ a，b，c }
| <math>P_n^k</math> 
| <math>C_n^k</math> 
|-
| style="background-color:#CCCCFF;"|  '''重复出现（再放回去）''' <br />{ a，a，b }
| <math>n^k \,</math>
| <math> H_n^k</math>
|-
|}

== 外部連結 ==
* [http://www.combinatorics.net/ The Combinatorics Net]
* [http://www.combinatorics.org/ Electronic Journal of Combinatorics]
* [http://www.geocities.com/kfzhouy/Mathtopic.html#Enumeration 点算的奥秘]

==參考文獻==
<references/>

[[Category:组合数学|*]]
[[Category:离散数学]]

==参见==
*[[排列组合符号]]
*[[阶乘]]
*[[阶乘符号]]
*[[排列]]