並べ替え不等式とは，$2n$ 個の実数 $x_1,x_2,\cdots,x_n,y_1,y_2,\cdots,y_n$ に対する次の不等式のことです．
並べ替え不等式： $x_1\ge x_2\ge \cdots \ge x_n，y_1\ge y_2 \ge \cdots \ge y_n$ とし，$y_1,y_2,\cdots,y_n$ を並べ替えたものを $y_{\sigma{(1)}},y_{\sigma{(2)}},\cdots,y_{\sigma{(n)}}$ とするとき，次の不等式が成り立つ．
\begin{array}{ccl} \large x_1y_1+x_2y_2+\cdots+x_ny_n &\large \ge& \large x_1y_{\sigma{(1)}}+x_2y_{\sigma{(2)}}+\cdots+x_ny_{\sigma{(n)}}\\ &\large \ge&\large x_1y_{n}+x_2y_{n-1}+\cdots+x_ny_{1} \end{array}
$2n$ 個の実数 $x_1,x_2,\cdots,x_n,y_1,y_2,\cdots,y_n$ は正でも負でも $0$ でも構いません．
並べ替え不等式の主張は二つです．まず，最初の不等号は，大きいもの同士の積の和は一番大きいということを言っています．また，二番目の不等号は，大きいものと小さいもの同士の積の和は一番小さいということを言っています.
例
たとえば，$x_1=100，x_2=10，x_3=1，y_1=200，y_2=20，y_3=2$ とすると，下の表から，並び替え不等式の主張が確かめられます．
\begin{array}{c|c} 100\cdot200+10\cdot20+1\cdot2& \color{red}{20202} \\ 100\cdot200+10\cdot2+1\cdot20& 20040 \\ 100\cdot20+10\cdot200+1\cdot2& 4002 \\ 100\cdot20+10\cdot2+1\cdot200& 2220 \\ 100\cdot2+10\cdot200+1\cdot20& 2220 \\ 100\cdot2+10\cdot20+1\cdot200& \color{blue}{600} \\ \end{array}
証明は， $(左辺)-(右辺) = \displaystyle \sum_{i=1}^n x_i(y_i-y_{\sigma{(i)}}) \ge 0$ であることを示せばよいです．
ここでは，つぎのアーベルの総和公式を用いて示します． $$ \sum_{i=1}^n a_ib_i=a_1(b_1-b_2)+(a_1+a_2)(b_2-b_3)+(a_1+a_2+a_3)(b_3-b_4)+\cdots$$ $$ +(a_1+a_2+\cdots+a_{n-1})(b_{n-1}-b_n)+(a_1+a_2+\cdots+a_n)b_n$$ 右辺は，隣り合う項でうまく打ち消されるように余分な項を足すことにより，差の形で表しています．
証明： 一番目の不等式を示します．アーベルの総和公式を用いると， \begin{array}{lll} \displaystyle \sum_{i=1}^n x_i(y_i-y_{\sigma{(i)}}) &=&\underbrace{(x_1-x_2)}_{\ge 0}\underbrace{(y_1-y_{\sigma{(1)}})}_{\ge 0}+\underbrace{(x_2-x_3)}_{\ge 0}\underbrace{(y_1+y_2-y_{\sigma{(1)}}-y_{\sigma{(2)}})}_{\ge 0}+\cdots\\ &&\displaystyle+\underbrace{(x_{n-1}-x_{n})}_{\ge 0}\underbrace{\left(\sum_{i=1}^{n-1}y_i-\sum_{i=1}^{n-1}y_{\sigma{(i)}}\right)}_{\ge 0}+x_n\underbrace{\left(\sum_{i=1}^n y_i-\sum_{i=1}^n y_{\sigma{(i)}}\right)}_{\ge 0} \end{array} より， $\displaystyle \sum_{i=1}^n x_i(y_i-y_{i-1}) \ge 0$． すなわち， $$\sum_{i=1}^n x_iy_i \ge \sum_{i=1}^n x_iy_{\sigma(i)}$$ となります．
二番目の不等式は， $$\sum_{i=1}^n x_i(y_{\sigma(i)}-y_{n-i+1})$$ にアーベルの総和公式を用いれば上と全く同様に示せます．
並べ替え不等式は，他のいろいろな不等式の証明に応用されます．
チェビシェフの不等式
次の定理はチェビシェフの不等式と呼ばれています．
チェビシェフの不等式： 実数 $a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_n$ について， $a_1 \ge a_2 \ge \cdots \ge a_n$，$b_1 \ge b_2 \ge \cdots \ge b_n$ ならば，次の不等式が成り立つ． $$\frac{1}{n}\sum_{k=1}^n a_kb_k \ge \left( \frac{1}{n}\sum _{k=1}^n a_k \right)\left( \frac{1}{n}\sum_{k=1}^n b_k\right)$$
この定理を並べ替え不等式を用いて証明してみましょう． 両辺を $n^2$ 倍すると， $$n\sum_{k=1}^n a_kb_k \ge \left( \sum _{k=1}^n a_k \right)\left( \sum_{k=1}^n b_k\right)$$ となるので，これを示せばいいですね．
並べ替え不等式を適用すると， \begin{array}{lrc} n\displaystyle \sum_{k=1}^n a_kb_k &\ge& (a_1b_1+a_2b_2+\cdots+a_nb_n)+ \\ && (a_1b_2+a_2b_3+\cdots+a_nb_{1})+ \\ && (a_1b_3+a_2b_4+\cdots+a_nb_{2})+ \\ &&\vdots \\ &&(a_1b_n+a_2b_1+\cdots+a_nb_{n-1}) \\ &=& \displaystyle \left( \sum _{k=1}^n a_k \right)\left( \sum_{k=1}^n b_k\right) \end{array}
他にも，数学的帰納法などにより証明することもできます．
相加相乗平均の不等式の証明に応用することもできます．例として，次の問題を並べ替え不等式を使って解いてみましょう．
問 $a,b,c$ を正の実数とする．次の不等式を示せ． $$a^3+b^3+c^3 \ge 3abc$$
示すべき式は $a,b,c$ について対称なので， $a \ge b \ge c \ge 0$ と仮定しても一般性を失いません．
並べ替え不等式から， $a^2\cdot \color{red}{\underline{\color{black}{a}}}+b^2\cdot \color{blue}{\underline{\color{black}{b}}}\ge a^2\cdot \color{blue}{\underline{\color{black}{b}}}+\color{red}{\underline{\color{black}{a}}}\cdot b^2$ すなわち， $$a^3+b^3\ge a^2b+ab^2 \cdots ①$$ また，$\color{red}{\underline{\color{black}{a}}}\cdot ab+\color{blue}{\underline{\color{black}{c}}}\cdot c^2 \ge ab\cdot \color{blue}{\underline{\color{black}{c}}}+\color{red}{\underline{\color{black}{a}}}\cdot c^2$ すなわち， $$a^2b+c^3 \ge abc+ac^2 \cdots ②$$ ①式と②式を辺々たすと， $$a^3+b^3+c^3 \ge abc+ab^2+ac^2$$ また，$ab^2+ac^2$ に再び並び替え不等式を用いると， $$ab^2+ac^2 =(ab)c+(ac)c \ge abc+abc\ge 2abc$$ よって， $$a^3+b^3+c^3 \ge 3abc$$ となります．
このように，並べ替え不等式を使って項を入れ替えていくことができます．
