排序不等式

Template:NoteTA Template:Unreferenced 排序不等式是數學上的一條不等式。它可以推導出很多有名的不等式，例如算術幾何平均不等式（簡稱算幾不等式），柯西不等式，和切比雪夫總和不等式。它是說：

如果 $x_1\le x_2\le \cdots \le x_n$，和 $y_1\le y_2\le \cdots \le y_n$ 是兩組實數。而 $x_{\sigma (1)},\dots ,x_{\sigma (n)}$ 是$x_1,\dots ,x_n$的一個排列。排序不等式指出 $x_1{y}_1+\cdots +x_n{y}_n\ge x_{\sigma (1)}{y}_1+\cdots +x_{\sigma (n)}{y}_n\ge x_n{y}_1+\cdots +x_1{y}_n$。

以文字可以說成是順序和不小於亂序和，亂序和不小於逆序和。與很多不等式不同，排序不等式不需限定$x_i,y_i$的正負。

證明

排序不等式可以用數學歸納法證明。關鍵在於下列結果：

若 $x_i\le x_j,y_i\le y_j$，則有 $(x_j-x_i)(y_j-y_i)\ge 0$

移項得出 $x_i{y}_i+x_j{y}_j\ge x_j{y}_i+x_i{y}_j$。

重複以上步骤便可得出排序不等式。

我们设 $S_i$ 为 $b_1,b_2,\dots b_n$ 原序列的前 $i$ 个数的和，即 $S_i=b_1+b_2+\dots b_i$。

设 $S^{\prime }$ 为打乱顺序后的序列，$S{\text{'}}_i$ 表示乱序后的前 $i$ 个数的和。所以有 $S_i\le S{\text{'}}_i$。

注意到 $a_n-a_{n+1}\le 0$，则 $S_i\times (a_n-a_{n+1})\ge S{\text{'}}_i\times (a_n-a_{n+1})$

$\sum _{k=1}^n{a}_k{b}_k=\sum _{k=1}^{n-1}{S}_k(a_k-a_{k+1})+S_n{a}_n\ge \sum _{k=1}^{n-1}S{\text{'}}_k(a_k-a_{k+1})+S{\text{'}}_n{a}_n(S{\text{'}}_n=S_n)$

得证。 Template:Math-stub