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

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

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

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

Свойства

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

$P_{n}=A_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!=1\cdot 2\cdot \dots \cdot 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)).$$(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$ Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают $S_{n}$$S_{n}$.
• Любая конечная группа порядка n изоморфна некоторой подгруппе группы перестановок из n чисел (теорема Кэли). При этом каждый элемент $a\in G$$a\in G$ сопоставляется с перестановкой $\pi _{a}$$\pi _{a}$, задаваемой тождеством $\pi _{a}(g)=a\circ g,$$\pi _{a}(g)=a\circ g,$ где g — произвольный элемент группы G, а $\circ$$\circ$ — групповая операция.

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

• Носитель перестановки $\pi \colon X\to X$$\pi \colon X\to X$ — это подмножество множества $X$$X$, определяемое как $\operatorname {supp} (\pi )=\{x\in X\mid \pi (x)\neq x\}.$$\operatorname {supp}(\pi )=\{x\in X\mid \pi (x)\neq x\}.$
• Неподвижной точкой перестановки $\pi$$\pi$ является всякая неподвижная точка отображения $\pi \colon X\to X$$\pi \colon X\to X$, то есть элемент множества $\{x\in X\mid \pi (x)=x\}.$$\{x\in X\mid \pi (x)=x\}.$ Множество всех неподвижных точек перестановки $\pi$$\pi$ является дополнением её носителя в $X$$X$.
• Инверсией в перестановке $\pi$$\pi$ порядка n называется всякая пара индексов $i,j$$i,j$ такая, что $1\leqslant i<j\leqslant n$$1\leqslant i<j\leqslant n$ и $\pi (i)>\pi (j)$$\pi (i)>\pi (j)$. Чётность числа инверсий в перестановке определяет чётность перестановки.

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

• Тождественная перестановка — перестановка $e,$$e,$ которая каждый элемент $x\in X$$x\in X$ отображает в себя: $e(x)=x.$$e(x)=x.$
• Инволюция — перестановка $\tau ,$$\tau ,$ которая является обратной самой себе, то есть $\tau \cdot \tau =e.$$\tau \cdot \tau =e.$
• Беспорядок — перестановка без неподвижных точек.
• Циклом длины $\ell$$\ell$ называется такая подстановка $\pi ,$$\pi ,$ которая тождественна на всём множестве $X,$$X,$ кроме подмножества $\{x_{1},x_{2},\dots ,x_{\ell }\}\subset X$$\{x_{1},x_{2},\dots ,x_{\ell }\}\subset X$ и $\pi (x_{\ell })=x_{1},\pi (x_{i})=x_{i+1}.$$\pi (x_{\ell })=x_{1},\pi (x_{i})=x_{{i+1}}.$ Обозначается $(x_{1},x_{2},\dots ,x_{\ell }).$$(x_{1},x_{2},\dots ,x_{\ell }).$. Число перестановок, содержащих k циклов, — есть числа Стирлинга первого рода
• Транспозиция — перестановка элементов множества $X$$X$, которая меняет местами два элемента. Транспозиция является циклом длины 2.

Подстановка

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

${\begin{pmatrix}x_{1}&x_{2}&x_{3}&\dots &x_{n}\\y_{1}&y_{2}&y_{3}&\dots &y_{n}\end{pmatrix}},$${\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$$\{x_{1},\dots ,x_{n}\}=\{y_{1},\dots ,y_{n}\}=X$ и $\pi (x_{i})=y_{i}.$$\pi (x_{i})=y_{i}.$

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

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

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

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. Для произвольного цикла длины $l\geqslant 2$$l\geqslant 2$ разложение можно написать так: $(x_{1},\dots ,x_{l})=(x_{1},x_{l})(x_{1},x_{l-1})\dots (x_{1},x_{2}).$$(x_{1},\dots ,x_{l})=(x_{1},x_{l})(x_{1},x_{{l-1}})\dots (x_{1},x_{2}).$ Циклы длины 1 действуют как тождественная перестановка и тоже могут быть легко разложены, так как квадрат любой транспозиции есть тождественная перестановка: $(1,2)(1,2)=(2,3)(2,3)=e.$$(1,2)(1,2)=(2,3)(2,3)=e.$ Такое разложение циклов на произведение транспозиций не будет единственным: $(1,2,3)=(1,3)(1,2)=(2,3)(1,3)=(1,3)(2,4)(2,4)(1,2).$$(1,2,3)=(1,3)(1,2)=(2,3)(1,3)=(1,3)(2,4)(2,4)(1,2).$

Таким образом любая перестановка может быть разложена в произведение транспозиций. Хотя это разложение и не будет единственным, но чётность числа транспозиций, входящих в разложение, сохраняется. Пусть перестановка $\pi$$\pi$ разложена в произведение $k$$k$ транспозиций, тогда знаком перестановки (иначе: чётностью перестановки или сигнатурой перестановки) $\pi$$\pi$ называют число $\varepsilon _{\pi }=(-1)^{k},$$\varepsilon _{{\pi }}=(-1)^{k},$ при этом $\pi$$\pi$ называют чётной перестановкой, если $\varepsilon _{\pi }=1,$$\varepsilon _{{\pi }}=1,$ и нечётной перестановкой, если $\varepsilon _{\pi }=-1.$$\varepsilon _{{\pi }}=-1.$

Знак перестановки $\pi$$\pi$ также может быть определен через число инверсий $N(\pi )$$N(\pi )$ в этой перестановке: $\varepsilon _{\pi }=(-1)^{N(\pi )}.$$\varepsilon _{{\pi }}=(-1)^{{N(\pi )}}.$

Замечание. Имеется два соглашения по умножению перестановок и циклов:

1) $(\sigma \circ \tau )(i)=\sigma (\tau (i))$$(\sigma \circ \tau )(i)=\sigma (\tau (i))$.

Например: $(12)(23)=(123)$$(12)(23)=(123)$.

2) $(i)(\sigma \circ \tau )=((i)\sigma )\tau$$(i)(\sigma \circ \tau )=((i)\sigma )\tau$.

Например: $(12)(23)=(132)$$(12)(23)=(132)$.

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

Рассмотрим n элементов m различных типов, причем в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если k_i — количество элементов i-го типа, то $k_{1}+k_{2}+\dots +k_{m}=n$$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}!}}.$$\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}),$$\xi =(\xi _{1},\ldots ,\xi _{n}),$ все элементы которого принимают натуральные значения от 1 до $n,$$n,$ и при этом вероятность совпадения любых двух элементов равна 0.

Независимой случайной перестановкой называется такая случайная перестановка $\xi$$\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\{\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},$$p_{{ij}},$ таких что

$\forall i(1\leqslant i\leqslant n):p_{i1}+\ldots +p_{in}=1$$\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.$$\sum \limits _{{\pi \in S_{n}}}p_{{1\pi (1)}}\ldots p_{{n\pi (n)}}>0.$

Если при этом $p_{ij}$$p_{{ij}}$ не зависят от $i$$i$, то перестановку $\xi$$\xi$ называют одинаково распределённой. Если же нет зависимости от $j$$j$, то есть $\scriptstyle \forall i,j(1\leq i,j\leq n):p_{ij}=1/n,$$\scriptstyle \forall i,j(1\leq i,j\leq n):p_{{ij}}=1/n,$ то $\xi$$\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.