当前位置：首页 > news >正文

扩展 Min-Max 容斥

news 2025/9/17 22:35:22

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) 中正是应用了该反演。