Четные и нечетные подстановки.

Пусть дана подстановка множества

Рассмотрим какую-нибудь неупорядоченную пару различных элементов множества М. Пара назьшается правильной по отношению к подстановке если разности имеют один и тот же знак. Говорят, что пара неправильна по отношению к подстановке или образует в ней инверсию, если разности имеют разные знаки. Так, например, в тождественной подстановке g! нет инверсии. В подстановке есть только одна инверсия. В подстановке имеется две инверсии.

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

Подстановка вида

называется транспозицией. Другими словами, подстановка называется транспозицией, если существует пара различных элементов из М, удовлетворяющих условиям для каждого

ЛЕММА 3.2. Любая транспозиция есть нечетная подстановка.

Доказательство. Пусть — транспозиция, переводящая i в т. е. удовлетворяющая условиям (1). Будем предполагать, что Легко видеть, что пара а М может образовать инверсию, если хотя бы один из ее элементов есть i или в противном случае обе разности совпадают.

Если или то среди пар нет инверсий, так как обе разности отрицательны.

Если то среди пар инверсиями являются следующие: , всего инверсий.

Если , то среди пар инверсиями являются пары имеется всего инверсий.

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