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

6 перестановок трёх шаров

Перестано́вка (англ. 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] при этом называется длиной перестановки.

В теории групп под перестановкой произвольного множества подразумевается биекция этого множества на себя. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово подстановка. (Другие авторы подстановкой называют наглядный способ записи перестановки. Более существенное отличие состоит в том, что подстановка — это непосредственно функция, а перестановка — результат применения этой функции к элементам последовательности.)

Перестановкой называются наборы, состоящие из одного и того же числа элементов, отличающихся только порядком следования элементов.

Свойства

Число всех перестановок из [math]\displaystyle{ n }[/math] элементов равно числу размещений из [math]\displaystyle{ n }[/math] по [math]\displaystyle{ n }[/math], то есть факториалу:

[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] называют однородной.

См. также

• Алгоритм Нарайаны
• Анаграмма
• Гигантская компонента
• Размещение
• Симметрическая группа
• Сочетание

Литература

• Дональд Кнут. Искусство программирования, том 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.