组合数学（综述）

                     

贡献者： 待更新

　　 本文根据 CC-BY-SA 协议转载翻译自维基百科相关文章。

　　 组合数学是数学的一个分支，主要研究计数（counting）——既作为获得结果的方法，又作为研究有限结构某些性质的目的。它与数学的许多其他领域密切相关，并在从逻辑到统计物理、从进化生物学到计算机科学等众多领域中有广泛的应用。

　　 组合数学以其所处理问题的广泛性而著称。组合问题出现在纯数学的许多分支中，尤其是在代数学、概率论、拓扑学与几何学中 \(^\text{[1]}\)，同时也出现在众多应用领域。 历史上，许多组合问题往往是独立提出的，作为在某个数学背景下出现的特定问题的特设性解法（ad hoc solutions）。然而，在二十世纪后期，强大而一般的理论方法被发展出来，使得组合数学成为一门独立的数学分支 \(^\text{[2]}\)。组合数学中最古老且最易于理解的部分之一是图论（graph theory），它本身就与其他数学领域有着大量自然的联系。在计算机科学中，组合数学被广泛用于推导算法分析中的公式与估计。

1. 定义

　　 组合数学的确切范围并没有被普遍认同 \(^\text{[3]}\)。正如 H. J. Ryser 所指出的，由于组合数学跨越了众多数学分支，因此要给出一个精确的定义是困难的 \(^\text{[4]}\)。如果我们从其所研究的问题类型来描述这一领域，那么组合数学主要涉及以下几个方面：

  1. 枚举（enumeration）：对特定结构的计数，这些结构在广义上被称为排列（arrangements）或配置（configurations），它们通常与有限系统相关；
  2. 存在性（existence）：研究满足特定条件的结构是否存在；
  3. 构造性（construction）：探讨如何以一种或多种方式构造出这些结构；
  4. 优化（optimization）：在多种可能的结构或解中寻找 “最优” 的一个，无论其意义为 “最大”、“最小” 或符合其他最优性标准。

　　 Leon Mirsky 曾指出：“组合数学是一系列彼此关联的研究，它们有共同点，但在目标、方法以及所达到的统一程度上却差异很大。”\(^\text{[5]}\) 一种定义组合数学的方式，或许是通过描述它的各个分支（subdivisions）、它们所处理的问题以及所采用的技术。下文将采用这种方式来介绍组合数学。然而，从历史的角度看，是否将某些主题纳入组合数学的范畴，也存在一定的传统性和争议性 \(^\text{[6]}\)。尽管组合数学主要关注有限系统，但其中的一些问题与方法也可以推广到无限（尤其是可数）离散系统的情形。

2. 历史

图
图 1：一个换铃（change ringing）的例子（使用六个钟），这是图论（graph theory）中最早的非平凡成果之一。

　　 基本的组合概念与枚举结果在古代世界的许多地方早已出现。最早记录在案的组合技巧可追溯到公元前 16 世纪的《莱因德纸草书》（Rhind Papyrus）中的第 79 题。这一问题涉及一种几何级数，与斐波那契（Fibonacci）关于 “由若干个 1 和 2 的组合形成给定总和” 的计数问题有相似之处 \(^\text{[7]}\)。印度医师苏什鲁塔（Sushruta）在其著作《Sushruta Samhita》中指出，从六种不同味道中取一种、两种、……直到全部六种，共可形成 $2^{6}-1=63$ 种组合。希腊历史学家普鲁塔克（Plutarch）记载了斯多亚学派哲学家克律西波斯（Chrysippus，公元前 3 世纪）与天文学家喜帕恰斯（Hipparchus，公元前 2 世纪）之间的一场关于一个精妙枚举问题的争论，该问题后来被证明与施罗德–喜帕恰斯数（Schröder–Hipparchus numbers）有关 \(^\text{[8][9][10]}\)。更早时，阿基米德（Archimedes，公元前 3 世纪）在其著作《Ostomachion》中可能已考虑过一个平面拼图问题中不同拼图配置数（configurations）的计算 \(^\text{[11]}\)，而阿波罗尼乌斯（Apollonius）失传的部分著作中也可能包含类似的组合思想 \(^\text{[12][13]}\)。

