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

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

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

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

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

Свойства

Число всех перестановок из $n$ элементов равно числу размещений из $n$ по $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$.

Любая конечная группа из $n$ элементов изоморфна некоторой подгруппе симметрической группы $S_n$ (теорема Кэли). При этом каждый элемент $a\in G$ сопоставляется с перестановкой ${\pi }_a$, задаваемой на элементах $G$ тождеством ${\pi }_a(g)=a\circ g,$ где $\circ$ — групповая операция в $G$.

Связанные определения

Носитель перестановки $\pi :X\to X$ — это подмножество множества $X$, определяемое как $\mathrm{supp}(\pi ):=\{x\in X\mid \pi (x)\ne x\}.$

Неподвижной точкой перестановки $\pi$ является всякая неподвижная точка отображения $\pi :X\to X$, то есть элемент множества $\{x\in X\mid \pi (x)=x\}.$ Множество всех неподвижных точек перестановки $\pi$ является дополнением её носителя в $X$.

Инверсией в перестановке $\pi$ называется всякая пара индексов $i,j$ такая, что $1⩽i<j⩽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 }).$.
• Транспозиция — перестановка элементов множества $X$, которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановка

Перестановка $\pi$ множества $X$ может быть записана в виде подстановки, например:

$\left(\begin{array}{ccccc}{x}_1& x_2& x_3& \dots & x_n\\ y_1& y_2& y_3& \dots & y_n\end{array}\right),$

где $\{x_1,\dots ,x_n\}=\{y_1,\dots ,y_n\}=X$ и $\pi (x_i)=y_i$.

Произведения циклов и знак перестановки

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

$\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 5& 1& 6& 4& 2& 3\end{array}\right)=(1,5,2)(3,6).$

Часто также считают, что неподвижные точки перестановки представляют собой самостоятельные циклы длины 1, и дополняют ими цикловое разложение перестановки. Для приведенного выше примера таким дополненным разложением будет $(1,5,2)(3,6)(4)$. Число циклов разной длины, а именно набор чисел $(c_1,c_2,\dots )$, где $c_{\ell }$ — это число циклов длины $\ell$, определяет цикловую структуру перестановки. При этом величина $1\cdot c_1+2\cdot c_2+\dots$ равна длине перестановки, а величина $c_1+c_2+\dots$ равна общему числу циклов. Число перестановок из $n$ элементов с $k$ циклами даётся числом Стирлинга первого рода без знака $\left[\begin{array}{c}n\\ k\end{array}\right]$.

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой $e$) можно представить как пустое произведение транспозиций или, например, как квадрат любой транспозиции: $(1,2)(1,2)=(2,3)(2,3)=e.$ Цикл длины $\ell ⩾2$ можно разложить в произведение $\ell -1$ транспозиций следующим образом:

$(x_1,\dots ,x_l)=(x_1,x_{\ell })(x_1,x_{\ell -1})\dots (x_1,x_2).$

Следует заметить, что разложение циклов на произведение транспозиций не является единственным:

$(1,2,3)=(1,3)(1,2)=(2,3)(1,3)=(1,3)(2,4)(2,4)(1,2).$

Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, чётность числа транспозиций во всех таких разложениях одинакова. Это позволяет определить знак перестановки (чётностью перестановки или сигнатурой перестановки) $\pi$ как:

${\epsilon }_{\pi }=(-1{)}^t,$

где $t$ — число транспозиций в каком-то разложении $\pi$. При этом $\pi$ называют чётной перестановкой, если ${\epsilon }_{\pi }=1$, и нечётной перестановкой, если ${\epsilon }_{\pi }=-1$.

Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки $\pi$ из $n$ элементов, состоящий из $k$ циклов, равен

${\epsilon }_{\pi }=(-1{)}^{n-k}$.

Знак перестановки $\pi$ также может быть определён через число инверсий $N(\pi )$ в $\pi$:

${\epsilon }_{\pi }=(-1{)}^{N(\pi )}$.

Перестановки с повторением

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

$P_n=(\genfrac{}{}{0ex}{}{n}{k_1,k_2,\dots ,k_m})=\frac{n!}{k_1!k_2!\dots k_m!}.$

Если множество $n$ состоит из элементов только двух типов, $k_1$ и $k_2=n-k_1$, то есть $n=k_1+k_2$, то перестановка с повторением рассчитывается также как и сочетание $n$ по $k_1$ (или $n$ по $k_2$):

$P_n(k_1,k_2)=P_n(k_1,(n-k_1))=\frac{n!}{k_1!(n-k_1)!}.$

$P_n(k_1,k_2)=P_n(k_2,(n-k_2))=\frac{n!}{k_2!(n-k_2)!}.$

Перестановку с повторениями можно также рассматривать как перестановку мультимножества $\{1^{k_1},2^{k_2},\dots ,m^{k_m}\}$ мощности $k_1+k_2+\dots +k_m=n$.

Пример

Необходимо расчитать в каком порядке могут выезжать из автопарка 6 автомобилей, 2 из которых - одинаковые грузовые автомобили, 4 - одинаковые автобусы. Обозначим грузовые автомобили - $b$, а автобусы - $a$. Для одинаковых грузовых автомобилей и одинаковых автобусов число возможных перестановок равно $\frac{6!}{2!4!}=15$

Грузовые автомобили и автобусы могут выезжать в 15 различных комбинациях (где, например, $bbaaaa$ означает, что сначала выезжают две грузовые машины, а потом четыре автобуса ):

$bbaaaa,babaaa,baabaa,baaaba,baaaab,abbaaa,ababaa,abaaba,$ $abaaab,aabbaa,aababa,aabaab,aaabba,aaabab,aaaabb$

Случайная перестановка

Основная статья: Случайные перестановки

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

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

$P\{\xi =\sigma \}=\frac{p_{1\sigma (1)}\dots p_{n\sigma (n)}}{\sum _{\pi \in S_n}{p}_{1\pi (1)}\dots p_{n\pi (n)}}$

для некоторых $p_{ij},$ таких, что:

$\mathrm{\forall }i(1⩽i⩽n):p_{i1}+\dots +p_{in}=1$

$\sum _{\pi \in S_n}{p}_{1\pi (1)}\dots p_{n\pi (n)}>0.$

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

См. также

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

Литература

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