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

Материал из Википедии — свободной энциклопедии

Перестано́вка или подстановка — это упорядоченный набор чисел $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))$ . Относительно этой операции множество перестановок образует группу, называемую симметрической группой. Нейтральным элементом в симметрической группе является тождественная перестановка $i d$ , определяемая как тождественное отображение $i d (k) = k$ .

Перестановка $π$ множества $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$ .

Любая группа является подгруппой группы перестановок некоторого множества (например множества элементов этой группы).

[править] Типы перестановок

Транспозиция — перестановка множества X, которая меняет местами только два элемента.
Циклом длины $\ell$ называется такая подстановка $π$ которая тождественна на всём множестве $X$ , кроме подмножества $\{x_1,x_2,\dots,x_\ell\}$ и $\pi(x_\ell)=x_1$ , $π(x i) = x i + 1$ . Обозначается $(x_1,x_2,\dots,x_\ell)$ .