Перестановочное неравенство

Материал из Википедии — свободной энциклопедии

Перестановочное неравенство, или неравенство об одномонотонных последовательностях, или «транс-неравенство», утверждает, что скалярное произведение двух наборов чисел является максимальным возможным, если наборы одномонотонны (то есть оба одновременно неубывающие или одновременно невозврастающие), и минимально возможным, если наборы противоположной монотонности (то есть один неубывающий, другой невозврастающий).

Другими словами, если $x_1\leq x_2 \leq \dots\leq x_n$ и $y_1\leq y_2 \leq \dots\leq y_n$ , то для произвольной перестановки $σ$ чисел $\{1,2,\dots,n\}$ выполняется неравенство:

$x_1 y_n + x_2 y_{n-1} + \dots + x_n y_1 \leq x_1 y_{\sigma(1)} + x_2 y_{\sigma(2)} + \dots + x_n y_{\sigma(n)} \leq x_1 y_1 + x_2 y_2 + \dots + x_n y_n$

Следствием перестановочного неравенства является неравенство Чебышёва для сумм.

[править] Обобщенное перестановочное неравенство

Для наборов вещественных чисел $x_1\le\cdots\le x_n$ и $y_1\le\cdots\le y_n$ ,

$x_{\sigma (1)}y_1 + \cdots + x_{\sigma (n)}y_n \leq x_{\pi(1)}y_1 + \cdots + x_{\pi(n)}y_n$

если число инверсий в перестановке $π$ меньше чем в перестановке $σ$ .

Из обобщенного перестановочного неравенства легко следует классическое в виду того, что в тождественной перестановке $(1,2,\dots,n)$ число инверсий равно нулю, а в перестановке $(n,n-1,\dots,1)$ оно равно $\frac{n(n-1)}{2}$ и больше чем в любой другой перестановке порядка $n$ .