　　 在中世纪时期，组合数学的研究主要在欧洲之外持续发展。印度数学家摩诃毗罗（Mahāvīra，约公元 850 年）给出了排列数与组合数的计算公式 \(^\text{[14][15]}\)，这些公式可能早在公元 6 世纪时就已为印度数学家所知 \(^\text{[16]}\)。犹太哲学家兼天文学家亚伯拉罕·伊本·以斯拉（Abraham ibn Ezra，约公元 1140 年）发现了二项式系数的对称性；而数学家利维·本·格尔松（Levi ben Gerson，亦称 Gersonides）则在 1321 年给出了其闭合形式 \(^\text{[17]}\)。展示二项式系数之间关系的算术三角形（arithmetical triangle）早在 10 世纪的数学论文中就已出现，它后来被称为帕斯卡三角形（Pascal’s triangle）。在中世纪的英格兰，钟学（campanology）的研究产生了当今所谓凯莱图（Cayley graphs）上的哈密顿环（Hamiltonian cycles）实例 \(^\text{[18][19]}\)。

　　 文艺复兴时期，伴随数学与科学的复兴，组合数学也焕发了新的生命力。帕斯卡（Pascal）、牛顿（Newton）、雅各布·伯努利（Jacob Bernoulli）与欧拉（Euler）的著作成为这一新兴领域的奠基之作。进入近代，J.J. Sylvester（19 世纪末）与 Percy MacMahon（20 世纪初）的工作奠定了枚举组合学（enumerative combinatorics）与代数组合学（algebraic combinatorics）的基础。与此同时，图论（graph theory）因与四色问题（four color problem）的联系而引发广泛关注。

　　 在 20 世纪下半叶，组合数学经历了迅速的发展，促成了数十种新的学术期刊与会议的创立 \(^\text{[20]}\)。这一增长部分得益于其与其他数学分支（如代数、概率论、泛函分析、数论等）之间的新联系与应用。这些跨界互动模糊了组合数学与数学及理论计算机科学其他领域之间的边界，同时也在某种程度上导致了该领域的局部分化。

3. 组合数学的研究方法与分支

枚举组合学

图
图 2：三个顶点上可能构成的五种二叉树（binary trees），是卡塔兰数（Catalan numbers）的一个例子。

　　 枚举组合学是组合数学中最经典的分支，主要研究如何计算特定组合对象（combinatorial objects）的数量。虽然 “计算集合中元素的数量” 是一个相当广泛的数学问题，但许多实际应用中出现的问题往往具有相对简单的组合描述。斐波那契数列（Fibonacci numbers）就是枚举组合学中最基本的例子之一。 著名的十二重分类（twelvefold way）为排列、组合与划分问题提供了一个统一的计数框架。

解析组合学

　　 解析组合学（Analytic Combinatorics）主要利用复分析与概率论的工具研究组合结构的枚举问题。与枚举组合学不同，后者通常依赖显式的组合公式与生成函数（generating functions）来表达结果，而解析组合学则旨在推导出渐近公式（asymptotic formulae），以揭示组合数量随规模增长时的行为规律。

划分理论

图
图 3：平面分拆

　　 划分理论研究与整数划分（integer partitions）相关的各种计数与渐近问题，并与 $q$-级数（$q$-series）、特殊函数（special functions）及正交多项式（orthogonal polynomials）密切相关。该领域最初属于数论与分析的一部分，但如今通常被视为组合数学的一个分支，或是一个独立学科。

　　 划分理论综合采用了双射方法（bijective approach）以及分析学与解析数论中的多种工具，并与统计力学（statistical mechanics）存在深刻联系。在几何上，整数划分可通过杨图（Young diagrams）或费雷图（Ferrers diagrams）进行可视化。划分理论在数学与物理的多个分支中均有应用，例如：对称多项式（symmetric polynomials）的研究；对称群（symmetric group）的结构分析；以及更一般的群表示论（group representation theory）。

图论

图
图 4：彼得森图

