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

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

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

Свойства

• Число всех перестановок порядка $n$ равно числу размещений из n по n, то есть факториалу:^[1][2][3][4]

$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)$. Чётность числа инверсий в перестановке определяет чётность перестановки.
• Знак перестановки определяется как +1 для чётной перестановки и −1 для нечётной, что выражается формулой $\sgn(\sigma)=(-1)^{N(\sigma)}$, где $N(\sigma)$ — количество инверсий в перестановке $\sigma$. Знак перестановки $\sigma$ может быть также определен как $\sgn(\sigma)=(-1)^m$, где m — количество транспозиций в разложении $\sigma$ в произведение транспозиций. Несмотря на то, что такое разложение не единственно, чётность количества транспозиций во всех разложениях $\sigma$ одна и та же, и поэтому знак перестановки корректно определён.

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

• Инволюция — перестановка $\tau,$ которая является обратной самой себе, то есть $\tau\cdot\tau=id.$
• Беспорядок — перестановка без неподвижных точек.
• Циклом длины $\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$ может быть записана в виде подстановки, например:

$\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.$

Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например:

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

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

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если k_i — количество элементов 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. Перестановки и факториалы

Литература

• Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0

Ссылки

• Аранжеман // Энциклопедический словарь Брокгауза и Ефрона: В 86 томах (82 т. и 4 доп.). — СПб., 1890—1907.