组合数学

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

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

历史

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

最基本的组合数学的思想和枚举的方法在古老时代就已经出现。公元前6世纪的古印度外科医生妙闻已经指出可以由6个相异的味道组合出63种相异的结果（每个味道都可以选择或不选择，但不能都不选择，因此有2⁶ − 1=63种组合）；罗马时代的希腊史家普鲁塔克与克律西波斯、喜帕恰斯讨论了后来显示与Schröder–Hipparchus数有关的枚举问题；公元前3世纪的阿基米德在其数学文章Ostomachion中考虑了一个拼接拼图的智力游戏（tiling puzzle）。

中世纪时，组合数学持续发展（主要是在欧洲外的文明）。公元850年的印度数学家Mahāvīra提供了关于排列数与组合的公式，甚至可能早在6世纪印度的数学家就对这些公式熟悉。1140年哲学家与天文学家阿伯拉罕·伊本·埃兹拉确认了二项式系数的对称性，而二项式系数公式则是由犹太人数学家Gersonides在1321年得到的。杨辉三角形最早可追溯至10世纪的数学论文，在中国则首现于13世纪南宋杨辉的《详解九章算法》。在英格兰，则出现一些与哈密顿回路相关的例子。

文艺复兴时期，与其他数学或科学领域一样，组合数学再现生机。帕斯卡、牛顿、雅各布·白努利、欧拉等人的研究为此新兴领域打下基础。在更近代时，西尔维斯特和MacMahon也对组合计数和代数组合学作出贡献。人们此时也对图论有高度的兴趣，例如关于四色问题的领域。

在20世纪下半叶，组合数学成长相当快速，甚至出现数十种新的期刊和会议。 在某种程度上，这样的成长是由对其他领域的连结与应用所带动，包括代数、几率论、泛函分析和数论等。

组合数学中的著名问题

• 计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。
• 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。
• 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。
• 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。
• 任务分配问题（也称分配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。
• 如何构造幻方。 幻方为一方阵，填入不重复之自然数，并使其中每一纵列、横列、对角线内数字之总和皆相同。

排列

主条目：排列

从$n$个元素中取出$k$个元素，$k$个元素的排列数量为：

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

以赛马为例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，从8匹马中取出3匹马来排前3名，排列数量为：

$P_3^8 =\frac{8!}{(8-3)!}=8\times7\times6=336$

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

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

不过，中国的教科书则是把从n取k的情况记作$P^k_n$或$A^k_n$（A代表Arrangement，即排列）。

上面的例子是建立在取出元素不重复出现状况。

从$n$个元素中取出$k$个元素，$k$个元素可以重复出现，这排列数量为：

$U_k^n = n^k$

以四星彩为例，10个数字取4个数字，因可能重复所以排列数量为：

$U_4^{10}=10^4=10000$

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

$P=\frac{1}{10000}=0.0001$

组合

主条目：组合

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

从$n$个元素中取出$k$个元素，$k$个元素的组合数量为：

$C_k^n ={n \choose k} = \frac{P_k^n}{k!} = \frac{n!}{k!(n-k)!}$

不过，中国的教科书则是把从$n$取$k$的情况记作$C^k_n$。

以六合彩为例。在六合彩中从49颗球中取出6颗球的组合数量为：

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

如同排列，上面的例子是建立在取出元素不重复出现状况。

从$n$个元素中取出$k$个元素，$k$个元素可以重复出现，这组合数量为：

$H_k^n = C_{k}^{n+k-1}$

以取色球为例，每种颜色的球有无限多颗，从8种色球中取出5颗球，这组合数量为：

$H_5^8 = C_{5}^{8+5-1} = C_5^{12} = \frac{12!}{5!7!} = 792$

因为组合数量公式特性，重复组合转换成组合有另一种公式为：

$H_k^n=C_k^{n+k-1}=\frac{(n+k-1)!}{k!(n-1)!}=C_{n-1}^{n+k-1}$

另外$H_k^n$也可以记为$F_k^n$

$F_k^n = H_k^n$

总结

$n$中取$k$	直线排列 （考虑顺序）	环状排列	组合 （不考虑顺序）
不重复出现 （不放回去）	$P^n_k=\frac{n!}{(n-k)!}$ （OEIS中的数列A008279）	$\frac{n!}{k \cdot (n-k)!}$ （OEIS中的数列A111492）	$C^n_k=\frac{n!}{k! \cdot (n-k)!}$ （OEIS中的数列A007318）
可重复出现 （再放回去）	$U^n_k=n^k$ （OEIS中的数列A004248）	$\frac{\sum_{r|k}(r \cdot \varphi(r) \cdot n^{\frac{k}{r}})}{k}$ （OEIS中的数列A075195）	$H^n_k=\frac{(n+k-1)!}{k! \cdot (n-1)!}$ （OEIS中的数列A097805）

参见

• 阶乘
• 阶乘符号
• 排列
• 组合

外部链接

• The Combinatorics Net
• Electronic Journal of Combinatorics
• 点算的奥秘