　　 图（graphs）是组合数学中最基本的对象之一。图论的研究内容十分广泛，既包括计数组合问题（例如：具有 $n$ 个顶点和 $k$ 条边的图的数量），也包括结构性问题（例如：哈密顿回路（Hamiltonian cycles）的存在性），以及代数表示问题（例如：给定一个图 $G$ 和两个数 $x, y$，Tutte 多项式 $T_G(x,y)$ 是否具有组合学解释？）。虽然图论与组合数学之间存在非常紧密的联系，但两者有时被视为独立的学科领域。\(^\text{[21]}\) 组合方法在许多图论问题中都有应用，但这两个领域通常关注不同类型的问题并使用不同的研究目标。

设计理论

　　 设计理论研究组合设计（combinatorial designs），即具有特定交集性质的子集集合。区组设计（block designs）是其中一种特殊类型。这一领域是组合数学中最古老的分支之一，其历史可追溯到 1850 年提出的柯克曼女学生问题（Kirkman's schoolgirl problem）。该问题的解是斯坦纳系统（Steiner system）的一个特例，而斯坦纳系统在有限单群分类中扮演着重要角色。此外，该领域还与编码理论（coding theory）和几何组合学（geometric combinatorics）密切相关。

　　 组合设计理论在实验设计（design of experiments）中有重要应用。统计学家罗纳德·费希尔（Ronald Fisher）在生物实验设计方面的工作奠定了其基础理论。现代应用还遍布众多领域，包括：有限几何（finite geometry）；比赛日程安排（tournament scheduling）；彩票设计（lotteries）；数学化学与数学生物学；算法设计与分析；网络与群体测试；密码学（cryptography）。\(^\text{[22]}\)

有限几何

　　 有限几何研究仅包含有限个点的几何系统。该领域主要研究与连续几何（如欧几里得平面、实射影空间等）类似、但以组合方式定义的结构。有限几何为设计理论提供了丰富的实例来源。需要注意的是，它不应与离散几何（Discrete Geometry，也称组合几何）混淆。

序理论

图
图 5：按包含关系排序的集合 \(\{x, y, z\}\) 的幂集的哈斯图

　　 序理论研究偏序集（partially ordered sets），包括有限与无限情形。它为诸如 “这个小于那个”（“this is less than that”）或 “这个先于那个”（“this precedes that”）等陈述提供了一个形式化的框架。偏序的各种实例广泛出现在代数、几何、数论、以及整个组合数学与图论中。偏序集的重要类型与例子包括：格（lattices）；布尔代数（Boolean algebras）。

拟阵理论

　　 拟阵理论抽象地推广了几何的一部分。它研究一组（通常是有限的）向量在向量空间中所具有的、不依赖于线性相关关系中具体系数的性质。拟阵理论不仅关注结构性质，也研究计数性质（enumerative properties）。该理论最早由哈斯勒·惠特尼（Hassler Whitney）提出，并最初作为序理论的一部分加以研究。如今，拟阵理论已成为一个独立的研究领域，并与组合数学的多个分支建立了密切联系。

极值组合学

　　 极值组合学研究：在满足特定约束的前提下，一个有限对象集（如数、图、向量、集合等）能够多大或多小。极值组合学的主要研究方向之一是极值集族理论（Extremal Set Theory）。例如：在一个含 $n$ 个元素的集合中，最多可以有多少个 $k$ 元子集使得它们两两相交？最多可以有多少个子集，使得任意一个都不包含另一个？第二个问题的答案由斯佩纳定理（Sperner’s Theorem）给出，该定理为极值集族理论奠定了基础。

　　 类似的问题还涉及满足特定性质的最大可能图。例如：在 $2n$ 个顶点上的最大三角形无关图（triangle-free graph）是一个完全二部图 $K_{n,n}$。在许多情况下，极值函数 $f(n)$ 的精确值过于复杂难以求得，因此通常只能给出其渐近估计（asymptotic estimate）。

　　 拉姆齐理论（Ramsey Theory）是极值组合学的另一个重要分支。它刻画了这样的原理：任何足够大的结构中都必然包含某种形式的 “秩序”。这一思想可视为抽屉原理（Pigeonhole Principle）的高阶推广。

概率组合学

图
图 6：方格网格图中的自回避行走。

