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

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

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

В более общем смысле, перестановкой произвольного (обычно конечного) множества называется всякая биекция этого множества на себя.

Содержание

1 Свойства
2 Связанные определения
- 2.1 Специальные типы перестановок
- 2.2 Подстановки и произведения циклов
3 Случайная перестановка
4 Литература
5 См. также

[править] Свойства

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

[править] Связанные определения

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

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

Основная статья: Обобщённая схема размещения

Случайной перестановкой называется называется случайный вектор $\xi=(\xi_1, \ldots , \xi_n),$ все элементы которого принимают натуральные значения от 1 до $n,$ и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка $ξ$ , для которой

$P\{\xi=\sigma\}=\frac{p_{1\sigma(1)}\ldots p_{n\sigma(n)}}{\sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}}$

для некоторых $p i j,$ таких что

$\forall i (1\leqslant i \leqslant n): p_{i1}+\ldots + p_{in}=1$

$\sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}>0.$

Если при этом $p i j$ не зависят от $i$ , то перестановку $ξ$ называют одинаково распределённой. Если же нет зависимости от $j$ , то есть $\scriptstyle \forall i,j (1\le i,j \le n): p_{ij}=1/n,$ то $ξ$ называют однородной.