Нерівність перестановок

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Нехай

дійсні числа
перестановка чисел .

Тоді справедливою є нерівність:

Доведення[ред.ред. код]

Друга нерівність випливає з першої, якщо її застосувати до послідовності

Тому достатньо довести лише першу нерівність. Оскільки кількість перестановок є скінченною, принаймні для одної значення суми

є максимальним. Якщо таких перестановок є кілька нехай σ — та з них, що залишає незмінними найбільшу кількість чисел.

Доведемо, що σ — одинична перестановка. Припустимо, що це не так. Тоді існує число j ∈ {1, ..., n − 1}, таке що σ(j) ≠ j і σ(i) = i для всіх i ∈ {1, ..., j − 1}. Тому σ(j) > j і існує k ∈ {j + 1, ..., n} для якого σ(k) = j. Оскільки

Тому,

Розписуючи добуток отримуємо:

тому перестановка

що утворюється з σ заміною значень σ(j) і σ(k), має принаймні одну додаткову фіксовану точку j, і також є максимальною. Це суперечить вибору σ.

Якщо

то нерівності (1), (2), і (3) є строгими, тому максимум може бути досягнутим лише в одиничній перестановці.

Див. також[ред.ред. код]

Посилання[ред.ред. код]