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
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/651e22344d44359142f243abb6d1a4eaebea8710)
or conversely
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f3b98a2327cc7b2d14bd37562cf041e30bc6c70)
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.