Парність перестановки, ПріМат
Перестановка, що містить парну кількість інверсій, називається парною, інакше — непарною.
Лемма. Якщо в перестановці довжини більше, поміняти місцями елемента, то парність зміниться на протилежну.Доказ: Доведемо, що всяка транспозиція змінює парність перестановки. Для чисел, що стоять поряд, це твердження очевидне. Їхнє взаємне розташування щодо інших чисел залишилося незмінним, а перестановка самих чисел змінює загальну кількість інверсій на одиницю. Нехай тепер між числами, що переставляються, і знаходяться інших чисел, тобто перестановка має вигляд. Мінятимемо місцями число послідовно з рядом числами, що стоять. Потім число, що стоїть перед, перемістимо вліво за допомогою транспозицій з числами. Таким чином, всього ми виконаємо транспозицій поряд чисел, що стоять. Отже, парність перестановки зміниться. Лемма доведена.
Приклад парної перестановки Ця перестановка є парною, оскільки містить 2 інверсії, числа 3 і 2, 6 і 5 утворюють інверсії. Приклад непарної перестановки Ця перестановка є непарною, оскільки містить 3 інверсії, числа 2 і 1, 5 і 4, 7 і 6 утворюють інверсії.
Транспозиція змінює парність.Лемма. Всі -перестановок довжини можна розташувати одну за іншою таким чином, що кожна наступна виходить з попередньої однієї транспозиції. Причому можна розпочинати таке впорядкування з будь-якої перестановки.
Слідство. При число парних перестановок із символів дорівнює числу непарних, тобто. .
- Бєлозеров Г.С. Конспект лекцій з алгебри та геометрії
- Курош А.Г. Курс вищої алгебри 431 стор М.: Наука, 1968, Стор. 28-30
- Воєводін В.В. Лінійна алгебра 400 стор М.: Наука, 1980,Стор. 122-124