　　 在概率组合学（Probabilistic Combinatorics）中，研究的问题通常如下：对于一个随机离散对象（例如随机图），某个特定性质出现的概率是多少？例如，一个随机图中平均会包含多少个三角形？概率方法还用于判断是否存在具有某些特定性质的组合对象（即使难以给出显式构造）。其思想是：如果随机选择一个对象时，选中具有这些性质的概率大于 0，则这样的对象必然存在。这种方法（通常称为概率方法（Probabilistic Method））在极值组合学（Extremal Combinatorics）和图论（Graph Theory）中具有极高的应用价值。与此密切相关的一个研究方向是有限马尔可夫链（Finite Markov Chains）在组合对象上的研究，其中再次运用了概率工具来估计混合时间（mixing time）。

　　 该领域通常与保罗·埃尔德什（Paul Erdős）联系在一起——他是该领域的奠基者。概率组合学最初被视为研究组合学其他分支问题的一套工具，但近年来已逐渐发展成为组合数学的一个独立分支。

代数组合学

图
图 7

　　 代数组合学（Algebraic Combinatorics）是数学的一个分支，它在各种组合情境中运用抽象代数的方法，尤其是群论（Group Theory）和表示论（Representation Theory），并且反过来也将组合技术应用于代数中的问题。随着研究的发展，代数组合学被更广泛地视为一个组合方法与代数方法交互尤为强烈且富有意义的数学领域。因此，代数组合学中的组合主题可能具有枚举（Enumerative）性质，或涉及拟阵（Matroids）、多面体（Polytopes）、偏序集（Partially Ordered Sets）或有限几何（Finite Geometries）等对象。在代数方面，除了群论和表示论之外，格论（Lattice Theory）与交换代数（Commutative Algebra）也是代数组合学中常见的研究工具。

词上的组合学

　　 词上的组合学（Combinatorics on Words）研究形式语言（Formal Languages）。它在数学的多个分支中独立产生，包括数论（Number Theory）、群论（Group Theory）与概率论（Probability）。该领域在枚举组合学（Enumerative Combinatorics）、分形分析（Fractal Analysis）、理论计算机科学（Theoretical Computer Science）、自动机理论（Automata Theory）以及语言学（Linguistics）中都有广泛的应用。尽管其中许多应用较为新颖，但乔姆斯基–舒岑贝格层次（Chomsky–Schützenberger Hierarchy）—— 即形式文法类别的经典分层结构，或许是该领域中最著名的成果。

几何组合学

图
图 8：一个二十面体。

　　 几何组合学（Geometric Combinatorics）与凸几何（Convex Geometry）和离散几何（Discrete Geometry）密切相关。它探讨的问题包括：一个凸多面体（Convex Polytope）在各个维度上可以拥有多少个面。多面体的度量性质（Metric Properties）同样起着重要作用，例如柯西定理（Cauchy Theorem）关于凸多面体刚性的结论。此外，还研究一些特殊的多面体，如置换多面体（Permutohedron）、结合多面体（Associahedron）以及伯克霍夫多面体（Birkhoff Polytope）。 “组合几何（Combinatorial Geometry）” 是离散几何的一个历史名称。

　　 几何组合学包含若干子领域，例如：多面体组合学（Polyhedral Combinatorics）：研究凸多面体的面结构；凸几何（Convex Geometry）：研究凸集，特别是其交集的组合性质；离散几何（Discrete Geometry）：其又在计算几何（Computational Geometry）中有广泛应用。此外，正多胞体（Regular Polytopes）、阿基米德立体（Archimedean Solids）以及接触数问题（Kissing Numbers）的研究也属于几何组合学的范畴。同样，置换多面体、结合多面体与伯克霍夫多面体等特殊多面体，都是该领域的重要研究对象。

拓扑组合学

图
图 9：用两刀分割项链。

　　 拓扑组合学使用拓扑学（Topology）中的概念和方法的组合论对应形式（Combinatorial Analogs），用于研究图染色（Graph Coloring）、公平划分（Fair Division）、集合划分（Partitions）、偏序集（Partially Ordered Sets）、决策树（Decision Trees）、项链问题（Necklace Problems）以及离散 Morse 理论（Discrete Morse Theory）等问题。需要注意的是，它不同于 “组合拓扑学（Combinatorial Topology）”，后者是代数拓扑学（Algebraic Topology）的旧称。

算术组合学

