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

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

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

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

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

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

ред.

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

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

Доведення

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

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

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

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

Джерела

ред.