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