Перестановка
Перестано́вка (англ. Permutations) в комбинаторике — упорядоченный набор без повторений чисел [math]\displaystyle{ 1,\ 2,\ \ldots,\ n, }[/math] обычно трактуемый как биекция на множестве [math]\displaystyle{ \{ 1,\;2,\;\ldots,\;n \} }[/math], которая числу [math]\displaystyle{ i }[/math] ставит в соответствие [math]\displaystyle{ i }[/math]-й элемент из набора. Число [math]\displaystyle{ n }[/math] при этом называется длиной перестановки[1].
В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки. Более существенное отличие состоит в том, что подстановка — это непосредственно функция, а перестановка — результат применения этой функции к элементам последовательности.)
Перестановкой называются наборы, состоящие из одного и того же числа элементов, отличающихся только порядком следования элементов.[2]
Свойства
Число всех перестановок из [math]\displaystyle{ n }[/math] элементов равно числу размещений из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ n }[/math], то есть факториалу[3][4][5][6]:
- [math]\displaystyle{ P_n=A_n^n=\frac {n!}{(n-n)!}=\frac {n!}{0!}=n!=1\cdot 2\cdot\ldots\cdot n }[/math].
Композиция определяет операцию произведения на перестановках одной длины: [math]\displaystyle{ (\pi\cdot\sigma)(k) = \pi(\sigma(k)). }[/math] Относительно этой операции множество перестановок из [math]\displaystyle{ n }[/math] элементов образует группу, которую называют симметрической и обычно обозначают [math]\displaystyle{ S_n }[/math].
Любая конечная группа из [math]\displaystyle{ n }[/math] элементов изоморфна некоторой подгруппе симметрической группы [math]\displaystyle{ S_n }[/math] (теорема Кэли). При этом каждый элемент [math]\displaystyle{ a \in G }[/math] сопоставляется с перестановкой [math]\displaystyle{ \pi_a }[/math], задаваемой на элементах [math]\displaystyle{ G }[/math] тождеством [math]\displaystyle{ \pi_a(g)=a \circ g, }[/math] где [math]\displaystyle{ \circ }[/math] — групповая операция в [math]\displaystyle{ G }[/math].
Связанные определения
Носитель перестановки [math]\displaystyle{ \pi\colon X\to X }[/math] — это подмножество множества [math]\displaystyle{ X }[/math], определяемое как [math]\displaystyle{ \operatorname{supp}(\pi):=\{x\in X\mid\pi(x)\ne x\}. }[/math]
Неподвижной точкой перестановки [math]\displaystyle{ \pi }[/math] является всякая неподвижная точка отображения [math]\displaystyle{ \pi\colon X\to X }[/math], то есть элемент множества [math]\displaystyle{ \{x\in X\mid\pi(x)=x\}. }[/math] Множество всех неподвижных точек перестановки [math]\displaystyle{ \pi }[/math] является дополнением её носителя в [math]\displaystyle{ X }[/math].
Инверсией в перестановке [math]\displaystyle{ \pi }[/math] называется всякая пара индексов [math]\displaystyle{ i,\ j }[/math] такая, что [math]\displaystyle{ 1\leqslant i\lt j\leqslant n }[/math] и [math]\displaystyle{ \pi(i)\gt \pi(j) }[/math]. Чётность числа инверсий в перестановке определяет чётность перестановки.
Специальные типы перестановок
- Тождественная перестановка — перестановка [math]\displaystyle{ e, }[/math] которая каждый элемент [math]\displaystyle{ x \in X }[/math] отображает в себя: [math]\displaystyle{ e(x) = x. }[/math]
- Инволюция — перестановка [math]\displaystyle{ \tau, }[/math] которая является обратной самой себе, то есть [math]\displaystyle{ \tau\cdot\tau=e. }[/math]
- Беспорядок — перестановка без неподвижных точек.
- Циклом длины [math]\displaystyle{ \ell }[/math] называется такая подстановка [math]\displaystyle{ \pi, }[/math] которая тождественна на всём множестве [math]\displaystyle{ X, }[/math] кроме подмножества [math]\displaystyle{ \{x_1,\;x_2,\;\ldots,\;x_\ell\}\subset X }[/math] и [math]\displaystyle{ \pi(x_\ell)=x_1,\ \pi(x_i)=x_{i+1}. }[/math] Обозначается [math]\displaystyle{ (x_1,\;x_2,\;\ldots,\;x_\ell). }[/math].
- Транспозиция — перестановка элементов множества [math]\displaystyle{ X }[/math], которая меняет местами два элемента. Транспозиция является циклом длины 2.
Подстановка
Перестановка [math]\displaystyle{ \pi }[/math] множества [math]\displaystyle{ X }[/math] может быть записана в виде подстановки, например:
- [math]\displaystyle{ \begin{pmatrix} x_1 & x_2 & x_3 & \ldots & x_n \\ y_1 & y_2 & y_3 & \ldots & y_n\end{pmatrix}, }[/math]
где [math]\displaystyle{ \{x_1,\;\ldots,\;x_n\}=\{y_1,\;\ldots,\;y_n\}=X }[/math] и [math]\displaystyle{ \pi(x_i)=y_i }[/math].
Произведения циклов и знак перестановки
Любая перестановка [math]\displaystyle{ \pi }[/math] может быть разложена в произведение (композицию) непересекающихся циклов длины [math]\displaystyle{ \ell \geqslant 2 }[/math], причём единственным образом с точностью до порядка следования циклов в произведении. Например:
- [math]\displaystyle{ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 1 & 6 & 4 & 2 & 3\end{pmatrix} = (1,\;5,\;2)(3,\;6). }[/math]
Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведенного выше примера таким дополненным разложением будет [math]\displaystyle{ (1,\;5,\;2)(3,\;6)(4) }[/math]. Число циклов разной длины, а именно набор чисел [math]\displaystyle{ (c_1,\;c_2,\;\ldots) }[/math], где [math]\displaystyle{ c_{\ell} }[/math] — это число циклов длины [math]\displaystyle{ \ell }[/math], определяет цикловую структуру перестановки. При этом величина [math]\displaystyle{ 1\cdot c_1 + 2\cdot c_2 + \ldots }[/math] равна длине перестановки, а величина [math]\displaystyle{ c_1 + c_2 + \ldots }[/math] равна общему числу циклов. Число перестановок из [math]\displaystyle{ n }[/math] элементов с [math]\displaystyle{ k }[/math] циклами даётся числом Стирлинга первого рода без знака [math]\displaystyle{ \begin{bmatrix}n\\k\end{bmatrix} }[/math].
Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой [math]\displaystyle{ e }[/math]) можно представить как пустое произведение[англ.] транспозиций или, например, как квадрат любой транспозиции: [math]\displaystyle{ (1,\;2)(1,\;2) = (2,\;3)(2,\;3) = e. }[/math] Цикл длины [math]\displaystyle{ \ell \geqslant 2 }[/math] можно разложить в произведение [math]\displaystyle{ \ell-1 }[/math] транспозиций следующим образом:
- [math]\displaystyle{ (x_1,\;\ldots,\;x_l) = (x_1,\;x_{\ell})(x_1,\;x_{\ell-1})\dots (x_1,\;x_2). }[/math]
Следует заметить, что разложение циклов на произведение транспозиций не является единственным:
- [math]\displaystyle{ (1,\;2,\;3) = (1,\;3)(1,\;2) = (2,\;3)(1,\;3) = (1,\;3)(2,\;4)(2,\;4)(1,\;2). }[/math]
Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, чётность числа транспозиций во всех таких разложениях одинакова. Это позволяет определить знак перестановки (чётностью перестановки или сигнатурой перестановки) [math]\displaystyle{ \pi }[/math] как:
- [math]\displaystyle{ \varepsilon_{\pi} = (-1)^t, }[/math]
где [math]\displaystyle{ t }[/math] — число транспозиций в каком-то разложении [math]\displaystyle{ \pi }[/math]. При этом [math]\displaystyle{ \pi }[/math] называют чётной перестановкой, если [math]\displaystyle{ \varepsilon_{\pi} = 1 }[/math], и нечётной перестановкой, если [math]\displaystyle{ \varepsilon_{\pi} = -1 }[/math].
Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки [math]\displaystyle{ \pi }[/math] из [math]\displaystyle{ n }[/math] элементов, состоящий из [math]\displaystyle{ k }[/math] циклов, равен
- [math]\displaystyle{ \varepsilon_{\pi} = (-1)^{n-k} }[/math].
Знак перестановки [math]\displaystyle{ \pi }[/math] также может быть определён через число инверсий [math]\displaystyle{ N(\pi) }[/math] в [math]\displaystyle{ \pi }[/math]:
- [math]\displaystyle{ \varepsilon_{\pi} = (-1)^{N(\pi)} }[/math].
Перестановки с повторением
Рассмотрим [math]\displaystyle{ n }[/math] элементов [math]\displaystyle{ m }[/math] различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если [math]\displaystyle{ k_i }[/math] — число элементов [math]\displaystyle{ i }[/math]-го типа, то [math]\displaystyle{ k_1+k_2+\ldots+k_m=n }[/math] и число всевозможных перестановок с повторениями равно мультиномиальному коэффициенту
[math]\displaystyle{ P_n=\textstyle \binom{n}{k_1,\;k_2,\;\ldots,\;k_m} = \frac{n!}{k_1!k_2!\ldots k_m!}. }[/math]
Если множество [math]\displaystyle{ n }[/math] состоит из элементов только двух типов, [math]\displaystyle{ k_1 }[/math] и [math]\displaystyle{ k_2=n-k_1 }[/math], то есть [math]\displaystyle{ n=k_1+k_2 }[/math], то перестановка с повторением рассчитывается также как и сочетание [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k_1 }[/math] (или [math]\displaystyle{ n }[/math] по [math]\displaystyle{ k_2 }[/math]):
[math]\displaystyle{ P_n(k_1,k_2)=P_n(k_1,(n-k_1)) = \frac{n!}{k_1!(n-k_1)!}. }[/math]
[math]\displaystyle{ P_n(k_1,k_2) = P_n(k_2,(n-k_2)) = \frac{n!}{k_2!(n-k_2)!}. }[/math]
Перестановку с повторениями можно также рассматривать как перестановку мультимножества [math]\displaystyle{ \{ 1^{k_1},\;2^{k_2},\;\ldots,\;m^{k_m} \} }[/math] мощности [math]\displaystyle{ k_1+k_2+\ldots+k_m=n }[/math].
Пример
Необходимо расчитать в каком порядке могут выезжать из автопарка 6 автомобилей, 2 из которых - одинаковые грузовые автомобили, 4 - одинаковые автобусы. Обозначим грузовые автомобили - [math]\displaystyle{ b }[/math], а автобусы - [math]\displaystyle{ a }[/math]. Для одинаковых грузовых автомобилей и одинаковых автобусов число возможных перестановок равно [math]\displaystyle{ \frac{6!}{2!4!} = 15 }[/math]
Грузовые автомобили и автобусы могут выезжать в 15 различных комбинациях (где, например, [math]\displaystyle{ bbaaaa }[/math] означает, что сначала выезжают две грузовые машины, а потом четыре автобуса ):
[math]\displaystyle{ bbaaaa, babaaa, baabaa, baaaba, baaaab, abbaaa, ababaa, abaaba, }[/math] [math]\displaystyle{ abaaab, aabbaa, aababa, aabaab, aaabba, aaabab, aaaabb }[/math]
Случайная перестановка
Случайной перестановкой называется случайный вектор [math]\displaystyle{ \xi=(\xi_1,\;\ldots,\;\xi_n), }[/math] все элементы которого принимают натуральные значения от 1 до [math]\displaystyle{ n, }[/math] и при этом вероятность совпадения любых двух элементов равна 0.
Независимой случайной перестановкой называется такая случайная перестановка [math]\displaystyle{ \xi }[/math], для которой:
- [math]\displaystyle{ 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]\displaystyle{ p_{ij}, }[/math] таких, что:
- [math]\displaystyle{ \forall i\ (1\leqslant i \leqslant n)\colon p_{i1}+\ldots + p_{in}=1 }[/math]
- [math]\displaystyle{ \sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}\gt 0. }[/math]
Если при этом [math]\displaystyle{ p_{ij} }[/math] не зависят от [math]\displaystyle{ i }[/math], то перестановку [math]\displaystyle{ \xi }[/math] называют одинаково распределённой. Если же нет зависимости от [math]\displaystyle{ j }[/math], то есть [math]\displaystyle{ \forall i,\;j\ (1\leqslant i,\;j \leqslant n)\colon p_{ij}=1/n, }[/math] то [math]\displaystyle{ \xi }[/math] называют однородной.
См. также
Примечания
- ↑ Евгений Вечтомов, Дмитрий Широков. Математика: логика, множества, комбинаторика. Учебное пособие для академического бакалавриата. — 2-е изд.. — Litres, 2018-03-02. — С. 145—146. — 244 с. Архивная копия от 7 апреля 2022 на Wayback Machine
- ↑ Теория вероятностей и элементы математической статистики Архивная копия от 1 февраля 2022 на Wayback Machine
- ↑ Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
- ↑ Теория конфигураций и теория перечислений . Дата обращения: 30 декабря 2009. Архивировано 23 января 2010 года.
- ↑ Глава 3. Элементы комбинаторики Архивная копия от 4 января 2010 на Wayback Machine. // Лекции по теории вероятностей.
- ↑ Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы
Литература
- Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
- Кострикин А. И. Введение в алгебру. Основы алгебры. — М.: Физматлит, 1994. — С. 59-71. — 320 с. — ISBN 5-02-014644-7.
- Сергей Мельников. Перестановки, сочетания, размещения: вывод всех перестановок // Delphi и Turbo Pascal на занимательных примерах. — БХВ-Петербург, 2012. — 448 с. — ISBN 978-5-94157-886-3.
Ссылки
- Аранжеман // Энциклопедический словарь Брокгауза и Ефрона : в 86 т. (82 т. и 4 доп.). — СПб., 1890—1907.