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

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

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

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

  • Транспозиция — перестановка множества X, которая меняет местами только два элемента.
  • Цикл длины \ell называется такая подстановка π которая тождественна на всём множестве X, кроме подмножества \{x_1,x_2,\dots,x_\ell\} и \pi(x_\ell)=x_1, π(xi) = xi + 1. Обозначается (x_1,x_2,\dots,x_\ell).
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home