组合数学中的组合偏序集 我们先从最基础的概念开始建立理解框架。偏序集（partially ordered set，简称poset）是指一个集合P配上一个二元关系≤，这个关系满足三个基本性质： 自反性：对任意x∈P，x≤x 反对称性：如果x≤y且y≤x，则x=y 传递性：如果x≤y且y≤z，则x≤z 在组合数学中研究的偏序集通常具有有限个元素，这使得我们可以用组合工具研究其结构性质。 让我介绍偏序集的图示表示方法——哈斯图（Hasse diagram）。在哈斯图中： 每个元素用点表示 如果x<y且不存在z使得x<z <y，则在x和y之间连一条边 y画在x的上方 例如，集合{1,2,3}的所有子集按包含关系构成的偏序集，其哈斯图形成一个立方体的骨架。 现在考虑偏序集中的特殊元素： 极小元：不存在x <a的元素a 极大元：不存在x>a的元素a 最小元：对所有x∈P，有a≤x 最大元：对所有x∈P，有x≤a 一个重要的概念是链（chain）和反链（antichain）： 链：P的子集，其中任意两个元素可比 反链：P的子集，其中任意两个元素不可比 迪尔沃斯定理（Dilworth定理）建立了链分解与反链大小的深刻联系：偏序集分解成链的最小数等于最大反链的大小。对偶的，分解成反链的最小数等于最大链的大小。 接下来介绍格（lattice）的概念。如果一个偏序集中任意两个元素都有最小上界（并）和最大下界（交），则称为格。例如： 布尔格：集合的所有子集按包含关系构成的格 划分格：集合的所有划分按加细关系构成的格 在组合计数中，莫比乌斯函数μ(x,y)是研究偏序集的重要工具。它递归定义为： μ(x,x) = 1 μ(x,y) = -Σ_ {x≤z<y} μ(x,z)，当x <y μ(x,y) = 0，其他情况 莫比乌斯反演公式允许我们在两个函数之间转换：如果g(x)=Σ_ {y≤x} f(y)，那么f(x)=Σ_ {y≤x} μ(y,x) g(y)。 偏序集的组合不变量包括： 序多项式：计数从P到{1,2,...,n}的保序映射个数 秩生成函数：按秩统计元素个数的生成函数 特征多项式：与莫比乌斯函数相关的多项式 Sperner定理是极值集合论在偏序集中的典型应用：在n元集合的子集格中，最大反链的大小是C(n, ⌊n/2⌋)，即中间一层的所有子集。 偏序集的组合研究还延伸到： 分配格：满足分配律的格 模格：满足模律的格 几何格：来自拟阵理论的格结构 这些概念在组合数学、代数、几何以及计算机科学中都有广泛应用，为理解离散结构的序关系提供了有力工具。