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

Парність перестановки скінченної множини — це парність кількості інверсії цієї множини.

Перестановка 4 елементів

Непарні — зелені та оранжеві. Числа справа — кількість інверсій.

Множина перестановок розбивається на рівні підмножини: парних і непарних перестановок.

Транспозиції та інверсії

Відомо, що довільну перестановку можна утворити через послідовність транспозицій(обмінів) пар елементів.

І парність кількості транспозицій буде дорівнювати парності інверсій.

Доведення

1. Транспозиція двох сусідніх елементів змінює кількість інверсій на $\pm 1.$
2. Транспозиція двох довільних елементів зводиться до непарного числа транспозицій сусідніх елементів.
3. Транспозиція — змінює кількість інверсій на непарне число.
4. Оскільки тотожна перестановка має 0 транспозицій та 0 інверсій, то парність кількості транспозицій дорівнює парності кількості інверсій.

Підгрупа парних перестановок

• Тотожне перетворення є парною перестановкою.
• Добуток парних перестановок є парною перестановкою.
• Обернена перестановка до парної перестановки є парною.

Отже парні перестановки утворюють групу (називається знакозмінною групою), що є підгрупою симетричної групи (групи всіх перестановок множини).

Джерела

• Курош А. Г. Теория групп. — 3-е изд. — Москва : Наука, 1967. — 648 с. — ISBN 5-8114-0616-9.(рос.)
• Джозеф Ротман. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — ISBN 978-0387942858.(англ.)