Maximum-minimums identity

Short description: Relates the maximum element of a set of numbers and the minima of its non-empty subsets

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}{rl}\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}{rl}\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
• Maxima and minima § In relation to sets

References

• Ross, Sheldon (2002). A First Course in Probability. Englewood Cliffs: Prentice Hall. ISBN 0-13-033851-6. https://archive.org/details/firstcourseinpro00ross.