Maximum-minimums identity
From HandWiki
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 2n − 1 non-empty subsets of S.
Let S = {x1, x2, ..., xn}. The identity states that
- [math]\displaystyle{ \begin{align} \max\{x_1,x_2,\ldots,x_{n}\} & = \sum_{i=1}^n x_i - \sum_{i\lt j}\min\{x_i,x_j\} +\sum_{i\lt j\lt 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} }[/math]
or conversely
- [math]\displaystyle{ \begin{align} \min\{x_1,x_2,\ldots,x_{n}\} & = \sum_{i=1}^n x_i - \sum_{i\lt j}\max\{x_i,x_j\} +\sum_{i\lt j\lt 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} }[/math]
For a probabilistic proof, see the reference.
See also
References
- Ross, Sheldon (2002). A First Course in Probability. Englewood Cliffs: Prentice Hall. ISBN 0-13-033851-6. https://archive.org/details/firstcourseinpro00ross.
Original source: https://en.wikipedia.org/wiki/Maximum-minimums identity.
Read more |