Maximum-minimums identity explained

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 = . The identity states that

\begin{align} max \{x _{1,x} _{2,\ldots,x} _{n} \} & = \sum ^{n} _{i =1} x _{i} - \sum _{i<j} min \{x _{i,x} _{j\}} + \sum _{i<j<k} min \{x _{i,x} _{j,x} _{k\}} - … \\ & … + \left( -1 \right) ^{n+1} min \{x _{1,x} _{2,\ldots,x} _{n\},\end{align}} or conversely\begin{align} min \{x _{1,x} _{2,\ldots,x} _{n} \} & = \sum ^{n} _{i =1} x _{i} - \sum _{i<j} max \{x _{i,x} _{j\}} + \sum _{i<j<k} max \{x _{i,x} _{j,x} _{k\}} - … \\ & … + \left( -1 \right) ^{n+1} max \{x _{1,x} _{2,\ldots,x} _{n\}. \end{align}}

For a probabilistic proof, see the reference.

See also

• Inclusion–exclusion principle

References

• Book: Ross, Sheldon . A First Course in Probability . Prentice Hall . Englewood Cliffs . 2002 . 0-13-033851-6 . registration .