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

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

Нехай дана підстановка безлічі

Розглянемо якусь неупорядковану пару різних елементів безлічі М. Пара назьшается правильної по відношенню до підстановці якщо різниці мають один і той же знак. Кажуть, що пара неправильна по відношенню до підстановці або утворює в ній інверсію, якщо різниці мають різні знаки. Так, наприклад, в тотожною підстановці g! немає інверсії. У підстановці є тільки одна інверсія. У підстановці є дві інверсії.

Підстановка називається парної, якщо вона містить парне число інверсій; підстановка називається непарної, якщо вона містить непарне число інверсій. Так, наприклад, тотожна підстановка є парна.

називається транспозицією. Іншими словами, підстановка називається транспозицією, якщо існує пара різних елементів з М, які відповідають умовам для кожного

ЛЕММА 3.2. Будь-яка транспозиція є непарна підстановка.

Доведення. Нехай - транспозиція, яка переводить i в т. Е. Що задовольняє умовам (1). Будемо припускати, що Легко бачити, що пара а М може утворити інверсію, якщо хоча б один з її елементів є i чи інакше обидві різниці збігаються.

Якщо чи то серед пар немає інверсій, так як обидві різниці негативні.

Якщо то серед пар інверсіями є наступні:, всього інверсій.

Якщо, то серед пар інверсіями є пари є всього інверсій.

Отже, транспозиція містить всього інверсій, значить, є непарна підстановка.