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

(Перенаправлено з Знак перестановки)

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

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

Транспозиції та інверсіїРедагувати

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

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

ДоведенняРедагувати

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

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

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

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

ДжерелаРедагувати