Русская Википедия:Перестановка
В комбинаторике перестано́вкой заданного конечного множества <math>X = \{a_1, a_2, \ldots, a_n\}</math> (все элементы <math>X</math> различны) называется произвольный упорядоченный набор всех элементов <math>X</math> (без повторений). Группируя эти элементы в разном порядке, можно получить различные перестановки. Всего из множества с <math>n</math> элементами можно получить <math>n! = 1\cdot 2\cdot 3 \cdot \ldots \cdot n</math> (<math>n</math>-факториал) различных перестановок (см. рисунок)[1][2].
Перестановка является частным случаем размещения, когда выбираются все элементы множества[1].
Подстановка
Перестановку можно рассматривать как функцию, которая каждому элементу некоторой начальной перестановки сопоставляет соответствующий по номеру элемент данной перестановки. Такую функцию часто называют подстановкойШаблон:Sfn. Перестановка <math>\pi</math> множества <math>X</math> может быть наглядно представлена в виде таблицы:
- <math>\begin{pmatrix}
x_1 & x_2 & x_3 & \ldots & x_n \\ y_1 & y_2 & y_3 & \ldots & y_n\end{pmatrix},</math> где <math>\{x_1,\;\ldots,\;x_n\} = \{y_1,\;\ldots,\;y_n\} = X</math> и <math>\pi(x_i)=y_i</math>.
Пример: перестановка элементов множества <math>X</math> в обратном порядке:
- <math>\begin{pmatrix}
x_1 & x_2 & x_3 & \ldots & x_n \\ x_n & x_{n-1} & x_{n-2} & \ldots & x_1\end{pmatrix},</math>
Инверсией в перестановке <math>\pi</math> называется всякая пара индексов <math>i,\ j</math> такая, что <math>1\leqslant i<j\leqslant n</math> и <math>\pi(i)>\pi(j)</math>. Чётность числа инверсий в перестановке определяет чётность перестановки. Пример:
- <math>\begin{pmatrix}
1 & 2 & 3 \\ 1 & 3 & 2\end{pmatrix},</math> Здесь элементы 2 и 3 образуют инверсию.
Связанные определения
Носитель перестановки <math>\pi\colon X\to X</math> — это подмножество множества <math>X</math>, определяемое как <math>\operatorname{supp}(\pi):=\{x\in X\mid\pi(x)\ne x\}.</math>
Неподвижной точкой перестановки <math>\pi</math> является всякая неподвижная точка отображения <math>\pi\colon X\to X</math>, то есть элемент множества <math>\{x\in X\mid\pi(x)=x\}.</math> Множество всех неподвижных точек перестановки <math>\pi</math> является дополнением её носителя в <math>X</math>.
Специальные типы перестановок
- Тождественная перестановка — перестановка <math>e,</math> которая каждый элемент <math>x \in X</math> отображает в себя: <math>e(x) = x.</math>
- Инволюция — перестановка <math>\tau,</math> которая является обратной самой себе, то есть <math>\tau\cdot\tau=e.</math>
- Беспорядок — перестановка без неподвижных точек.
- Циклом длины <math>\ell</math> называется такая подстановка <math>\pi,</math> которая тождественна на всём множестве <math>X,</math> кроме подмножества <math>\{x_1,\;x_2,\;\ldots,\;x_\ell\}\subset X</math> и <math>\pi(x_\ell)=x_1,\ \pi(x_i)=x_{i+1}.</math> Обозначается <math>(x_1,\;x_2,\;\ldots,\;x_\ell).</math>.
- Транспозиция — перестановка элементов множества <math>X</math>, которая меняет местами два элемента. Транспозиция является циклом длины 2.
Произведения циклов и знак перестановки
Любая перестановка <math>\pi</math> может быть разложена в произведение (композицию) непересекающихся циклов длины <math>\ell \geqslant 2</math>, причём единственным образом с точностью до порядка следования циклов в произведении. Например:
- <math>\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 1 & 6 & 4 & 2 & 3\end{pmatrix} = (1,\;5,\;2)(3,\;6).</math>
Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведённого выше примера таким дополненным разложением будет <math>(1,\;5,\;2)(3,\;6)(4)</math>. Число циклов разной длины, а именно набор чисел <math>(c_1,\;c_2,\;\ldots)</math>, где <math>c_{\ell}</math> — это число циклов длины <math>\ell</math>, определяет цикловую структуру перестановки. При этом величина <math>1\cdot c_1 + 2\cdot c_2 + \ldots</math> равна длине перестановки, а величина <math>c_1 + c_2 + \ldots</math> равна общему числу циклов. Число перестановок из <math>n</math> элементов с <math>k</math> циклами даётся числом Стирлинга первого рода без знака <math>\begin{bmatrix}n\\k\end{bmatrix}</math>.
Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой <math>e</math>) можно представить как Шаблон:Нп5 транспозиций или, например, как квадрат любой транспозиции: <math>(1,\;2)(1,\;2) = (2,\;3)(2,\;3) = e.</math> Цикл длины <math>\ell \geqslant 2</math> можно разложить в произведение <math>\ell-1</math> транспозиций следующим образом:
- <math>(x_1,\;\ldots,\;x_l) = (x_1,\;x_{\ell})(x_1,\;x_{\ell-1})\dots (x_1,\;x_2).</math>
Следует заметить, что разложение циклов на произведение транспозиций не является единственным:
- <math>(1,\;2,\;3) = (1,\;3)(1,\;2) = (2,\;3)(1,\;3) = (1,\;3)(2,\;4)(2,\;4)(1,\;2).</math>
Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, чётность числа транспозиций во всех таких разложениях одинакова. Это позволяет определить знак перестановки (чётностью перестановки или сигнатурой перестановки) <math>\pi</math> как:
- <math>\varepsilon_{\pi} = (-1)^t,</math>
где <math>t</math> — число транспозиций в каком-то разложении <math>\pi</math>. При этом <math>\pi</math> называют чётной перестановкой, если <math>\varepsilon_{\pi} = 1</math>, и нечётной перестановкой, если <math>\varepsilon_{\pi} = -1</math>.
Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки <math>\pi</math> из <math>n</math> элементов, состоящий из <math>k</math> циклов, равен
- <math>\varepsilon_{\pi} = (-1)^{n-k}</math>.
Знак перестановки <math>\pi</math> также может быть определён через число инверсий <math>N(\pi)</math> в <math>\pi</math>:
- <math>\varepsilon_{\pi} = (-1)^{N(\pi)}</math>.
Вариации и обобщения
В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют (приведённый выше) наглядный способ записи перестановки. Более существенное отличие состоит в том, что подстановка — это непосредственно функция, а перестановка — результат применения этой функции к элементам последовательности.)
Композиция определяет операцию произведения на перестановках одной длины: <math>(\pi\cdot\sigma)(k) = \pi(\sigma(k)).</math> Относительно этой операции множество перестановок из <math>n</math> элементов образует группу, которую называют симметрической и обычно обозначают <math>S_n</math>.
Любая конечная группа порядка <math>n</math> изоморфна некоторой подгруппе симметрической группы <math>S_n</math> (теорема Кэли). При этом каждый элемент <math>a \in G</math> сопоставляется с перестановкой <math>\pi_a</math>, задаваемой на элементах <math>G</math> тождеством <math>\pi_a(g)=a \circ g,</math> где <math>\circ</math> — групповая операция в <math>G</math>.
Перестановки с повторением
Рассмотрим <math>n</math> элементов <math>m</math> различных типов, причём в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если <math>k_i</math> — число элементов <math>i</math>-го типа, то <math>k_1+k_2+\ldots+k_m=n</math> и число всевозможных перестановок с повторениями равно мультиномиальному коэффициенту <math>\textstyle \binom{n}{k_1,\;k_2,\;\ldots,\;k_m} = \frac{n!}{k_1!k_2!\ldots k_m!}.</math>
Перестановку с повторениями можно также рассматривать как перестановку мультимножества <math>\{ 1^{k_1},\;2^{k_2},\;\ldots,\;m^{k_m} \}</math> мощности <math>k_1+k_2+\ldots+k_m=n</math>.
Случайная перестановка
Случайной перестановкой называется случайный вектор <math>\xi=(\xi_1,\;\ldots,\;\xi_n),</math> все элементы которого принимают натуральные значения от 1 до <math>n,</math> и при этом вероятность совпадения любых двух элементов равна 0.
Независимой случайной перестановкой называется такая случайная перестановка <math>\xi</math>, для которой:
- <math>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)}}</math>
для некоторых <math>p_{ij},</math> таких, что:
- <math>\forall i\ (1\leqslant i \leqslant n)\colon p_{i1}+\ldots + p_{in}=1</math>
- <math>\sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}>0.</math>
Если при этом <math>p_{ij}</math> не зависят от <math>i</math>, то перестановку <math>\xi</math> называют одинаково распределённой. Если же нет зависимости от <math>j</math>, то есть <math>\forall i,\;j\ (1\leqslant i,\;j \leqslant n)\colon p_{ij}=1/n,</math> то <math>\xi</math> называют однородной.
См. также
Примечания
Литература
Ссылки
