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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
6 перестановок 3-х шаров

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

В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову "перестановка" в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки.)

Свойства[править | править вики-текст]

P_n=A_n^n=\frac {n!}{(n-n)!}=\frac {n!}{0!}=n!=1\cdot 2\cdot\dots\cdot n.
  • Композиция определяет операцию произведения на перестановках одного порядка: (\pi\cdot\sigma)(k) = \pi(\sigma(k)). Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают S_n.
  • Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент a \in G сопоставляется с перестановкой \pi_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 является всякая неподвижная точка отображения \pi\colon X\to X, то есть элемент множества \{x\in X\mid\pi(x)=x\}. Множество всех неподвижных точек перестановки \pi является дополнением её носителя в X.
  • Инверсией в перестановке \pi порядка n называется всякая пара индексов i, j такая, что 1\leqslant i<j\leqslant n и \pi(i)>\pi(j). Чётность числа инверсий в перестановке определяет чётность перестановки.

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

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

Подстановка[править | править вики-текст]

Перестановка \pi множества 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 и \pi(x_i)=y_i.

Произведения циклов и знак перестановки[править | править вики-текст]

Любая перестановка \pi \ne e может быть разложена в произведение (композицию) непересекающихся циклов длины l \geqslant 2, причём единственным образом с точностью до порядка следования циклов в произведении. Например:

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

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. Для произвольного цикла длины l \geqslant 2 разложение можно написать так: (x_1,\dots, x_l) = (x_1,x_l)(x_1,x_{l-1})\dots (x_1, x_2). Циклы длины 1 действуют как тождественная перестановка и тоже могут быть легко разложены, так как квадрат любой транспозиции есть тождественная перестановка: (1, 2)(1, 2) = (2, 3)(2, 3) = e. Такое разложение циклов на произведение транспозиций не будет единственным: (1, 2, 3) = (1, 3)(1, 2) = (2, 3)(1, 3) = (1, 3)(2, 4)(1, 2)(2, 4).

Таким образом любая перестановка может быть разложена в произведение транспозиций. Хотя это разложение и не будет единственным, но чётность числа транспозиций, входящих в разложение, сохраняется. Пусть перестановка \pi разложена в произведение k транспозиций, тогда знаком перестановки (иначе: чётностью перестановки или сигнатурой перестановки) \pi называют число \varepsilon_{\pi} = (-1)^k, при этом \pi называют чётной перестановкой, если \varepsilon_{\pi} = 1, и нечётной перестановкой, если \varepsilon_{\pi} = -1.

Знак перестановки \pi также может быть определен через число инверсий N(\pi) в этой перестановке: \varepsilon_{\pi} = (-1)^{N(\pi)}.


Замечание. Имеется два соглашения по умножению перестановок и циклов:

1) (\sigma \circ \tau)(i) = \sigma (\tau (i)).

Например: (1 2)(2 3) = (1 2 3) .

2)  (i)(\sigma \circ \tau) = ((i)\sigma ) \tau .

Например: (1 2)(2 3) = (1 3 2).

Перестановки с повторением[править | править вики-текст]

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если ki — количество элементов i-го типа, то k_1+k_2+\dots+k_m=n и количество всевозможных перестановок с повторениями равно мультиномиальному коэффициенту \textstyle \binom{n}{k_1,\ k_2,\ \dots,\ k_m} = \frac{n!}{k_1!k_2!\dots k_m!}.

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

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

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

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_{ij}, таких что

\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_{ij} не зависят от i, то перестановку \xi называют одинаково распределённой. Если же нет зависимости от j, то есть \scriptstyle \forall i,j (1\le i,j \le n): p_{ij}=1/n, то \xi называют однородной.

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

Примечания[править | править вики-текст]

  1. Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
  2. Теория конфигураций и теория перечислений
  3. Глава 3. Элементы комбинаторики. // Лекции по теории вероятностей.
  4. Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]