「Learning Notes」Maximum-Minimums Identity

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Maximum-Minimums Identity

Identity

对于全序集合 S ,有:

\max{S}=\sum_{T\subseteq S}(-1)^{|T|-1}\min{T}

\min{S}=\sum_{T\subseteq S}(-1)^{|T|-1}\max{T}

Proof

此处只证明 \max \min 的转化, \min \max 的转化证明类似.

f(k) 满足:

\max{S}=\sum_{T\subseteq S}f\left(|T|\right)\min{T}

考虑集合 S 中第 k 大的元素被计算的次数,有:

\left[k=1\right]=\sum_{i=0}^{k-1}\binom{k-1}{i}f\left(i+1\right)

二项式反演可得:

f(k)=\sum_{i=0}^{k-1}(-1)^{k-1-i}\binom{k-1}{i}\left[i+1=1\right]=(-1)^{k-1}

故:

\max{S}=\sum_{T\subseteq S}f\left(|T|\right)\min{T}=\sum_{T\subseteq S}(-1)^{|T|-1}\min{T}

Extension

考虑证明过程,可以发现其容易推广为如下形式:

f(k) 满足:

\operatorname{n-thmax}{S}=\sum_{T\subseteq S}f\left(|T|\right)\min{T}

考虑集合 S 中第 k 大的元素被计算的次数,有:

\left[k=n\right]=\sum_{i=0}^{k-1}\binom{k-1}{i}f\left(i+1\right)

二项式反演可得:

f(k)=\sum_{i=0}^{k-1}(-1)^{k-1-i}\binom{k-1}{i}\left[i+1=n\right]=(-1)^{k-n}\binom{k-1}{n-1}

故:

\operatorname{n-thmax}{S}=\sum_{T\subseteq S}f\left(|T|\right)\min{T}=\sum_{T\subseteq S}(-1)^{|T|-n}\binom{|T|-1}{n-1}\min{T}

同理有

\operatorname{n-thmin}{S}=\sum_{T\subseteq S}(-1)^{|T|-n}\binom{|T|-1}{n-1}\max{T}

Examples

「Luogu P4707」重返现世