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

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

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

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

Термин «перестановка» возник потому, что сначала брались объекты, каким-то образом расставленные, а другие способы упорядочения требовали переставить эти объекты.

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

СвойстваПравить

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

$P_n=A_n^n=\frac{n!}{(n-<!--\; -\; -->n)!}=\frac{n!}{0!}=n!=1\cdot <!--\; \cdot \; -->2\cdot <!--\; \cdot \; -->\dots <!--\; \dots \; -->\cdot <!--\; \cdot \; -->n$$P_{n}=A_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!=1\cdot 2\cdot \ldots \cdot n$ .

Композиция определяет операцию произведения на перестановках одной длины: $(\mathrm{\pi <!--\; \pi \; -->}\cdot <!--\; \cdot \; -->\mathrm{\sigma <!--\; \sigma \; -->})(k)=\mathrm{\pi <!--\; \pi \; -->}(\mathrm{\sigma <!--\; \sigma \; -->}(k)).$$(\pi \cdot \sigma )(k)=\pi (\sigma (k)).$  Относительно этой операции множество перестановок из $n$$n$  элементов образует группу, которую называют симметрической и обычно обозначают $S_n$$S_{n}$ .

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

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

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

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

Инверсией в перестановке $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  называется всякая пара индексов $i,j$$i,\ j$  такая, что $1\leqslant i<j\leqslant n$  и $\mathrm{\pi <!--\; \pi \; -->}(i)>\mathrm{\pi <!--\; \pi \; -->}(j)$$\pi (i)>\pi (j)$ . Чётность числа инверсий в перестановке определяет чётность перестановки.

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

• Тождественная перестановка — перестановка $e,$$e,$  которая каждый элемент $x\in <!--\; \in \; -->X$$x\in X$  отображает в себя: $e(x)=x.$$e(x)=x.$ 
• Инволюция — перестановка $\mathrm{\tau <!--\; \tau \; -->},$$\tau ,$  которая является обратной самой себе, то есть $\mathrm{\tau <!--\; \tau \; -->}\cdot <!--\; \cdot \; -->\mathrm{\tau <!--\; \tau \; -->}=e.$$\tau \cdot \tau =e.$ 
• Беспорядок — перестановка без неподвижных точек.
• Циклом длины $\mathrm{\ell <!--\; \ell \; -->}$$\ell$  называется такая подстановка $\mathrm{\pi <!--\; \pi \; -->},$$\pi ,$  которая тождественна на всём множестве $X,$$X,$  кроме подмножества $\{x_1,x_2,\dots <!--\; \dots \; -->,x_{\mathrm{\ell <!--\; \ell \; -->}}\}\subset <!--\; \subset \; -->X$$\{x_{1},\;x_{2},\;\ldots ,\;x_{\ell }\}\subset X$  и $\mathrm{\pi <!--\; \pi \; -->}(x_{\mathrm{\ell <!--\; \ell \; -->}})=x_1,\mathrm{\pi <!--\; \pi \; -->}(x_i)=x_{i+1}.$$\pi (x_{\ell })=x_{1},\ \pi (x_{i})=x_{i+1}.$  Обозначается $(x_1,x_2,\dots <!--\; \dots \; -->,x_{\mathrm{\ell <!--\; \ell \; -->}}).$$(x_{1},\;x_{2},\;\ldots ,\;x_{\ell }).$ .
• Транспозиция — перестановка элементов множества $X$$X$ , которая меняет местами два элемента. Транспозиция является циклом длины 2.

ПодстановкаПравить

Перестановка $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  множества $X$$X$  может быть записана в виде подстановки, например:

${\begin{pmatrix}x_{1}&x_{2}&x_{3}&\ldots &x_{n}\\y_{1}&y_{2}&y_{3}&\ldots &y_{n}\end{pmatrix}},$ 

где $\{x_1,\dots <!--\; \dots \; -->,x_n\}=\{y_1,\dots <!--\; \dots \; -->,y_n\}=X$$\{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X$  и $\mathrm{\pi <!--\; \pi \; -->}(x_i)=y_i$$\pi (x_{i})=y_{i}$ .

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

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

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

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

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) транспозиций. При этом цикл длины 1 (являющийся по сути тождественной перестановкой $e$$e$ ) можно представить как пустое произведение^[en] транспозиций или, например, как квадрат любой транспозиции: $(1,2)(1,2)=(2,3)(2,3)=e.$$(1,\;2)(1,\;2)=(2,\;3)(2,\;3)=e.$  Цикл длины $\mathrm{\ell <!--\; \ell \; -->}⩾<!--\; ⩾\; -->2$$\ell \geqslant 2$  можно разложить в произведение $\mathrm{\ell <!--\; \ell \; -->}-<!--\; -\; -->1$$\ell -1$  транспозиций следующим образом:

