Maximum-minimums identity

Template:Short description In mathematics, the maximum-minimums identity is a relation between the maximum element of a set S of n numbers and the minima of the 2ⁿ − 1 non-empty subsets of S.

Let S = {x₁, x₂, ..., x_n}. The identity states that

$\begin{array}{cc}\max \{x_1,x_2,\dots ,x_n\}& =\sum _{i=1}^n{x}_i-\sum _{i<j}\min \{x_i,x_j\}+\sum _{i<j<k}\min \{x_i,x_j,x_k\}-\cdots \\ & \cdots +{(-1)}^{n+1}\min \{x_1,x_2,\dots ,x_n\},\end{array}$

or conversely

$\begin{array}{cc}\min \{x_1,x_2,\dots ,x_n\}& =\sum _{i=1}^n{x}_i-\sum _{i<j}\max \{x_i,x_j\}+\sum _{i<j<k}\max \{x_i,x_j,x_k\}-\cdots \\ & \cdots +{(-1)}^{n+1}\max \{x_1,x_2,\dots ,x_n\}.\end{array}$

For a probabilistic proof, see the reference.

See also

• Inclusion–exclusion principle
• Template:Section link

References

• Template:Cite book