Rearrangement inequality
In mathematics, the rearrangement inequality states that for every choice of real numbers x 1 ≤ ⋯ ≤ x n and y 1 ≤ ⋯ ≤ y n {\displaystyle x_{1}\leq \cdots \leq x_{n}\quad {\text{ and }}\quad y_{1}\leq \cdots \leq y_{n}} and every permutation σ {\displaystyle \sigma } of the numbers 1 , 2 , … n {\displaystyle 1,2,\ldots n} we have Informally, this means that in these types of sums, the largest sum is achieved by pairing large x {\displaystyle x} values with large y {\displaystyle y} values, and the smallest sum is achieved by pairing small values with large values. This can be formalised in the case that the x 1 , … , x n {\displaystyle x_{1},\ldots ,x_{n}} are distinct, meaning that x 1 < ⋯ < x n , {\displaystyle x_{1}<\cdots <x_{n},} then: The upper bound in (1) is attained only for permutations σ {\displaystyle \sigma } that keep the order of y 1 , … , y n , {\displaystyle y_{1},\ldots ,y_{n},} that is, y σ ( 1 ) ≤ ⋯ ≤ y σ ( n ) , {\displaystyle y_{\sigma (1)}\leq \cdots \leq y_{\sigma (n)},} or equivalently ( y 1 , … , y n ) = ( y σ ( 1 ) , … , y σ ( n ) ) .