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

**Перестановка** – упорядоченный кортеж элементов, где все элементы различны. $S_{n}$ - множество всех перестановок. $|S_{n}| = n!$

**Инверсией** (беспорядком) называется пара $(i, j)$, если $i < j$, но $\sigma(i) > \sigma(j)$

**Чётность перестановки** - чётность числа инверсий Если $\sigma$ — перестановка, то $$(-1)^{\sigma} = \left\{ \begin{matrix} 1, & \text{если число инверсий чётно} \\ -1, & \text{если нечётно} \end{matrix} \right.$$

**Транспозицией** $(i, j)$ называют перестановку $\sigma \in S_k$, которая действует по правилу: $$\sigma(x) = \begin{cases} j, & x = i \\ i, & x = j \\ x, & \text{иначе} \end{cases}$$ Т.е. меняет местами два элемента с индексами $i$ и $j$. Транспозиция называется **смежной**, если меняются соседние элементы.

Если $\sigma_{2} = \sigma_{1} \circ \tau$, где $\tau$ - транспозиция, то у $\sigma_{1}$ и $\sigma_{2}$ разная чётностью. (т.е. если перестановки отличаются на транспозицию)

**Случай смежной транспозиции** Пусть $\tau = (i, i+1)$. При перестановке $s_i$ и ${} s_{i+1} {}$ количество инверсий изменяется на $\pm 1$ $\implies$ чётность меняется. **Общий случай** Пусть $\tau = (i, i+k)$. Реализуем транспозицию как композицию смежных транспозиций: $$\begin{align} k~ &\begin{cases} (s_{i}, s_{i+1}) \\ (s_{i+1}, s_{i+2}) \\ \dots \\ (s_{i+k-1}, s_{i+k}) \\ \end{cases} \\ k-1~ &\begin{cases} (s_{i+k-2}, s_{i+k-1}) \\ \dots \\ (s_{i}, s_{i+1}) \end{cases} \end{align}$$ Получаем, что число смежных транспозиций - $2k - 1$. Так как каждая меняет чётность и их нечётное число, то итоговая чётность изменяется. $\square$

Для $n \geq 2$ все $n!$ перестановок можно выписать так, что любые две соседние отличаются транспозицией.

Индукция по $n$. **База индукции** ($n=2$): $(1,2),~ (2,1)$ - отличаются транспозицией $(1,2)$ **Шаг индукции**: Пусть для $n$ утверждение верно. Для $n+1$: 1. Зафиксируем элемент ${} s_1$ на первом месте. Оставшиеся $n$ элементов перечислим по предположению индукции ($n!$ перестановок) 2. Возьмём последнюю перестановку и сделаем транспозицию $(s_{1}, s_{2})$ 3. Зафиксируем $s_2$ на первом месте и перечислим оставшиеся $n$ элементов ($n!$ перестановок). 4. Повторим для всех элементов Заметим: - В каждом блоке, где зафиксирован элемент, соседние перестановки отличаются на транспозицию по предположению индукции - Между концом одного блока и началом следующего перестановки отличаются на транспозицию из построения (пункт 2) Всего $(n+1) \cdot n! = (n+1)!$ перестановок. $\square$

Число чётных = число нечётных перестановок = $\dfrac{n!}{2}$

$$(-1)^{\sigma_{1} \circ \sigma_{2}} = (-1)^{\sigma_{1}} \cdot (-1)^{\sigma_{2}}$$

Запишем $\sigma_{2}$ как композицию транспозиций: $$\sigma_{2} = \varepsilon \circ \tau_{1} \circ \tau_{2} \circ \dots \circ \tau_{k}$$ Тогда: $$(-1)^{\sigma_{1} \circ \sigma_{2}} = (-1)^{\sigma_{1} \circ \tau_{1} \circ \dots \circ \tau_{k}} =^{*} (-1)^{\sigma_{1} \circ \tau_{1} \circ \dots \circ \tau_{k-1}} \cdot (-1) =^{*} \dots =^{*} (-1)^{\sigma_{1}} \cdot (-1)^{k}$$ $*$ - вынесли транспозицию как $(-1)$ по лемме Но по построению, $(-1)^{k} = (-1)^{\sigma_{2}}$, а значит $(-1)^{\sigma_{1} \circ \sigma_{2}} = (-1)^{\sigma_{1}} \cdot (-1)^{\sigma_{2}}$ $\square$

$\sigma$ и $\sigma^{-1}$ одной чётности

$$(-1)^{\sigma \circ \sigma^{-1}} = (-1)^\varepsilon = 1 = (-1)^\sigma \cdot (-1)^{\sigma^{-1}}$$ А значит чётность одинаковая $\square$