Sorting identity

In mathematics, the sorting identity is a relation between the ordered set of a set S of n numbers and the minima of the 2ⁿ − 1 nonempty subsets of S.

Let S = {x₁, x₂, ..., x_n} and x₁ < x₂ < … < x_n.

The identity states that

$\sum_{l=1}^n \lambda^{l} x_l = \sum_{k=1}^n (1-\lambda)^{k-1} \lambda^{n-k+1} \sum_\mathrm{samp} \min ( x_{\alpha_1}, x_{\alpha_2}, \dots, x_{\alpha_k} )$

where 0 < λ < ∞ and the inner sum is over all possible samples of k elements of n, or conversely

$\sum_{l=1}^n \lambda^{l} x_l = \sum_{k=1}^n (1-\lambda)^{k-1} \lambda^{n-k+1} \sum_\mathrm{samp} \max ( x_{\alpha_1}, x_{\alpha_2}, \dots, x_{\alpha_k} )$

provided that x₁ > x₂ > … > x_n.

Sorting identity automatically arranges its left-hand side in ascending order of x_i for the given right-hand side.

Sorting identity generalizes the maximum-minimums identity reduces to it in the limit λ → ∞.