Четность подстановки

Определение 6. Пусть — разложение подстановки в произведение транспозиций. Тогда число называется знаком ⁷⁾(четностью) подстановки . Подстановка называется четной ⁸⁾, если и нечетной ⁹⁾ в противном случае.

Предложение 3. Четность подстановки не зависит от способа разложения подстановки в произведение транспозиций.

Предложение 4. Для двух подстановок и четность их произведения равна произведению четностей:

Доказательство.

Пусть , , значит, и . Тогда — разложение подстановки в произведение транспозиций. Поэтому

.

Предложение 5. Пусть — цикл длины . Тогда его четность равна .

Доказательство.

Утверждение следует из того, что цикл длины представим в виде произведения -й транспозиции

Утверждение следует из того, что цикл длины представим в виде произведения -й транспозиции

.

Определение 7. Пусть — разложение подстановки в произведение независимых циклов длин . Число называется декрементом ¹⁰⁾ подстановки .

Предложение 6. Пусть — разложение подстановки в произведение независимых циклов длин . Тогда четность подстановки вычисляется по формуле

.

По предложению 5 для . По предложению 4

.

Пример 6. Любая транспозиция — это нечетная подстановка. Подстановка из примера 4 нечетная, так как декремент — нечетное число.

Пример 7. Любая подстановка, в разложении которой на независимые циклы все циклы имеют нечетные длины , четна, так как ее декремент — это сумма четных чисел .