- Source: 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 2n − 1 non-empty subsets of S.
Let S = {x1, x2, ..., xn}. The identity states that
max
{
x
1
,
x
2
,
…
,
x
n
}
=
∑
i
=
1
n
x
i
−
∑
i
<
j
min
{
x
i
,
x
j
}
+
∑
i
<
j
<
k
min
{
x
i
,
x
j
,
x
k
}
−
⋯
⋯
+
(
−
1
)
n
+
1
min
{
x
1
,
x
2
,
…
,
x
n
}
,
{\displaystyle {\begin{aligned}\max\{x_{1},x_{2},\ldots ,x_{n}\}&=\sum _{i=1}^{n}x_{i}-\sum _{i
or conversely
min
{
x
1
,
x
2
,
…
,
x
n
}
=
∑
i
=
1
n
x
i
−
∑
i
<
j
max
{
x
i
,
x
j
}
+
∑
i
<
j
<
k
max
{
x
i
,
x
j
,
x
k
}
−
⋯
⋯
+
(
−
1
)
n
+
1
max
{
x
1
,
x
2
,
…
,
x
n
}
.
{\displaystyle {\begin{aligned}\min\{x_{1},x_{2},\ldots ,x_{n}\}&=\sum _{i=1}^{n}x_{i}-\sum _{i
For a probabilistic proof, see the reference.
See also
Inclusion–exclusion principle
Maxima and minima § In relation to sets
References
Ross, Sheldon (2002). A First Course in Probability. Englewood Cliffs: Prentice Hall. ISBN 0-13-033851-6.
Kata Kunci Pencarian:
- Maximum-minimums identity
- Maximum and minimum
- Minimum phase
- Matching (graph theory)
- Inclusion–exclusion principle
- List of probabilistic proofs of non-probabilistic theorems
- Arg max
- Identity element
- Principle of maximum entropy
- Maximum life span
