Введение
В математике, неравенство о перестановках гласит, что для любого выбора вещественных чисел
и любой перестановки чисел , выполняется:
Неформально, это означает, что в подобных суммах наибольшая сумма достигается при сопоставлении больших значений с большими значениями, а наименьшая – при сопоставлении малых значений с большими значениями. Это можно формализовать в случае, когда различны, то есть:
Верхняя граница в достигается только для перестановок , сохраняющих порядок , то есть , или, эквивалентно, . Такая может переставлять индексы равных значений; в случае , когда , любая перестановка сохраняет порядок . Если , то единственная такая – это тождественная перестановка. Соответственно, нижняя граница в достигается только для перестановок , обращающих порядок , то есть . Если , то для всех единственной перестановкой, обеспечивающей это, является . Следует отметить, что неравенство о перестановках не делает никаких предположений о знаках вещественных чисел, в отличие от неравенств, таких как неравенство между средним арифметическим и средним геометрическим.
then:
The upper bound in is attained only for permutations that keep the order of that is, or equivalently Such a can permute the indices of values that are equal; in the case every permutation keeps the order of If then the only such is the identiy. Correspondingly, the lower bound in is attained only for permutations that reverse the order of meaning that If then for all is the only permutation to do this. Note that the rearrangement inequality makes no assumptions on the signs of the real numbers, unlike inequalities such as the arithmetic geometric mean inequality.
Интуиция
Неравенство перестановки можно интуитивно понять следующим образом. Представьте, что есть стопка купюр по 10 долларов, стопка купюр по 20 долларов и еще одна стопка купюр по 100 долларов. Вам разрешено взять 7 купюр из любой стопки, после чего эта стопка исчезает. Во втором раунде вам разрешается взять 5 купюр из другой стопки, и она тоже исчезает. В последнем раунде вы можете взять 3 купюры из оставшейся стопки. В каком порядке следует выбирать стопки, чтобы максимизировать свою прибыль? Очевидно, что наибольшую прибыль можно получить долларов. Именно это утверждает верхняя граница неравенства перестановки для последовательностей и . В этом смысле, его можно рассматривать как пример жадного алгоритма.
Геометрическая интерпретация
Предположим, что и . Рассмотрим прямоугольник шириной и высотой, разделенный на столбцов ширины и такое же количество строк высоты, так что получается маленьких прямоугольников. Вам нужно выбрать из них прямоугольники, взяв по одному из каждого столбца и по одному из каждой строки. Неравенство о перестановках утверждает, что общую площадь выбранных прямоугольников можно оптимизировать, выбирая прямоугольники, расположенные на главной или побочной диагонали.