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

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

Перейти к: навигация, поиск

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

В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя. Множество всех перестановок данного множества G является симметрической группой.

Содержание

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

  • Число всех перестановок порядка n равно факториалу n!=1\cdot 2\cdot\dots\cdot n.
  • Композиция определяет операцию произведения на перестановках одного порядка: (\pi\cdot\sigma)(k) = \pi(\sigma(k)). Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают Sn.
  • Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент 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, π(xi) = xi + 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 и π(xi) = yi.

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

(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)}}

для некоторых pij, таких что

\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.

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

[править] Литература

Question book-4.svg
 В этой статье не хватает ссылок на источники информации.
Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.

[править] См. также

Источник — «http://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0»