bulgakov

07. Чётных и нечётных подстановок поровну

Среди всех n!n! подстановок ровно половина чётных и половина нечётных. Чтобы это увидеть, не нужно перебирать подстановки: достаточно одного обмена, который переводит каждую чётную подстановку в нечётную и обратно.

Один обмен меняет чётность

Возьмём n≥2n\ge2 и транспозицию [1 2][1\,2]. Умножим на неё подстановку π\pi слева. По свойству 26.3 в таблице π\pi меняются местами числа 11 и 22 верхней строки. Знак меняется:

s([1 2] π)=s([1 2]) s(π)=−s(π).s([1\,2]\,\pi)=s([1\,2])\,s(\pi)=-s(\pi).

Кроме того, разные подстановки остаются разными. Если [1 2]π1=[1 2]π2[1\,2]\pi_1=[1\,2]\pi_2, умножим обе части слева на [1 2][1\,2]. Так как [1 2][1 2]=ε[1\,2][1\,2]=\varepsilon, получим π1=π2\pi_1=\pi_2.

Утверждения 27.1 и 27.2. Если π1,…,πk\pi_1,\ldots,\pi_k — попарно различные нечётные подстановки, то [1 2]π1,…,[1 2]πk[1\,2]\pi_1,\ldots,[1\,2]\pi_k — попарно различные чётные. И наоборот: из различных чётных получаются различные нечётные.

Поровну

Из утверждения 27.1 следует, что нечётных подстановок не больше, чем чётных: каждой нечётной сопоставлена своя чётная. Из утверждения 27.2 — что чётных не больше, чем нечётных. Значит, их поровну.

Следствие 27.3. При n≥2n\ge2 чётных и нечётных подстановок по

n!2.\boxed{\frac{n!}{2}.}

Условие n≥2n\ge2 нужно: при n=1n=1 есть единственная подстановка ε\varepsilon, она чётна, а транспозиции [1 2][1\,2] не существует.

Пример, n=3n=3. Запишем нижние строки канонических таблиц. В каноническом виде умножение слева на [1 2][1\,2] просто меняет местами первые два числа нижней строки: под 11 встаёт π(2)\pi(2), под 22 — π(1)\pi(1).

Чётная π\pi Инверсий [1 2]π[1\,2]\pi Инверсий
(1,2,3)(1,2,3) 00 (2,1,3)(2,1,3) 11
(2,3,1)(2,3,1) 22 (3,2,1)(3,2,1) 33
(3,1,2)(3,1,2) 22 (1,3,2)(1,3,2) 11

Три чётные подстановки перешли в три разные нечётные: 3=3!/23=3!/2.

Множество чётных подстановок AnA_n

Множество всех чётных подстановок из SnS_n обозначают AnA_n. По следствию 27.3

∣An∣=n!2(n≥2).|A_n|=\frac{n!}{2}\qquad(n\ge2).

Утверждение 27.3. Внутри AnA_n можно умножать и брать обратные:

  1. если π1,π2∈An\pi_1,\pi_2\in A_n, то π1π2∈An\pi_1\pi_2\in A_n, потому что s(π1π2)=1⋅1=1s(\pi_1\pi_2)=1\cdot1=1;
  2. ε∈An\varepsilon\in A_n, потому что s(ε)=1s(\varepsilon)=1;
  3. если π∈An\pi\in A_n, то π−1∈An\pi^{-1}\in A_n, потому что s(π−1)=s(π)s(\pi^{-1})=s(\pi).

Для нечётных подстановок так не получится: произведение двух нечётных чётно, (−1)(−1)=+1(-1)(-1)=+1. Поэтому нечётные подстановки не образуют такого же замкнутого набора.

Проверь себя

  1. Сколько чётных подстановок при n=5n=5?
  2. Подстановка π=(12342143)\pi=\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix} чётна. Найди [1 2]π[1\,2]\pi и её знак.
  3. Пусть α\alpha и β\beta нечётны. Лежит ли αβ\alpha\beta в AnA_n?
Показать решение

1. 5!/2=120/2=605!/2=120/2=60.

2. Меняем первые два числа нижней строки: (2,1,4,3)→(1,2,4,3)(2,1,4,3)\to(1,2,4,3). Получаем [1 2]π=(12341243)[1\,2]\pi=\begin{pmatrix}1&2&3&4\\1&2&4&3\end{pmatrix} с одной инверсией (4,3)(4,3). Знак −1-1, как и должно быть.

3. Да: s(αβ)=(−1)(−1)=+1s(\alpha\beta)=(-1)(-1)=+1, значит, αβ\alpha\beta чётна и лежит в AnA_n.

ПрактикаЗагружаем тест…