组合数学

广义的组合数学（英语：Combinatorics）就是离散数学，狭义的组合数学是组合计数、图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究可数或离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。 组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化（最佳组合）等。最基本的组合数学的思想和枚举的方法在古老时代就已经出现。公元前6世纪的古印度外科医生妙闻已经指出可以由6个相异的味道组合出63种相异的结果（每个味道都可以选择或不选择，但不能都不选择，因此有26 − 1=63种组合）；罗马时代的希腊史家普鲁塔克与克律西波斯、喜帕恰斯讨论了后来显示与Schröder–Hipparchus数（英语：Schröder–Hipparchus number）有关的枚举问题；公元前3世纪的阿基米德在其数学文章Ostomachion（英语：Ostomachion）中考虑了一个拼接拼图的智力游戏（tiling puzzle）。中世纪时，组合数学持续发展（主要是在欧洲外的文明）。公元850年的印度数学家Mahāvīra（英语：Mahāvīra (mathematician)）提供了关于排列数与组合的公式，甚至可能早在6世纪印度的数学家就对这些公式熟悉 。公元1140年哲学家与天文学家阿伯拉罕·伊本·埃兹拉确认了二项式系数的对称性，而二项式系数公式则是由犹太人数学家Gersonides在公元1321年得到的。杨辉三角形最早可追溯至10世纪的数学论文，在中国则首现于13世纪南宋杨辉的《详解九章算法》。在英格兰，则出现一些与哈密顿回路相关的例子。文艺复兴时期，与其他数学或科学领域一样，组合数学再现生机。帕斯卡、牛顿、雅各布·白努利、欧拉等人的研究为此新兴领域打下基础。在更近代时，西尔维斯特和MacMahon（英语：Percy Alexander MacMahon）也对组合计数和代数组合学作出贡献。人们此时也对图论有高度的兴趣，例如关于四色问题的领域。在20世纪下半叶，组合数学成长相当快速，甚至出现数十种新的期刊和会议。 在某种程度上，这样的成长是由对其他领域的连结与应用所带动，包括代数、几率论、泛函分析和数论等。从 n {displaystyle n} 个元素中取出 k {displaystyle k} 个元素， k {displaystyle k} 个元素的排列数量为：以赛马为例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，从8匹马中取出3匹马来排前3名，排列数量为：因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：不过，中国大陆的教科书则是把从n取k的情况记作 P n k {displaystyle P_{n}^{k}} 或 A n k {displaystyle A_{n}^{k}} （A代表Arrangement，即排列）。上面的例子是建立在取出元素不重复出现状况。从 n {displaystyle n} 个元素中取出 k {displaystyle k} 个元素， k {displaystyle k} 个元素可以重复出现，这排列数量为：以四星彩为例，10个数字取4个数字，因可能重复所以排列数量为：这时的一次性添入中奖的概率就应该是：和排列不同的是，组合取出元素的顺序不考虑。从 n {displaystyle n} 个元素中取出 k {displaystyle k} 个元素， k {displaystyle k} 个元素的组合数量为：不过，中国大陆的教科书则是把从n取k的情况记作 C n k {displaystyle C_{n}^{k}} 。以六合彩为例。在六合彩中从49颗球中取出6颗球的组合数量为：如同排列，上面的例子是建立在取出元素不重复出现状况。从 n {displaystyle n} 个元素中取出 k {displaystyle k} 个元素， k {displaystyle k} 个元素可以重复出现，这组合数量为：以取色球为例，每种颜色的球有无限多颗，从8种色球中取出5颗球，这组合数量为：因为组合数量公式特性，重复组合转换成组合有另一种公式为：另外 H k n {displaystyle H_{k}^{n}} 也可以记为 F k n {displaystyle F_{k}^{n}}