基于分配格的扩展 Min-Max 容斥

zifanwang · 2025-09-11 15:46:36 · 算法·理论

本文同步发表于 https://www.cnblogs.com/zifanoi/p/19164122，借助 ChatGPT 整理与完善。

1. 基本定义与记号

偏序集（Poset）：一对 (P,\preccurlyeq)，P 为集合，\preccurlyeq 为满足自反、反对称、传递的二元关系。写 x\prec y 表示 x\preccurlyeq y 且 x\neq y。
上确界 / 下确界（join / meet）：
对 x,y\in P，如果存在最大下界则称为 meet，记作 x\wedge y；如果存在最小上界则称为 join，记作 x\vee y。
格（Lattice）：若对任意 x,y\in P 都存在 x\wedge y 与 x\vee y，则 (P,\preccurlyeq) 称为格，记作 L=(L,\preccurlyeq)。
分配格（Distributive lattice）：格 L 若对任意 x,y,z\in L 满足分配律
x\vee(y\wedge z)=(x\vee y)\wedge(x\vee z),\qquad x\wedge(y\vee z)=(x\wedge y)\vee(x\wedge z),
则称为分配格。
带索引的多重集 / 列表：为处理重复值，习惯把一个族写成带索引的序列 S=(x_1,\dots,x_n)。在下面的定义与证明中，我们总以“索引集合” \{1,\dots,n\} 作为子集的取法基础（而不是把 S 看作无标号的集合），以保证对重复元素的正确计数。
记号约定：对索引集 T\subseteq\{1,\dots,n\} 使用
\bigwedge_{i\in T} x_i,\qquad \bigvee_{i\in T} x_i
分别表示取这些索引对应元素的 meet 与 join（若 T=\varnothing 的情形按需要单独约定）。

2. 分配格与 valuation（赋值）

定义（valuation / 赋值）
令 L 为格，A 为可加阿贝尔群（例如 \mathbb{R} 或 \mathbb{Z}）。映射

v:L\longrightarrow A

称为 valuation（赋值），当且仅当对任意 x,y\in L 有恒等

\boxed{\; v(x)+v(y)=v(x\vee y)+v(x\wedge y). \;}\tag{V}

备注：在幂集格上，基数函数 A\mapsto |A| 或任意有限可加测度都是典型的 valuation；在整除格上，把乘法取对数（v(n)=\log n）也把乘法型关系变为加性，从而满足 (V)。

基本性质（直观）

valuation 把格的并—交结构变成线性等式，使得包含—排除类型的线性组合在代数上成立。
在分配格上，valuation 的二元恒等 (V) 可以被逐步推广到任意有限族上的包含—排除恒等（见下节与第 5 节的推广定理）。

3. 在链（totally ordered set）上的第 k 大：定义与等价刻画

链上的常规定义（数值情形）
设 S=(x_1,\dots,x_n) 为一列实数（允许重复），按非增序排列为

y_{(1)}\ge y_{(2)}\ge\cdots\ge y_{(n)}.

则称 y_{(k)} 为 S 的 第 k 大（亦称第 k 阶统计量，the k-th order statistic）。等价地，y_{(k)} 是“最大的 k 个数中的最小值”。

格上的自然推广（带索引形式）
对于任意格 L 与带索引的序列 S=(x_1,\dots,x_n)\subseteq L，定义

\boxed{\; \operatorname{max}_k(S) \;:=\; \bigvee_{\substack{T\subseteq\{1,\dots,n\}\\|T|=k}} \bigwedge_{i\in T} x_i. \;} \tag{D}

即先对每个恰好 k 个元素取它们的 meet（即这些 k 个中的最小），再对所有这些结果取 join（即取这些“k-最小”中的最大者）——正是“最大的 k 个中的最小”的格论翻译。

在链（totally ordered set）上 (D) 与常规定义一致。

4. 主定理（链 / 数值形式）与证明

4.1 关键组合恒等（引理）

Lemma（组合恒等）
对于任意整数 \ell\ge k\ge1 有

\boxed{\; \sum_{i=k}^{\ell} (-1)^{\,i-k}\binom{i-1}{k-1}\binom{\ell-1}{i-1} = \begin{cases} 1,&\ell=k,\\[3pt] 0,&\ell>k. \end{cases} \;}\tag{L}

证明
使用组合数恒等

\binom{i-1}{k-1}\binom{\ell-1}{i-1}=\binom{\ell-1}{k-1}\binom{\ell-k}{i-k}.

于是左式化为

