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

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

目录 1 历史 2 组合数学中的著名问题 3 排列 4 组合 5 总结 6 参见 7 参考文献 8 外部链接 历史

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数有关的枚举问题[1][2]；公元前3世纪的阿基米德在其数学文章Ostomachion中讲述拼接拼图的智力游戏（tiling puzzle）。

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

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

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

组合数学中的著名问题 计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆。 地图着色问题：为地图填色，每区用一色。如果要邻区颜色相异，是否只需四色？这是图论题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊，但船每次只能运送一种东西。怎样把所有东西运过河？这是线性规划题。 中国邮差问题：由中华民国组合数学家管梅谷教授提出。邮差要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。也是图论题。 任务分配问题（也称分配问题）：有一些员工要完成一些任务。各员工完成不同任务用的时间都不同。每个员工只分配一项任务。每项任务只分给一个员工。怎样分配员工与任务以使所花费的时间最少？也是线性规划题。 如何构造幻方： 幻方为一方阵，填入不重复之自然数，并使其中每一纵列、横列、对角线内数字之和皆相同。 数独：游戏一般由9个3×3个的九宫格组成。每一列的数字均须包含 1～9，不能缺少，也不能重复。每一宫(粗黑线围起来的区域，通常是 3x3 的九宫格)的数字均须包含 1～9，不能缺少，也不能重复。参见Mathematics_of_Sudoku 排列 主条目：排列 从 � n个元素取出 � k个元素， � k个元素的排列数量为：

� � �

� ! ( � − � ) ! P_{k}^{n}={\frac {n!}{(n-k)!}} 以赛马为例，有8匹马参赛，玩家需在彩票上填入前三匹胜出的马匹号码，从8匹马取出3匹来排前3名，排列数量为：

� 3 8

8 ! ( 8 − 3 ) !

8 × 7 × 6

336 {\displaystyle P_{3}^{8}={\frac {8!}{(8-3)!}}=8\times 7\times 6=336} 因为有336种排列，因此玩家在一次填入中中奖的概率是：

�

1 336

0.00298 P={\frac {1}{336}}=0.00298 不过，中国大陆的教科书则是把从n取k的情况记作 � � � {\displaystyle P_{n}^{k}}或 � � � {\displaystyle A_{n}^{k}}（A代表Arrangement，即排列[9]）。

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

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

� � �

� � U_{k}^{n}=n^{k}[10] 以四星彩为例，10个数取4个，因可能重复所以排列数量为：

� 4 10

10 4

10000 U_{4}^{10}=10^{4}=10000 这时的一次性添入中奖的概率就是：

�

1 10000

0.0001 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的情况记作 � � � {\displaystyle C_{n}^{k}}[11]。

以香港六合彩为例，六合彩49颗球选6颗的组合数量为：

� 6 49

( 49 6 )

49 ! 6 ! 43 !

13983816 C_{{6}}^{{49}}={49 \choose 6}={\frac {49!}{6!43!}}=13983816 如同排列，上面的例子是建立在取出元素不重复出现状况。

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

� � �

� � � + � − 1 H_{k}^{n}=C_{k}^{n+k-1} 以取色球为例，每种颜色的球有无限多颗，从8种色球取出5颗球，这组合数量为：

� 5 8

� 5 8 + 5 − 1

� 5 12

12 ! 5 ! 7 !

792 H_{5}^{8}=C_{5}^{8+5-1}=C_{5}^{12}={\frac {12!}{5!7!}}=792 因为组合数量公式特性，重复组合转换成组合有另一种公式为：

� � �

� � � + � − 1

( � + � − 1 ) ! � ! ( � − 1 ) !

� � − 1 � + � − 1 {\displaystyle 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}[12]

� � �

� � � F_{k}^{n}=H_{k}^{n} 总结 � n中取 � k 直线排列 （考虑顺序） 环状排列 组合 （不考虑顺序） 不重复出现 （不放回去） � � �

� ! ( � − � ) ! {\displaystyle P_{k}^{n}={\frac {n!}{(n-k)!}}} （OEIS数列A008279） � ! � ⋅ ( � − � ) ! {\displaystyle {\frac {n!}{k\cdot (n-k)!}}} （OEIS数列A111492） � � �

� ! � ! ⋅ ( � − � ) ! {\displaystyle C_{k}^{n}={\frac {n!}{k!\cdot (n-k)!}}} （OEIS数列A007318） 可重复出现 （再放回去） � � �

� � {\displaystyle U_{k}^{n}=n^{k}} （OEIS数列A004248） ∑ � | � ( � ⋅ � ( � ) ⋅ � � � ) � {\displaystyle {\frac {\sum _{r|k}(r\cdot \varphi (r)\cdot n^{\frac {k}{r}})}{k}}} （OEIS数列A075195） � � �

( � + � − 1 ) ! � ! ⋅ ( � − 1 ) ! {\displaystyle H_{k}^{n}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}} （OEIS数列A097805） 参见 阶乘 阶乘符号 排列 组合

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: