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_1< x_2< \dots < 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<\lambda<\infty$ 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_1> x_2> \dots > 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 $\lambda\rightarrow\infty$.

References

• Zaskulnikov V. M., Statistical mechanics of fluids in a step potential: arXiv:1205.6546