Maximum-minimums identity

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 2n − 1 nonempty subsets of S.

Let S = {x1, x2, ..., xn}. The identity states that

\begin{align}
\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{align}

or conversely

\begin{align}
\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{align}

For a probabilistic proof, see the reference.

See also[edit]

References[edit]

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