88.147.198.247 в 04:22, 21 августа 2025

2025-08-21T04:22:50Z

Новая страница

[[Файл:Permutations RGB.svg|thumb|180px|6 перестановок трёх шаров; <math>6=1\cdot 2\cdot 3=3!</math>]]
В [[комбинаторика|комбинаторике]] '''перестано́вкой''' заданного [[Множество|конечного множества]] <math>X = \{a_1, a_2, \ldots, a_n\}</math> (все элементы <math>X</math> различны) называется произвольный [[Кортеж (математика)|упорядоченный набор]] всех элементов <math>X</math> (без повторений). Группируя эти элементы в разном порядке, можно получить различные перестановки. Всего из множества с <math>n</math> элементами можно получить <math>n! = 1\cdot 2\cdot 3 \cdot \ldots \cdot n</math> (<math>n</math>-[[факториал]]) различных перестановок (см. рисунок)<ref name=VYG>{{книга |автор=[[Выгодский, Марк Яковлевич|Выгодский М. Я.]] |место=М. |издательство=АСТ |год=2006 |заглавие=Справочник по элементарной математике |страницы=293—294 |страниц=509 |isbn=5-17-009554-6}}</ref><ref>{{книга|заглавие=Популярная комбинаторика|автор=Виленкин Н.Я.|место=М.|издательство=Наука|год=1975|часть=Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями|страниц=208|ссылка=http://www.math.ru/lib/book/djvu/combinatorika.djvu|страницы=80|archive-date=2010-10-14|archive-url=https://web.archive.org/web/20101014225249/http://math.ru/lib/book/djvu/combinatorika.djvu}}</ref>.

Перестановка является частным случаем [[Размещение|размещения]], когда выбираются все элементы множества<ref name=VYG/>.

== Подстановка ==
Перестановку можно рассматривать как функцию, которая каждому элементу некоторой начальной перестановки сопоставляет соответствующий по номеру элемент данной перестановки. Такую функцию часто называют '''подстановкой'''{{sfn |Математическая энциклопедия|1984}}. Перестановка <math>\pi</math> множества <math>X</math> может быть наглядно представлена в виде таблицы:
: <math>\begin{pmatrix}
x_1 & x_2 & x_3 & \ldots & x_n \\
y_1 & y_2 & y_3 & \ldots & y_n\end{pmatrix},</math>
где <math>\{x_1,\;\ldots,\;x_n\} = \{y_1,\;\ldots,\;y_n\} = X</math> и <math>\pi(x_i)=y_i</math>.

'''Пример''': перестановка элементов множества <math>X</math> в обратном порядке:
: <math>\begin{pmatrix}
x_1 & x_2 & x_3 & \ldots & x_n \\
x_n & x_{n-1} & x_{n-2} & \ldots & x_1\end{pmatrix},</math>

'''''Инверсией''''' в перестановке <math>\pi</math> называется всякая пара индексов <math>i,\ j</math> такая, что <math>1\leqslant i<j\leqslant n</math> и <math>\pi(i)>\pi(j)</math>. Чётность числа инверсий в перестановке определяет '''чётность перестановки'''. Пример:
: <math>\begin{pmatrix}
1 & 2 & 3 \\
1 & 3 & 2\end{pmatrix},</math>
Здесь элементы 2 и 3 образуют инверсию.

== Связанные определения ==
'''''Носитель перестановки''''' <math>\pi\colon X\to X</math> — это подмножество множества <math>X</math>, определяемое как <math>\operatorname{supp}(\pi):=\{x\in X\mid\pi(x)\ne x\}.</math>

'''''Неподвижной точкой''''' перестановки <math>\pi</math> является всякая [[неподвижная точка]] отображения <math>\pi\colon X\to X</math>, то есть элемент множества <math>\{x\in X\mid\pi(x)=x\}.</math> Множество всех неподвижных точек перестановки <math>\pi</math> является [[дополнение (теория множеств)|дополнением]] её носителя в <math>X</math>.

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

=== Произведения циклов и знак перестановки ===
Перестановку <math>\pi</math> можно представить в виде ориентированного графа, где вершинами являются элементы конечного множества, а связи между вершинами описывают переход. В случае, <math>\pi(i) = i</math>, для <math>i</math> элемента рисуется петля. Таким образом, получается граф, где из каждой вершины выходит и входит одно ребро. Пример перестановки представленной в виде ориентированного графа можно увидеть на изображении справа.
[[Файл:Пример перестановки, представленной в виде орграфа.png|мини|Пример перестановки, представленной в виде ориентированного графа]]

Таким образом, любая перестановка <math>\pi</math> может быть разложена в произведение ([[Композиция функций|композицию]]) ''непересекающихся циклов'' длины <math>\ell \geqslant 2</math>, причём единственным образом с точностью до порядка следования циклов в произведении. Например:
: <math>\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 \\
5 & 1 & 6 & 4 & 2 & 3\end{pmatrix} = (1,\;5,\;2)(3,\;6).</math>

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

Любой цикл может быть разложен в произведение (не обязательно непересекающихся) [[Транспозиция (математика)|транспозиций]]. При этом цикл длины 1 (являющийся по сути тождественной перестановкой <math>e</math>) можно представить как {{нп5|пустое произведение|||Empty product}} транспозиций или, например, как квадрат любой транспозиции: <math>(1,\;2)(1,\;2) = (2,\;3)(2,\;3) = e.</math> Цикл длины <math>\ell \geqslant 2</math> можно разложить в произведение <math>\ell-1</math> транспозиций следующим образом:
: <math>(x_1,\;\ldots,\;x_l) = (x_1,\;x_{\ell})(x_1,\;x_{\ell-1})\dots (x_1,\;x_2).</math>
Разложение циклов на произведение транспозиций не является единственным:
: <math>(1,\;2,\;3) = (1,\;3)(1,\;2) = (2,\;3)(1,\;3) = (1,\;3)(2,\;4)(2,\;4)(1,\;2).</math>

{{якорь|Чётность}}
Таким образом, любая перестановка может быть разложена в произведение транспозиций. Хотя это можно сделать многими способами, [[Чётные и нечётные числа|чётность]] числа транспозиций во всех таких разложениях одинакова. Это позволяет определить ''знак перестановки'' (''чётность перестановки,'' или ''сигнатуру перестановки'') <math>\pi</math> как:
: <math>\varepsilon_{\pi} = (-1)^t,</math>
где <math>t</math> — число транспозиций в каком-то разложении <math>\pi</math>. При этом <math>\pi</math> называют ''чётной перестановкой'', если <math>\varepsilon_{\pi} = 1</math>, и ''нечётной перестановкой'', если <math>\varepsilon_{\pi} = -1</math>.

Эквивалентно, знак перестановки определяется её цикловой структурой: знак перестановки <math>\pi</math> из <math>n</math> элементов, состоящий из <math>k</math> циклов, равен
: <math>\varepsilon_{\pi} = (-1)^{n-k}</math>.

Знак перестановки <math>\pi</math> также может быть определён через число ''инверсий'' <math>N(\pi)</math> в <math>\pi</math>:
: <math>\varepsilon_{\pi} = (-1)^{N(\pi)}</math>.

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

[[Композиция функций|Композиция]] определяет операцию произведения на перестановках одной длины: <math>(\pi\cdot\sigma)(k) = \pi(\sigma(k)).</math> Относительно этой операции множество перестановок из <math>n</math> элементов образует [[группа (математика)|группу]], которую называют [[симметрическая группа|симметрической]] и обычно обозначают <math>S_n</math>.

Любая [[конечная группа]] порядка <math>n</math> [[Изоморфизм групп|изоморфна]] некоторой подгруппе [[Симметрическая группа|симметрической группы]] <math>S_n</math> ([[Теорема Кэли (теория групп)|теорема Кэли]]). При этом каждая пара элементов <math>a,b \in G</math> сопоставляется с парой перестановок <math>\pi_a, \pi_b</math>, задаваемых на элементах <math>G</math> тождествами <math>\pi_a(g)=\pi_b, a \circ g = b,</math> где <math>\circ</math> — групповая операция в <math>G</math>.

=== Перестановки с повторением ===
Рассмотрим <math>n</math> элементов <math>m</math> различных типов, причём в каждом типе все элементы одинаковы. Тогда перестановки из всех этих элементов с точностью до порядка следования однотипных элементов называются ''перестановками с повторением''.
Если <math>k_i</math> — число элементов <math>i</math>-го типа, то <math>k_1+k_2+\ldots+k_m=n</math> и число всевозможных перестановок с повторениями равно [[мультиномиальный коэффициент|мультиномиальному коэффициенту]] <math>\textstyle \binom{n}{k_1,\;k_2,\;\ldots,\;k_m} = \frac{n!}{k_1!k_2!\ldots k_m!}.</math>

Перестановку с повторениями можно также рассматривать как перестановку [[Мультимножество|мультимножества]] <math>\{ 1^{k_1},\;2^{k_2},\;\ldots,\;m^{k_m} \}</math> мощности <math>k_1+k_2+\ldots+k_m=n</math>.

=== Случайная перестановка ===
{{main|Случайные перестановки}}

''Случайной перестановкой'' называется [[Случайная величина|случайный вектор]] <math>\xi=(\xi_1,\;\ldots,\;\xi_n),</math> все элементы которого принимают натуральные значения от 1 до <math>n,</math> и при этом [[вероятность]] совпадения любых двух элементов равна 0.

''Независимой случайной перестановкой'' называется такая случайная перестановка <math>\xi</math>, для которой:
: <math>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>p_{ij},</math> таких, что:
: <math>\forall i\ (1\leqslant i \leqslant n)\colon p_{i1}+\ldots + p_{in}=1</math>
: <math>\sum\limits_{\pi \in S_n}p_{1\pi(1)}\ldots p_{n\pi(n)}>0.</math>

Если при этом <math>p_{ij}</math> не зависят от <math>i</math>, то перестановку <math>\xi</math> называют ''одинаково распределённой''. Если же нет зависимости от <math>j</math>, то есть <math>\forall i,\;j\ (1\leqslant i,\;j \leqslant n)\colon p_{ij}=1/n,</math> то <math>\xi</math> называют ''однородной''.

== См. также ==
{{навигация|Викисловарь=перестановка}}{{колонки}}
* [[Алгоритм Нарайаны]]
* [[Анаграмма]]
* [[Гигантская компонента]]
* [[Размещение]]
* [[Симметрическая группа]]
* [[Сочетание]]
{{колонки|конец}}

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|подзаголовок
|заглавие=Искусство программирования, том 3. Сортировка и поиск
|оригинал=The Art of Computer Programming, vol.3. Sorting and Searching
|ссылка=
|автор=[[Дональд Кнут]]
|издание = 2-е изд
|год=2007
|место=М.
|издательство= [[Вильямс (издательство)|«Вильямс»]]
|страниц= 824
|isbn= 0-201-89685-0
}}
* {{книга
|автор = [[Кострикин, Алексей Иванович|Кострикин А. И.]]
|заглавие = Введение в алгебру. Основы алгебры
|ссылка = https://archive.org/details/isbn_5020146447
|издание =
|место = {{М}}
|издательство = [[Физматлит]]
|год = 1994
|страницы = [https://archive.org/details/isbn_5020146447/page/n58 59]-71
|страниц = 320
|isbn = 5-02-014644-7
}}
* {{книга |часть=Перестановка |столбцы=256 |заглавие=Математическая энциклопедия (в 5 томах)
|место=М. |страниц=1216 |том=4 |год=1984 |ref=Математическая энциклопедия
|издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]]}}
* {{книга
|заглавие = Delphi и Turbo Pascal на занимательных примерах
|часть = Перестановки, сочетания, размещения: вывод всех перестановок
|ссылка часть = http://www.iqfun.ru/articles/perestanovki.shtml
|автор = Сергей Мельников
|издательство = БХВ-Петербург
|isbn = 978-5-94157-886-3
|год = 2012
|страниц = 448
}}

== Ссылки ==
* {{ВТ-ЭСБЕ|Аранжеман}}
{{вс}}

[[Категория:Перестановки]]
[[Категория:Комбинаторика]]
[[Категория:Теория групп]]

Перестановка - История изменений

88.147.198.247 в 04:22, 21 августа 2025