\binom{\ell-1}{k-1}\sum_{j=0}^{\ell-k}(-1)^j\binom{\ell-k}{j} =\binom{\ell-1}{k-1}(1-1)^{\ell-k},

当 \ell=k 时为 1，当 \ell>k 时为 0。证毕。 \square

4.2 主定理（链 / 数值情形）

Theorem（第 k 大的包含—排除式）
设 S=(x_1,\dots,x_n) 为一列实数（允许相等）。则对任意 1\le k\le n 有

\boxed{\; \operatorname{max}_k(S) =\sum_{\substack{T\subseteq\{1,\dots,n\}\\|T|\ge k}} (-1)^{|T|-k}\binom{|T|-1}{k-1}\;\min_{i\in T} x_i. \;}

证明（按“贡献”计数）
将 S 按非增序排列为 y_{(1)}\ge y_{(2)}\ge\cdots\ge y_{(n)}。我们把右端按“哪个位置的元素作为 \min(T)”分组，并计算每个 y_{(\ell)} 的总系数。

若 \min(T)=y_{(\ell)}，则 T 必须包含某个对应位置为 \ell 的索引，並且其余 |T|-1 个元素必须从更大的位置 \{1,\dots,\ell-1\} 中选出。因此，对固定大小 i=|T| 而言，出现的子集数为 \binom{\ell-1}{i-1}。所以 y_{(\ell)} 在右端的总系数为

\sum_{i=k}^{\ell}(-1)^{\,i-k}\binom{i-1}{k-1}\binom{\ell-1}{i-1}.

由引理 (L)，此和当且仅当 \ell=k 时为 1，其余情况为 0。因此右端只留下 y_{(k)} 的贡献 1，即等于 \operatorname{max}_k(S)。证毕。 \square

5. 推广：分配格上的 valuation 版本

下面对 valuation 版本给出更详尽的、形式化的证明要点 —— 包括按 meet 值分组、用组合恒等归简、以及在偏序上的 Möbius 反演步骤。

5.1 形式化定理

Theorem（分配格 + valuation 版本）
令 L 为分配格，S=(x_1,\dots,x_n)\subseteq L 为带索引的元素列。令 v:L\to A 为到可加阿贝尔群 A 的 valuation，即满足对任意 u,w\in L：

v(u)+v(w)=v(u\vee w)+v(u\wedge w).

则对任意 1\le k\le n 在 A 中成立

\boxed{\; v\big(\operatorname{max}_k(S)\big) =\sum_{\substack{T\subseteq\{1,\dots,n\}\\|T|\ge k}} (-1)^{|T|-k}\binom{|T|-1}{k-1}\; v\Big(\bigwedge_{i\in T} x_i\Big). \;}\tag{★}

5.2 证明（详尽步骤）

（A）按 meet 值分组，将指数维度降维

定义映射 \varphi:\mathcal P(\{1,\dots,n\})\setminus\{\varnothing\}\to L：

\varphi(T):=\bigwedge_{i\in T} x_i.

记 \operatorname{Im}\varphi 为映像。对任意 y\in\operatorname{Im}\varphi 定义

\mathcal T_y:=\{\,T\subseteq\{1,\dots,n\}:\ T\neq\varnothing,\ \varphi(T)=y\,\}.

把 RHS（标记为 R）按 y 分组：

R=\sum_{T:|T|\ge k} (-1)^{|T|-k}\binom{|T|-1}{k-1}\; v(\varphi(T)) =\sum_{y\in\operatorname{Im}\varphi} c(y)\, v(y),

其中

c(y):=\sum_{T\in\mathcal T_y} (-1)^{|T|-k}\binom{|T|-1}{k-1}.

要证明 c(y)=1 当 y=\operatorname{max}_k(S)，否则 c(y)=0。

（B）把“\varphi(T)\succeq y” 的集合与 I_y 对应并应用组合恒等

定义

I_y:=\{\, i\in\{1,\dots,n\} : x_i \succeq y \,\}.

注意：若 T\subseteq I_y（非空），则 \varphi(T)=\bigwedge_{i\in T}x_i\succeq y；反之若 \varphi(T)\succeq y 则 T\subseteq I_y. 因此集合 \{T:\varphi(T)\succeq y\} 恰为非空子集集合 \mathcal P(I_y)\setminus\{\varnothing\}。

考虑累积和

S(y):=\sum_{\substack{T\neq\varnothing\\ \varphi(T)\succeq y}} (-1)^{|T|-k}\binom{|T|-1}{k-1}.

