Maximum-minimums identity

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 nonempty subsets of S.

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

{\begin{aligned}\max\{x_{1},x_{2},\ldots ,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 \\&\qquad \cdots +\left(-1\right)^{{n+1}}\min\{x_{1},x_{2},\ldots ,x_{n}\},\end{aligned}}

or conversely

{\begin{aligned}\min\{x_{1},x_{2},\ldots ,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 \\&\qquad \cdots +\left(-1\right)^{{n+1}}\max\{x_{1},x_{2},\ldots ,x_{n}\}.\end{aligned}}

For a probabilistic proof, see the reference.

References

Ross, Sheldon (2002). A First Course in Probability. Englewood Cliffs: Prentice Hall. ISBN 0-13-033851-6.

This article is issued from Wikipedia - version of the 7/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Maximum-minimums identity

See also

References