　　 算术组合学起源于数论（Number Theory）、组合数学（Combinatorics）、遍历理论（Ergodic Theory）和调和分析（Harmonic Analysis）之间的相互作用。它研究与算术运算（加、减、乘、除）相关的组合估计（Combinatorial Estimates）。其中，当仅涉及加法与减法运算时的特殊情形称为加性数论（Additive Number Theory）或加性组合学（Additive Combinatorics）。算术组合学中的一个重要技术是动力系统的遍历理论（Ergodic Theory of Dynamical Systems）。

无穷组合学

　　 无穷组合学（又称组合集论 Combinatorial Set Theory）是将组合思想扩展到无限集合（Infinite Sets）的研究领域。它属于集合论（Set Theory）（数理逻辑的一个分支），但同时借鉴了集合论与极值组合学（Extremal Combinatorics）的思想与工具。该领域研究的对象包括连续图与树（Continuous Graphs and Trees）、 Ramsey 定理的扩展（Extensions of Ramsey’s Theorem）、以及 Martin 公理（Martin’s Axiom）等。近年的发展涉及连续统的组合学（Combinatorics of the Continuum）\(^\text{[23]}\) 与奇异基数后继的组合学（Combinatorics on Successors of Singular Cardinals）\(^\text{[24]}\)。

　　 Gian-Carlo Rota 曾使用 “连续组合学（Continuous Combinatorics）” 一词来描述几何概率论（Geometric Probability）\(^\text{[25]}\)，因为计数（Counting）与测度（Measure）之间存在许多类比关系。

4. 相关领域

图
图 10：相互接触的球体同时与编码理论和离散几何密切相关。

组合优化

　　 组合优化研究的是离散（Discrete）与组合对象（Combinatorial Objects）上的优化问题。它起源于组合数学（Combinatorics）和图论（Graph Theory），但现已被视为应用数学（Applied Mathematics）与计算机科学（Computer Science）的一个分支，与运筹学（Operations Research）、算法理论（Algorithm Theory）以及计算复杂性理论（Computational Complexity Theory）密切相关。

编码理论

　　 编码理论最初起源于设计理论（Design Theory），源自对纠错码（Error-Correcting Codes）的早期组合构造。其主要思想是设计高效且可靠的数据传输方法（Efficient and Reliable Methods of Data Transmission）。如今，它已成为信息论（Information Theory）的重要分支。

离散与计算几何

　　 离散几何（Discrete Geometry）（又称组合几何 Combinatorial Geometry） 最初也是组合数学的一部分，其早期成果包括关于凸多面体（Convex Polytopes）和接触数（Kissing Numbers）的问题。随着离散几何在计算几何（Computational Geometry）中的应用出现，这两个领域逐渐融合，并形成了一个独立的研究方向。 它仍与几何组合学（Geometric Combinatorics）和拓扑组合学（Topological Combinatorics）保持紧密联系——后两者可以看作早期离散几何的延伸。

组合数学与动力系统

　　 动力系统的组合方面是一个新兴的研究领域。在这里，动力系统（Dynamical Systems）可以定义在组合对象（Combinatorial Objects）上。例如，参见图动力系统（Graph Dynamical System）的研究。

组合数学与物理学

　　 组合数学与物理学（Physics），尤其是统计物理（Statistical Physics）之间的联系日益紧密。例如：伊辛模型（Ising Model）的精确解是组合方法的典型应用；Potts 模型（Potts Model）与色多项式（Chromatic Polynomial）和 Tutte 多项式（Tutte Polynomial）之间也存在深刻的联系。

5. 另见

