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

На первое место можно поставить любой из $n$ элементов, на второе — любой из оставшихся $n-1$, …, на последнее — единственный оставшийся. Всего $n(n-1)\cdots 1 = n!$ вариантов. $\blacksquare$

Соседние элементы. Пусть меняются местами $i_k$ и $i_{k+1}$. Для любой другой пары элементов их взаимный порядок не меняется, а значит, не меняется и то, образуют ли они инверсию. Пара $\{i_k, i_{k+1}\}$ инверсию либо приобретает, либо теряет. Значит, число инверсий меняется на $\pm 1$, и чётность меняется.

Общий случай. Пусть меняются местами элементы на местах $k < l$, и между ними стоит $s = l - k - 1$ элементов. Сдвинем $i_k$ вправо $s + 1$ элементарными транспозициями так, чтобы он встал сразу за $i_l$. Затем сдвинем $i_l$ влево на место $k$ ещё $s$ элементарными транспозициями. Всего $2s + 1$ элементарных транспозиций — нечётное число, и каждая меняет чётность. Значит, чётность меняется. $\blacksquare$

1. Пусть нужно перейти от $(i_1, \dots, i_n)$ к $(j_1, \dots, j_n)$. Если $i_1 \ne j_1$, переставим $i_1$ с элементом $j_1$, после чего на первом месте стоит $j_1$. Затем так же устанавливаем на нужное место второй элемент, не трогая первый, и т.д. Каждый шаг требует не более одной транспозиции, а последний элемент встаёт на место автоматически.

2. Сопоставим каждой перестановке перестановку, полученную обменом первых двух элементов. Это отображение совпадает со своим обратным, поэтому оно взаимно однозначно. Оно переводит чётные перестановки в нечётные и наоборот. Значит, тех и других поровну, а всего их $n!$. $\blacksquare$

1–3. Композиция взаимно однозначных отображений взаимно однозначна. Композиция ассоциативна: обе части равенства 2 переводят $i$ в $\sigma(\tau(\rho(i)))$. Тождественное отображение нейтрально.

4. Взаимно однозначное отображение имеет обратное. Если $\sigma\tau' = \varepsilon$ и $\tau''\sigma = \varepsilon$, то $\tau'' = \tau''(\sigma\tau') = (\tau''\sigma)\tau' = \tau'$, что доказывает единственность. Далее, $(\sigma\tau)(\tau^{-1}\sigma^{-1}) = \sigma(\tau\tau^{-1})\sigma^{-1} = \varepsilon$, и аналогично в другом порядке.

5. Пусть $\sigma = (1\ 2)$, $\tau = (1\ 3)$. Тогда $(\sigma\tau)(1) = \sigma(3) = 3$, а $(\tau\sigma)(1) = \tau(2) = 2$. $\blacksquare$

Возьмём элемент $i$ и рассмотрим последовательность $i, \sigma(i), \sigma^2(i), \dots$. Она принимает конечное число значений, поэтому $\sigma^k(i) = \sigma^l(i)$ при некоторых $k > l \ge 0$. Применив $l$ раз $\sigma^{-1}$, получаем $\sigma^{k-l}(i) = i$. Пусть $d$ — наименьшее натуральное число с $\sigma^d(i) = i$. Тогда элементы $i, \sigma(i), \dots, \sigma^{d-1}(i)$ различны, и $\sigma$ действует на них как цикл. Это множество называется орбитой элемента $i$.

Орбиты двух элементов либо совпадают, либо не пересекаются: орбита любого своего элемента совпадает со всей орбитой. Поэтому $\{1, \dots, n\}$ разбивается на непересекающиеся орбиты. Пусть $c_1, \dots, c_s$ — циклы, отвечающие орбитам длины $\ge 2$. Они независимы. Любой элемент сдвигается только «своим» циклом, остальные его не двигают, поэтому $\sigma = c_1 c_2 \cdots c_s$ при любом порядке множителей.

Единственность. Пусть $\sigma = c_1' \cdots c_t'$ — разложение в независимые циклы, и элемент $i$ входит в цикл $c'$. Остальные циклы не двигают ни $i$, ни его образы, поэтому $c'$ переводит $i \mapsto \sigma(i) \mapsto \sigma^2(i) \mapsto \dots$. Значит, $c'$ совпадает с циклом орбиты $i$. $\blacksquare$

В правой части сначала действует $(i_1\ i_2)$, затем $(i_1\ i_3)$, …, последней — $(i_1\ i_k)$. Элементы вне цикла неподвижны.

• $i_1$: первая транспозиция переводит его в $i_2$, остальные $i_2$ не двигают. Итог: $i_2$.
• $i_m$ при $2 \le m < k$: транспозиции до $(i_1\ i_m)$ его не двигают, $(i_1\ i_m)$ переводит в $i_1$, следующая $(i_1\ i_{m+1})$ — в $i_{m+1}$, остальные $i_{m+1}$ не двигают. Итог: $i_{m+1}$.
• $i_k$: его двигает лишь последняя транспозиция $(i_1\ i_k)$. Итог: $i_1$.

Это в точности действие цикла. Второе утверждение следует из разложения подстановки в произведение независимых циклов; для $\varepsilon$ можно взять, например, $(1\ 2)(1\ 2)$. $\blacksquare$

Лемма. Если $t = (i\ j)$, то $\operatorname{sgn}(\sigma t) = -\operatorname{sgn}\sigma$. Действительно, $(\sigma t)(i) = \sigma(j)$, $(\sigma t)(j) = \sigma(i)$, остальные значения те же. Значит, нижняя строка записи $\sigma t$ получается из нижней строки $\sigma$ транспозицией элементов на местах $i$ и $j$, и чётность меняется.

Пусть $\tau = t_1 t_2 \cdots t_m$ — разложение в транспозиции (оно существует: каждый цикл — произведение транспозиций). Применяя лемму $m$ раз к $\sigma\tau = (\dots((\sigma t_1) t_2)\dots) t_m$, получаем

При $\sigma = \varepsilon$ (нижняя строка без инверсий, $\operatorname{sgn}\varepsilon = 1$) это даёт $\operatorname{sgn}\tau = (-1)^m$, что доказывает пункт 2. Подставив это в предыдущее равенство, получаем пункт 1.

Из $\sigma\sigma^{-1} = \varepsilon$ следует $\operatorname{sgn}\sigma\operatorname{sgn}\sigma^{-1} = 1$. Цикл длины $k$ — произведение $k-1$ транспозиций. $\blacksquare$