$(x_1,\dots <!--\; \dots \; -->,x_l)=(x_1,x_{\mathrm{\ell <!--\; \ell \; -->}})(x_1,x_{\mathrm{\ell <!--\; \ell \; -->}-<!--\; -\; -->1})\dots <!--\; \dots \; -->(x_1,x_2).$$(x_{1},\;\ldots ,\;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).$$(1,\;2,\;3)=(1,\;3)(1,\;2)=(2,\;3)(1,\;3)=(1,\;3)(2,\;4)(2,\;4)(1,\;2).$ 

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

${\mathrm{\epsilon <!--\; \epsilon \; -->}}_{\mathrm{\pi <!--\; \pi \; -->}}=(-<!--\; -\; -->1{)}^t,$$\varepsilon _{\pi }=(-1)^{t},$ 

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

Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  из $n$$n$  элементов, состоящий из $k$$k$  циклов, равен

${\mathrm{\epsilon <!--\; \epsilon \; -->}}_{\mathrm{\pi <!--\; \pi \; -->}}=(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->k}$$\varepsilon _{\pi }=(-1)^{n-k}$ .

Знак перестановки $\mathrm{\pi <!--\; \pi \; -->}$$\pi$  также может быть определён через число инверсий $N(\mathrm{\pi <!--\; \pi \; -->})$$N(\pi )$  в $\mathrm{\pi <!--\; \pi \; -->}$$\pi$ :

${\mathrm{\epsilon <!--\; \epsilon \; -->}}_{\mathrm{\pi <!--\; \pi \; -->}}=(-<!--\; -\; -->1{)}^{N(\mathrm{\pi <!--\; \pi \; -->})}$$\varepsilon _{\pi }=(-1)^{N(\pi )}$ .

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

Рассмотрим $n$$n$  элементов $m$$m$  различных типов, причём в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются перестановками с повторением. Если $k_i$$k_i$  — число элементов $i$$i$ -го типа, то $k_1+k_2+\dots <!--\; \dots \; -->+k_m=n$$k_{1}+k_{2}+\ldots +k_{m}=n$  и число всевозможных перестановок с повторениями равно мультиномиальному коэффициенту $(\genfrac{}{}{0ex}{}{n}{k_1,k_2,\dots <!--\; \dots \; -->,k_m})=\frac{n!}{k_1!k_2!\dots <!--\; \dots \; -->k_m!}.$$\textstyle {\binom {n}{k_{1},\;k_{2},\;\ldots ,\;k_{m}}}={\frac {n!}{k_{1}!k_{2}!\ldots k_{m}!}}.$ 

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

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

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

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

Независимой случайной перестановкой называется такая случайная перестановка $\mathrm{\xi <!--\; \xi \; -->}$$\xi$ , для которой:

$P\{\mathrm{\xi <!--\; \xi \; -->}=\mathrm{\sigma <!--\; \sigma \; -->}\}=\frac{p_{1\mathrm{\sigma <!--\; \sigma \; -->}(1)}\dots <!--\; \dots \; -->p_{n\mathrm{\sigma <!--\; \sigma \; -->}(n)}}{\underset{\mathrm{\pi <!--\; \pi \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}{p}_{1\mathrm{\pi <!--\; \pi \; -->}(1)}\dots <!--\; \dots \; -->p_{n\mathrm{\pi <!--\; \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}},$  таких, что:

$\mathrm{\forall <!--\; \forall \; -->}i(1⩽<!--\; ⩽\; -->i⩽<!--\; ⩽\; -->n):<!--\; :\; -->p_{i1}+\dots <!--\; \dots \; -->+p_{in}=1$$\forall i\ (1\leqslant i\leqslant n)\colon p_{i1}+\ldots +p_{in}=1$ 

$\underset{\mathrm{\pi <!--\; \pi \; -->}\in <!--\; \in \; -->S_n}{\sum <!--\; \sum \; -->}{p}_{1\mathrm{\pi <!--\; \pi \; -->}(1)}\dots <!--\; \dots \; -->p_{n\mathrm{\pi <!--\; \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$ , то перестановку $\mathrm{\xi <!--\; \xi \; -->}$$\xi$  называют одинаково распределённой. Если же нет зависимости от $j$$j$ , то есть $\mathrm{\forall <!--\; \forall \; -->}i,j(1⩽<!--\; ⩽\; -->i,j⩽<!--\; ⩽\; -->n):<!--\; :\; -->p_{ij}=1/n,$$\forall i,\;j\ (1\leqslant i,\;j\leqslant n)\colon p_{ij}=1/n,$  то $\mathrm{\xi <!--\; \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.