Инверсия (перестановка)

Перестано́вка — это упорядоченный набор чисел $1, 2,\dots, n.$ При этом n называется порядком перестановки. Число всех перестановок порядка n равно $n!=1\cdot 2\cdot\dots\cdot n.$

Более общо, перестановкой произвольного (хотя обычно конечного) множества X называется биекция $\pi: X\to X$.

Свойства

• Композиция определяет операцию произведения на перестановках $(\pi\cdot\sigma)(k) = \pi(\sigma(k)).$ Относительно этой операции множество перестановок образует группу, которую называют симметрической и обычно обозначают S_n (n — количество переставляемых элементов).
• Любая группа является подгруппой группы перестановок некоторого множества (например множества элементов этой группы). Каждый элемент $a \in G$ сопоставляется с перестановкой $\pi_a: \forall g \in G: \pi_a(g)=a \circ g,$ где $\circ$ — операция в группе G.

Связанные определения

• Носитель перестановки $\pi:X\to X$ — это подмножество множества X, определяемое как $\operatorname{supp}(\pi)=\{x\in X\mid\pi(x)\ne x\}.$
• Неподвижной точкой перестановки π является всякая неподвижная точка отображения $\pi:X\to X$, то есть элемент множества $\{x\in X\mid\pi(x)=x\}.$ Множество всех неподвижных точек перестановки π является дополнением её носителя в X.
• Инверсией в перестановке π порядка n называется всякая пара индексов i, j такая, что $1\leq i<j\leq n$ и π(i) > π(j). Чётность числа инверсий в перестановке определяет чётность перестановки.

Специальные типы перестановок

• Инволюция — перестановка τ, которая является обратной самой себе, то есть $\tau\cdot\tau=id.$
• Беспорядок — перестановка без неподвижных точек.
• Циклом длины $\ell$ называется такая подстановка π, которая тождественна на всём множестве X, кроме подмножества $\{x_1,x_2,\dots,x_\ell\}\subset X$ и $\pi(x_\ell)=x_1,$ π(x_i) = x_{i + 1}. Обозначается $(x_1,x_2,\dots,x_\ell).$
• Транспозиция — перестановка элементов множества X, которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановки и произведения циклов

Перестановка π множества X может быть записана в виде подстановки, например:

$\begin{pmatrix} x_1 & x_2 & x_3 & \dots & x_n \\ y_1 & y_2 & y_3 & \dots & y_n\end{pmatrix},$

где $\{x_1,\dots, x_n\}=\{y_1,\dots, y_n\}=X$ и π(x_i) = y_i.

Перестановку также можно записать в виде произведения непересекающихся циклов, причем единственным образом с точностью до порядка следования циклов в произведении. Например:

$(1\, 5\, 2)(3\, 6)(4)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 1 & 6 & 4 & 2 & 3\end{pmatrix}.$

Случайная перестановка

Случайной перестановкой называется называется случайный вектор ξ = (ξ₁,...,ξ_n), все элементы которого принимают натуральные значения от 1 до n, и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка ξ, для которой $P\{\xi=\sigma\}=\frac{p_{1\sigma(1)}...p_{n\sigma(n)}}{\sum\limits_{\pi \in S_n}p_{1\pi(1)}...p_{n\pi(n)}}$ для некоторых p_ij, для которых $\forall i (1\le i \le n): p_{i1}+...+p_{in}=1$ и $\sum\limits_{\pi \in S_n}p_{1\pi(1)}...p_{n\pi(n)}>0.$ Если при этом p_ij не зависят от i, то перестановку ξ называют одинаково распределённой. Если же нет зависимости от j, то есть $\forall i,j (1\le i,j \le n): p_{ij}=1/n,$ то ξ называют однородной.

См. также

• Чётность перестановки (англ.)
• Гигантская компонента