排序不等式与切比雪夫不等式

当两列数都已排序，较大数配较大数会增加乘积和，这是排序方法的基本局部操作。

排序不等式为何适用

研究 $\sum a_ic_i$ 时，若 $c_1,\ldots,c_n$ 只是同一组数的不同排列，就可以在所有配对之间比较。局部交换的依据是：对 $a\le b,c\le d$ ，

ac+bd-ad-bc=(b-a)(d-c)\ge0.

因此把较大的系数配给较大的数，会使乘积和不减。所有数都可以为负，判断依据是两组数各自的顺序。

下面先给出完整的双侧结论和等号条件，再说明另一种利用部分和的证明。完全对称的原问题可以先将变量排序；仅有循环对称时，任意换位可能改变原式，必须先确认允许的换位。

排序不等式与切比雪夫不等式的双侧形式

设 $a_1\le\cdots\le a_n$ 、 $b_1\le\cdots\le b_n$ ，均为实数， $\sigma$ 为任意排列。则

\sum_{i=1}^n a_i b_{n+1-i}\le\sum_{i=1}^n a_i b_{\sigma(i)}\le\sum_{i=1}^n a_ib_i.

不要求各数为正。证明的基本交换是：当 $i<j$ 且 $b_{\sigma(i)}>b_{\sigma(j)}$ 时，将这两项交换后，和增加

(a_j-a_i)(b_{\sigma(i)}-b_{\sigma(j)})\ge0.

逐次消除逆序得到上界；按相反方向交换得到下界。上界取等的精确条件是 $a_i<a_j$ 时必有 $b_{\sigma(i)}\le b_{\sigma(j)}$ ；下界对应 $b_{\sigma(i)}\ge b_{\sigma(j)}$ 。两列均严格递增时，只有完全同序或完全反序分别取等；有重复值时允许在相等项间交换。

切比雪夫双侧式：

n\sum a_i b_{n+1-i}\le(\sum a_i)(\sum b_i)\le n\sum a_ib_i.

右侧可由恒等式

n\sum a_ib_i-(\sum a_i)(\sum b_i) =\sum_{i<j}(a_j-a_i)(b_j-b_i)\ge0

直接证明；将 $b$ 反序，各项差异号，得到左侧。若 $n\ge2$ ，任意一侧取等当且仅当至少一列为常数列：两列若都不恒定，则首末项差均非零，右侧和至少有一项为正；反序同理。 $n=1$ 时恒为等式。

用部分和证明排序不等式

仍设 $a_1\le\cdots\le a_n$ ， $b_1\le\cdots\le b_n$ ， $c_1,\ldots,c_n$ 是 $b$ 的任意排列。令

D_k=\sum_{i=1}^k(b_i-c_i).

因为 $b_1,\ldots,b_k$ 是整组数中最小的 $k$ 个， $D_k\le0$ ，并且 $D_n=0$ 。写 $b_i-c_i=D_i-D_{i-1}$ 、 $D_0=0$ ，展开并错位合并，得到有限求和恒等式

\begin{aligned} \sum_{i=1}^na_i(b_i-c_i) &=a_nD_n+\sum_{k=1}^{n-1}(a_k-a_{k+1})D_k\\ &=\sum_{k=1}^{n-1}(a_k-a_{k+1})D_k\ge0. \end{aligned}

这证明任意排列和不超过同序和。

类似地，前 $k$ 个反序项 $b_n,\ldots,b_{n+1-k}$ 是最大的 $k$ 个，故将 $D_k$ 改为 $\sum_{i=1}^k(b_{n+1-i}-c_i)\ge0$ ，同一恒等式给出反序和不大于任意排列和。这种整理称为有限阿贝尔变换，适合已掌握部分和大小关系的情形。

排序等号与切比雪夫等号要分别检查

若两列都已递增，同序配对本身就使排序不等式的上界取等号，无须某列为常数。例如 $(1,2)$ 与 $(3,4)$ 同序配对得 $11$ ，已经是最大乘积和，而两列都非常数。

若两列都严格递增，同序最大值只在同序配对时取得，反序最小值只在反序配对时取得；有相同元素时，交换这些元素不会改变和。一般情形可沿交换证明逐步检查：每次被交换的一对，只有差的乘积为零才不改变值。

切比雪夫不等式比较的是同序乘积和与均值乘积，等号条件是另一个问题，应使用上一节的差积恒等式。

例

正数 $a,b,c$ 与倒数 $1/a,1/b,1/c$ 反序，因此

3\le\frac{(a+b+c)(1/a+1/b+1/c)}3.

从而乘积至少为 $9$ ，等号在三数相等时取得。这与分式柯西所得结论一致，但组织信息的方式不同。

关联阅读

先修：不等式的性质与解法。

同主题：柯西不等式与分式形式 · 凸性与有限加权不等式。