Relation between inclusion-exclusion principle and maximum-minimums identity
Inclusion-exclusion principle states that the size of the union of $n$ finite sets is given by the sum of the sizes of all sets minus sum of the sizes of all the pairwise intersections plus sum of the sizes of all the triple intersections and so on: $$ \left| A_1\cup \dots \cup A_n\right| = \sum_i \left| A_i\right|-\sum_{i<j} \left| A_i\cap A_j\right|+\sum_{i<j<k} \left| A_i\cap A_j\cap A_k\right|-\dots+(-1)^{n+1}\left| A_1\cap \dots \cap A_n\right|. $$ Maximum-minimums identity states that the maximum of a finite set of numbers $S = \{x_1, \dots, x_n \}$ is given by the sum of all elements minus the sum of minimums of all pairs of elements plus sum of minimums of all triples and so on: $$ \max\{x_1, \dots,x_n\} = \sum_i x_i -\sum_{i<j}\min\{x_i, x_j\} + \sum_{i<j<k}\min\{x_i, x_j,x_k\}-\dots+(-1)^{n+1}\min\{x_1,\dots, x_n\}. $$ It is hard to miss the similarity.
- Is there a relation between maximum-minimums identity and inclusion-exclusion principle?
- Can either one be proven from the other?
Inspired by kimchi lover's proof:
Let us first assume $x_1,\dots,x_n$ are positive integers. Then we can construct sets $A_i = \{1, \dots, x_i\}$ for all $i$s. Now $|A_i|=x_i$, therefore, $|A_1\cup\dots\cup A_n|=\max\{x_1,\dots,x_n\}$, $|A_i\cap A_j|=\min\{x_i,x_j\}$, and so on.
We can extend this proof to the case where $x_i$s can be negative by shifting all the elements, finding the maximum and then shifting back.
Similarly, we can extend to rationals by multiplying everything by the common denominator.
Finally, we can extend to reals by continuity.
Without loss of generality, reindex the elements so that $i\lt j\implies x_i\le x_j$. Let $U_k$ be the set of $k$-tuples from $\{x_j:1\le j\le n\}$ $$ U_k=\{(x_{j_1},x_{j_2},\dots,x_{j_k}):1\le j_1\lt j_2\lt\dots\lt j_k\le n\} $$ Note that $|U_k|=\binom{n}{k}$.
$x_j$ is the minimum in $\binom{n-j}{k-1}$ elements of $U_k$. Therefore, $$ \sum_{u\in U_k}\min u=\sum_{j=1}^n x_j\binom{n-j}{k-1} $$ and so $$ \begin{align} \sum_{k=1}^n(-1)^{k-1}\sum_{u\in U_k}\min u &=\sum_{k=1}^n(-1)^{k-1}\sum_{j=1}^nx_j\binom{n-j}{k-1}\\ &=\sum_{j=1}^nx_j\sum_{k=1}^n(-1)^{k-1}\binom{n-j}{k-1}\\ &=\sum_{j=1}^nx_j\,[j=n]\\[9pt] &=x_n \end{align} $$ Compare this to this proof of the Inclusion-Exclusion Principle.