大家好，欢迎来到IT知识分享网。
注：
本文多有疏漏，敬请谅解。如有建议请在评论区留言，我会及时更正。谢谢。
本文希望提供较为严谨的排序不等式证明。有的地方作者能力不足或者说不清楚的，也许会不当地使用“显然”之类模糊不清的词，还请读者海涵。
排序不等式简介
排序不等式是数学上的一条不等式。它是说：如果 x 1 ≤ x 2 ≤ ⋯ ≤ x n x_1 \leq x_2 \leq \cdots \leq x_n x1≤x2≤⋯≤xn ，和 y 1 ≤ y 2 ≤ ⋯ ≤ y n y_1 \leq y_2 \leq \cdots \leq y_n y1≤y2≤⋯≤yn 是两组实数。而 x σ ( 1 ) , … , x σ ( n ) x_{\sigma(1)}, \ldots, x_{\sigma(n)} xσ(1),…,xσ(n) 是 x 1 , … , x n x_1, \ldots, x_n x1,…,xn 的一个排列。排序不等式指出 x 1 y 1 + ⋯ + x n y n ≥ x σ ( 1 ) y 1 + ⋯ + x σ ( n ) y n ≥ x n y 1 + ⋯ + x 1 y n x_1 y_1+\cdots+x_n y_n \geq x_{\sigma(1)} y_1+\cdots+x_{\sigma(n)} y_n \geq x_n y_1+\cdots+x_1 y_n x1y1+⋯+xnyn≥xσ(1)y1+⋯+xσ(n)yn≥xny1+⋯+x1yn 。 以文字可以说成是顺序和不小于乱序和，乱序和不小于逆序和。与很多不等式不同，排序不等式不需限定 x i , y i x_i, y_i xi,yi 的符号。
排序不等式证明
一般来说排序不等式有两种证明方法：数学归纳法和阿贝尔变换。这里只介绍数学归纳法证明，对阿贝尔变换感兴趣的同学可以参看这篇文章。
首先我们定义顺序和，乱序和和逆序和如下：
我们用 x i x_i xi 表示序列 X X X 的第 i i i 个元素，用 y i y_i yi 表示序列 Y Y Y 的第 i i i 个元素。我们假设 ∣ X ∣ = ∣ Y ∣ = n |X| = |Y| = n ∣X∣=∣Y∣=n 。保证 X X X 和 Y Y Y 满足如下条件：
∀ i ( 1 < i ≤ n ) → ( x i ≥ x i − 1 ∧ y i ≥ y i − 1 ) \forall_i (1<i \le n)\rightarrow(x_i \geq x_{i-1} \land y_i \geq y_{i-1}) ∀i(1<i≤n)→(xi≥xi−1∧yi≥yi−1)
顺序和 A \Alpha A 定义如下：
A = ∑ i = 1 n x i × y i A=\sum\limits_{i=1}^{n}x_i \times y_i A=i=1∑nxi×yi
乱序和 B \Beta B 定义如下：
我们定义序列 C C C 表示 Y Y Y 的一组全排列，即 C C C 中的每一个元素都在 Y Y Y 当中，且 Y Y Y 中的每一个元素都在 C C C 当中，且 ∣ Y ∣ = ∣ C ∣ |Y|=|C| ∣Y∣=∣C∣ 。
我们用 c i c_i ci 表示 C C C 的第 i i i 个元素。
B = ∑ i = 1 n x i × c i B=\sum\limits_{i=1}^n x_i \times c_i B=i=1∑nxi×ci
逆序和 Γ \Gamma Γ 定义如下：
Γ = ∑ i = 1 n x i × y n − i + 1 \Gamma = \sum \limits _{i=1} ^n x_i \times y_{n-i+1} Γ=i=1∑nxi×yn−i+1
我们首先证明 n = 1 n=1 n=1 时 A ≥ B ≥ Γ \Alpha \geq \Beta \geq \Gamma A≥B≥Γ ：
显然的是， Y Y Y 的全排列有且仅有一种，即 ( y 1 ) (y_1) (y1) ，那么乱序和只能是 x 1 × y 1 x_1 \times y_1 x1×y1 。我们也会发现，顺序和和逆序和同样都是 x 1 × y 1 x_1 \times y_1 x1×y1 。于是 A ≥ B ≥ Γ \Alpha \geq \Beta \geq \Gamma A≥B≥Γ 成立。
接下来我们证明假设 n = k ( k ≥ 1 ) n=k(k\geq 1) n=k(k≥1) 时 A ≥ B ≥ Γ \Alpha \geq \Beta \geq \Gamma A≥B≥Γ ，那么 n = k + 1 n=k+1 n=k+1 时 A ≥ B ≥ Γ \Alpha \geq \Beta \geq \Gamma A≥B≥Γ 。
当 c k + 1 = y k + 1 c_{k+1} = y_{k+1} ck+1=yk+1 时，假设存在一个排列 C C C 使得 B > A \Beta>\Alpha B>A ，那么我们可以推导出如下式子：
∑ i = 1 k x i × c i > ∑ i = 1 k x i × y i \sum\limits_{i=1}^k x_i \times c_i > \sum\limits_{i=1}^{k}x_i \times y_i i=1∑kxi×ci>i=1∑kxi×yi
与假设矛盾，故 A ≥ B \Alpha \geq \Beta A≥B。
同理，当 c k + 1 = y 1 c_{k+1} = y_1 ck+1=y1 时，假设存在一个排列 C C C 使得 B < Γ \Beta < \Gamma B<Γ，那么我们可以推导出如下的式子：
∑ i = 1 k x i × c i < ∑ i = 1 k x i × y ( k + 1 ) − i + 1 \sum\limits_{i=1}^k x_i \times c_i < \sum \limits _{i=1} ^k x_i \times y_{(k+1)-i+1} i=1∑kxi×ci<i=1∑kxi×y(k+1)−i+1
与假设矛盾，故 B ≥ Γ \Beta \geq \Gamma B≥Γ 。
当 c k + 1 ≠ y k + 1 c_{k+1} \ne y_{k+1} ck+1=yk+1 时，我们假设 c i = y k + 1 c_i = y_{k+1} ci=yk+1 。
于是我们可以得到，不论 C C C 怎样排列，只要 c k + 1 ≠ y k + 1 c_{k+1} \ne y_{k+1} ck+1=yk+1 ，都必然存在一种大于等于它的方案，也即 c k + 1 = y k + 1 c_{k+1} = y_{k+1} ck+1=yk+1 时的方案。
而当 c k + 1 = y k + 1 c_{k+1} = y_{k+1} ck+1=yk+1 时，最大的乘积之和就是 A \Alpha A 。
于是，我们证明了 A ≥ B \Alpha \geq \Beta A≥B。
接下来我们证明当 c k + 1 ≠ y 1 c_{k+1} \ne y_1 ck+1=y1 时，也有 B ≥ Γ \Beta \geq \Gamma B≥Γ 。
我们首先假设 c i = y 1 c_i = y_1 ci=y1 。
于是我们可以得到，不论 C C C 怎样排列，只要 c k + 1 ≠ y 1 c_{k+1}\ne y_1 ck+1=y1，都必然存在一种小于等于它的方案，也即 c k + 1 = y 1 c_{k+1} = y_{1} ck+1=y1 时的方案。
而当 c k + 1 = y 1 c_{k+1} = y_1 ck+1=y1 时，最小的乘积之和就是 Γ \Gamma Γ 。
于是，我们证明了 B ≥ Γ \Beta \ge \Gamma B≥Γ 。
到此，我们证明了对于所有的 n ∈ N + n \in N^+ n∈N+ 都有 A ≥ B ≥ Γ \Alpha \geq \Beta \geq \Gamma A≥B≥Γ 。
证明完毕。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/137542.html
