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

---

В комбинаторике перестано́вкой заданного конечного множества ${\displaystyle X=\{a_{1},a_{2},\ldots ,a_{n}\}}$ (все элементы ${\displaystyle X}$ различны) называется произвольный упорядоченный набор всех элементов ${\displaystyle X}$ (без повторений). Группируя эти элементы в разном порядке, можно получить различные перестановки. Всего из множества с ${\displaystyle n}$ элементами можно получить ${\displaystyle n!=1\cdot 2\cdot 3\cdot \ldots \cdot n}$ (${\displaystyle n}$-факториал) различных перестановок (см. рисунок)^[1][2].

Перестановку можно рассматривать как функцию, которая каждому элементу некоторой начальной перестановки сопоставляет соответствующий по номеру элемент данной перестановки. Такую функцию часто называют подстановкой^[3]. Перестановка ${\displaystyle \pi }$ множества ${\displaystyle X}$ может быть наглядно представлена в виде таблицы:

где ${\displaystyle \{x_{1},\;\ldots ,\;x_{n}\}=\{y_{1},\;\ldots ,\;y_{n}\}=X}$ и ${\displaystyle \pi (x_{i})=y_{i}}$.

Пример: перестановка элементов множества ${\displaystyle X}$ в обратном порядке:

---