按大小分组并用组合恒等化简得

S(y)=\sum_{t=k}^{|I_y|}(-1)^{t-k}\binom{t-1}{k-1}\binom{|I_y|}{t}.

按引理 (L) 的组合代数推理可化简为

S(y)= \begin{cases} 1,& |I_y|\ge k,\\[4pt] 0,& |I_y|<k. \end{cases} \tag{1}

（C）Möbius 反演：从累积和到点系数

另一方面，把累积和按照 \varphi 的像值展开：

S(y)=\sum_{\substack{T\neq\varnothing\\ \varphi(T)\succeq y}} (-1)^{|T|-k}\binom{|T|-1}{k-1} = \sum_{z\succeq y} \sum_{T\in\mathcal T_z} (-1)^{|T|-k}\binom{|T|-1}{k-1} = \sum_{z\succeq y} c(z).

即对任意 y\in\operatorname{Im}\varphi 有

\sum_{z\succeq y} c(z) = S(y). \tag{2}

方程 (2) 是偏序 \operatorname{Im}\varphi 上的累和关系。由偏序上的 Möbius 反演（有限偏序上若 F(y)=\sum_{z\succeq y} f(z)，则 f(y)=\sum_{z\succeq y}\mu(y,z)F(z)，其中 \mu 为该偏序的 Möbius 函数）可得

c(y)=\sum_{z\succeq y} \mu(y,z)\, S(z). \tag{3}

把 (1) 带入 (3) 得

c(y)=\sum_{\substack{z\succeq y\\ |I_z|\ge k}} \mu(y,z). \tag{4}

（D）识别 c(y)：U_k 的最小元就是 \operatorname{max}_k(S)

令

U_k:=\{\, z\in\operatorname{Im}\varphi : |I_z|\ge k\,\}.

注意 U_k 是一个上集（up-set）：若 z\in U_k 且 z'\succeq z，则 z'\in U_k。

定义

y_*:=\bigvee_{\substack{T\subseteq\{1,\dots,n\}\\|T|=k}} \bigwedge_{i\in T} x_i = \operatorname{max}_k(S).

可以证明 y_* 是 U_k 的最小元（即 y_*\in U_k，且对任一 z\in U_k 有 y_*\preccurlyeq z）。因此集合 \{ z\succeq y :\, |I_z|\ge k\} 要麼是空的（当 y\not\preccurlyeq y_* 时），要麼等于集合 \{ z\succeq y_* \}（当 y\preccurlyeq y_* 时）。

因此由 (4) 可得：

若 y\not\preccurlyeq y_* 则 c(y)=0；
若 y\preccurlyeq y_* 则 c(y)=\sum_{z\succeq y,\, z\succeq y_*} \mu(y,z) =\sum_{z\succeq y_*} \mu(y,z).
利用 Möbius 的基本性质（對固定 y，\sum_{z\succeq w}\mu(y,z)=\delta_{y,w}）可以推出
c(y)= \begin{cases} 1,& y=y_*,\\[3pt] 0,& y\prec y_*. \end{cases}

综上，c(y)=1 当且仅当 y=\operatorname{max}_k(S)，其余为 0。

（E）代回并完成证明

把 c(y) 代回分组表达式

R=\sum_{y\in\operatorname{Im}\varphi} c(y)\, v(y)

得到

R=v(\operatorname{max}_k(S)).

这正是等式 (★)。证毕。 \square

5.3 讨论与补充说明

分配性：在上述证明中，分配性用来确保将索引子集按 meet 值分组时，meet 与 join 的组合行为不会产生额外的“交错”导致计数失效；即在展开多元 join/meet 时项能够按期望方式合并与抵消。若格非分配，则需要用更复杂的偏序 Möbius 函数对系数进行修正，原二项式系数一般不成立。
valuation 的作用：(V) 保证把格元素替换为数值后线性关系保持，从而将格上的组合恒等推广为数值恒等；若没有 (V)，即使格上的指示系数 c(y) 正确，代上的数值和也不一定成立。
Möbius 理论接口：证明中的关键转换 (2) ↔ (3) 实际上是偏序上标准的 ζ-μ（Zeta–Möbius）反演：在有限偏序 (P,\preccurlyeq) 上定义 ζ 函数 ζ(x,y)=[x\preccurlyeq y]，其逆为 Möbius 函数 μ(x,y)，满足矩阵反演关系。我们在 (2)-(3) 中正是应用了该反演。

6. OI 中的应用

咕咕咕