6. 注释

  1. Björner 与 Stanley，第 2 页
  2. Lovász, László (1979). Combinatorial Problems and Exercises. North-Holland. ISBN 978-0821842621. 归档日期：2021-04-16，检索日期：2021-03-23。作者写道：“在我看来，组合学正在从其早期阶段成长出来。”
  3. Pak, Igor. “What is Combinatorics?” 归档于 2017 年 10 月 17 日，检索于 2017 年 11 月 1 日。
  4. Ryser 1963，第 2 页。
  5. Mirsky, Leon (1979). “书评 (Book Review)” (PDF), 美国数学学会通报（Bulletin of the American Mathematical Society）, 新系列, 1: 380–388, doi:10.1090/S0273-0979-1979-14606-8, PDF 版本归档于 2021-02-26, 检索于 2021-02-04。
  6. Rota, Gian Carlo (1969). Discrete Thoughts. Birkhäuser. 第 50 页. doi:10.1007/978-0-8176-4775-9. ISBN 978-0-8176-4775-9. “……组合理论孕育了当代数学中几个最活跃的分支，并且它们已成为独立的领域……典型的例子是代数拓扑（过去称为组合拓扑）。”
  7. Biggs, Norman; Lloyd, Keith; Wilson, Robin (1995). “第 44 章”. 载于 Ronald Graham, Martin Grötschel, László Lovász 编. Handbook of Combinatorics. MIT Press. 第 2163–2188 页. ISBN 0262571722. 检索于 2008-03-08。
  8. Acerbi, F. (2003). “On the shoulders of Hipparchus”. Archive for History of Exact Sciences. 57 (6): 465–502. doi:10.1007/s00407-003-0067-0. S2CID 122758966. 归档于 2022-01-23，检索于 2021-03-12。
  9. Stanley, Richard P. “Hipparchus, Plutarch, Schröder, and Hough”, American Mathematical Monthly, 104 (1997), no. 4, 344–350.
  10. Habsieger, Laurent; Kazarian, Maxim; Lando, Sergei (1998). “On the Second Number of Plutarch”. The American Mathematical Monthly. 105 (5): 446. doi:10.1080/00029890.1998.12004906.
  11. Netz, R.; Acerbi, F.; Wilson, N. “Towards a reconstruction of Archimedes' Stomachion”. Sciamvs. 5: 67–99. 归档于 2021-04-16，检索于 2021-03-12。
  12. Hogendijk, Jan P. (1986). “Arabic Traces of Lost Works of Apollonius”. Archive for History of Exact Sciences. 35 (3): 187–253. doi:10.1007/BF00357307.
  13. Huxley, G. (1967). “Okytokion”.Greek, Roman, and Byzantine Studies. 8 (3): 203.
  14. O'Connor, John J.; Robertson, Edmund F. “Combinatorics”. \textit{MacTutor History of Mathematics Archive}, University of St Andrews.
  15. Puttaswamy, Tumkur K. (2000). “The Mathematical Accomplishments of Ancient Indian Mathematicians”. 见 Helaine Selin 编，《Mathematics Across Cultures: The History of Non-Western Mathematics》. Netherlands: Kluwer Academic Publishers. 第 417 页. ISBN 978-1-4020-0260-1.
  16. Biggs, Norman L. (1979). “The Roots of Combinatorics”. \textit{Historia Mathematica}. 6 (2): 109–136. doi:10.1016/0315-0860(79)90074-0.
  17. Maistrov, L.E. (1974). Probability Theory: A Historical Sketch. Academic Press. 第 35 页. ISBN 978-1-4832-1863-2. 英译自 1967 年俄文版。
  18. White, Arthur T. (1987). “Ringing the Cosets”. The American Mathematical Monthly. 94 (8): 721–746. doi:10.1080/00029890.1987.12000711.
  19. White, Arthur T. (1996). “Fabian Stedman: The First Group Theorist?”. The American Mathematical Monthly. 103 (9): 771–778. doi:10.1080/00029890.1996.12004816.
  20. “Journals in Combinatorics and Graph Theory”，归档于 2021-02-17。
  21. Sanders, Daniel P. “2-Digit MSC Comparison”，归档于 2008-12-31。
  22. Stinson 2003，第 1 页。
  23. Andreas Blass，《Combinatorial Cardinal Characteristics of the Continuum》，见《Handbook of Set Theory》第 6 章，Matthew Foreman 与 Akihiro Kanamori 主编，Springer，2010。
  24. Eisworth, Todd (2010). 载于 Foreman, Matthew; Kanamori, Akihiro (编), “Successors of Singular Cardinals”, Handbook of Set Theory. Dordrecht: Springer Netherlands. 第 1229–1350 页. doi:10.1007/978-1-4020-5764-9_16. ISBN 978-1-4020-4843-2. 检索于 2022-08-27。
  25. “Continuous and Profinite Combinatorics” (PDF). 归档于 2009-02-26，检索于 2009-01-03。

7. 参考文献

8. 外部链接

                     

© 保留一切权利