KNOWECON WIKI

ARTICLE

组合数学

组合数学 (Combinatorics) 组合数学（Combinatorics）是数学中研究离散对象的计数、排列、组合和结构的分支。它关注有限集合中元素的选取与安排方式，在概率论、计算机科学、统计学和经济学中具有广泛应用。组合数学的核心问题是计算满足特定条件的对象数量，其方法涵盖从基本乘加原理到复杂的生成函数和波利亚计数理论。 基本计数原理 组合计数的基础建

浏览 9 更新 2025-10-26

组合数学 (Combinatorics)

组合数学（Combinatorics）是数学中研究离散对象的计数、排列、组合和结构的分支。它关注有限集合中元素的选取与安排方式，在概率论、计算机科学、统计学和经济学中具有广泛应用。组合数学的核心问题是计算满足特定条件的对象数量，其方法涵盖从基本乘加原理到复杂的生成函数和波利亚计数理论。

基本计数原理

组合计数的基础建立在两个基本原理之上。加法原理指，若一项任务可通过互斥的两种方式完成，方式A有m种方法、方式B有n种方法，则完成任务共有 m+nm+n 种方法。乘法原理指，若任务需先后两个独立步骤，第一步有m种方法、第二步有n种方法，则共有 m×nm \times n 种方法。两原理的组合构成所有计数的逻辑基础：复杂计数问题通过分解为互斥情况（加法）和独立步骤（乘法）的组合求解。

排列与组合

排列（Permutation）是从n个不同元素中选取r个的有序安排。不重复排列数为 P(n,r)=n!/(n−r)!P(n,r) = n!/(n-r)!；全排列数为 P(n,n)=n!P(n,n) = n!。圆排列数为 (n−1)!(n-1)!。可重复排列数为 nrn^r。

组合（Combination）是从n个不同元素中选取r个的无序集合。组合数为二项式系数：

(nr)=n!r!(n−r)!\binom{n}{r} = \frac{n!}{r!(n-r)!}

基本恒等式包括对称性 (nr)=(nn−r)\binom{n}{r} = \binom{n}{n-r}、加法公式 (nr)=(n−1r−1)+(n−1r)\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}，以及二项式定理：

(x+y)n=∑k=0n(nk)xn−kyk(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k

重要工具与原理

鸽巢原理（Pigeonhole Principle）：若将 n+1n+1 个物体放入n个盒子，则至少有一个盒子包含不少于两个物体。该原理在存在性证明中极为有力。

容斥原理（Inclusion-Exclusion Principle）：计算若干集合并集的大小时，先加各集合大小，再减两两交集大小，再加三三交集大小，以此交替。对于n个集合 A1,…,AnA_1, \ldots, A_n：

∣⋃i=1nAi∣=∑i∣Ai∣−∑i<j∣Ai∩Aj∣+∑i<j<k∣Ai∩Aj∩Ak∣−⋯|\bigcup_{i=1}^n A_i| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots

生成函数（Generating Function）：将序列 a0,a1,a2,…a_0, a_1, a_2, \ldots 编码为幂级数 G(x)=∑k≥0akxkG(x) = \sum_{k \ge 0} a_k x^k，将组合计数转化为代数运算。普通生成函数处理无标号组合，指数生成函数 E(x)=∑k≥0akxk/k!E(x) = \sum_{k \ge 0} a_k x^k/k! 适合处理带标号的排列。

递推关系（Recurrence Relation）将问题规模n的解表达为较小规模解的函数。例如斐波那契数 Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} 的闭式解可通过特征方程法求得。

在经济学中的应用

组合数学在博弈论中用于计算策略组合数量：n个参与者每人有m个纯策略时，纯策略组合总数为 mnm^n。在机制设计中，计算可能的分配方案数量涉及排列组合。在概率论中，组合数为等可能结果的计数提供了基础。计算抽样中不同样本组合的数量、构造假设检验中精确的p值时，组合恒等式不可或缺。组合数学作为离散结构的语言，为经济学中涉及有限选择和离散优化的模型提供了基本的计数与分析工具。