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

Перестановка — в комбинаторике конечного множества — любое упорядоченное расположение всех его элементов, при котором каждый элемент встречается ровно один раз. В более широком смысле перестановкой называют также сам процесс изменения порядка следования элементов. Перестановки являются фундаментальным объектом комбинаторики и теории групп, а также находят применение в теории вероятностей, статистике, криптографии, алгоритмах сортировки и многих других областях математики и информатики.

Определение и основные понятия

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

Например, для множества из трёх элементов \(\{a, b, c\}\) существует шесть различных перестановок: \(abc, acb, bac, bca, cab, cba\).

Количество различных перестановок из \(n\) элементов обозначается \(P_n\) (от французского permutation) и вычисляется по формуле: \[ P_n = n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n \] где \(n!\) — факториал числа \(n\). По определению, \(0! = 1\) (существует ровно одна перестановка пустого множества).

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

Если в множестве имеются одинаковые (неразличимые) элементы, то говорят о перестановках с повторениями. Пусть имеется \(n\) элементов, среди которых есть \(n_1\) элементов первого типа, \(n_2\) — второго, …, \(n_k\) — \(k\)-го типа, причём \(n_1 + n_2 + \ldots + n_k = n\). Количество различных перестановок с повторениями вычисляется по формуле: \[ P_n(n_1, n_2, \ldots, n_k) = \frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!} \]

Пример: сколько различных слов можно составить из букв слова «МАТЕМАТИКА»? В слове 10 букв: М — 2, А — 3, Т — 2, Е — 1, И — 1, К — 1. Количество перестановок: \(\frac{10!}{2! \cdot 3! \cdot 2! \cdot 1! \cdot 1! \cdot 1!} = 151200\).

История

Понятие перестановки известно с древности. Первые систематические исследования перестановок связывают с индийскими математиками, которые в VI веке н. э. рассматривали задачи о подсчёте числа возможных комбинаций в музыке и стихосложении. В европейской математике перестановки начали изучать в эпоху Возрождения. В 1654 году Блез Паскаль и Пьер Ферма в переписке по вопросам теории вероятностей заложили основы комбинаторики, включая правило подсчёта числа перестановок. Термин «перестановка» (лат. permutatio) ввёл в математический обиход Якоб Бернулли в своей книге «Искусство предположений» (1713). В XVIII—XIX веках теория перестановок развивалась в работах Леонарда Эйлера, Жозефа Луи Лагранжа, Огюстена Луи Коши и Эвариста Галуа, который связал перестановки с теорией групп, что привело к созданию абстрактной алгебры.

Способы задания перестановок

Перестановку можно задать несколькими способами.

Табличная запись

Перестановка \(\sigma\) на множестве \(\{1, 2, \ldots, n\}\) записывается в виде двух строк: в верхней строке указываются исходные позиции, в нижней — соответствующие им новые позиции после перестановки: \[ \sigma = \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(n) \end{pmatrix} \]

Циклическая запись

Перестановка может быть представлена как произведение независимых циклов. Цикл \((a_1 \, a_2 \, \ldots \, a_k)\) означает, что элемент \(a_1\) переходит в \(a_2\), \(a_2\) — в \(a_3\), …, \(a_k\) — в \(a_1\). Например, перестановка \(\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}\) в циклической записи имеет вид \((1\,2)(3\,4)\).

Графическое представление

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

Свойства и классификация

Чётность перестановки

Каждая перестановка может быть разложена в произведение транспозиций — перестановок, меняющих местами два элемента. Количество транспозиций в разложении не является постоянным, но его чётность всегда одинакова для данной перестановки. Перестановка называется чётной, если она раскладывается в чётное число транспозиций, и нечётной — в противном случае. Знак перестановки \(\operatorname{sgn}(\sigma)\) равен \(+1\) для чётной и \(-1\) для нечётной перестановки. Чётность перестановки играет важную роль в теории определителей матриц.

Группа перестановок

Множество всех перестановок из \(n\) элементов с операцией композиции (последовательного применения) образует группу, называемую симметрической группой \(S_n\). Порядок этой группы равен \(n!\). Группа \(S_n\) является одной из важнейших в теории групп: любая конечная группа изоморфна некоторой подгруппе симметрической группы (теорема Кэли).

Инверсии и порядок

Инверсией в перестановке называется пара элементов, расположенных в порядке, обратном их естественному порядку (например, в числовой перестановке \(3, 1, 2\) инверсиями являются пары \((3,1)\) и \((3,2)\)). Число инверсий определяет чётность перестановки: чётное число инверсий соответствует чётной перестановке, нечётное — нечётной.

Применение

Криптография

Перестановки используются в шифрах перестановки, где символы открытого текста меняются местами по определённому правилу. Примером является шифр «Скитала» (Древняя Греция), где текст записывался на полоску, намотанную на цилиндр, а затем читался после разматывания. Современные блочные шифры (например, AES) используют перестановки битов и байтов как часть алгоритма.

Алгоритмы сортировки

Многие алгоритмы сортировки (пузырьковая, быстрая, сортировка слиянием) основаны на перестановках элементов массива для достижения упорядоченного состояния. Количество перестановок, необходимых для сортировки, является мерой эффективности алгоритма.

Теория вероятностей и статистика

Перестановки лежат в основе подсчёта вероятностей в задачах, где порядок важен. Например, вероятность того, что в случайной перестановке из \(n\) элементов ни один элемент не останется на своём месте (задача о беспорядках), стремится к \(1/e\) при \(n \to \infty\).

Комбинаторные задачи

Перестановки используются для решения задач о рассадке, составлении расписаний, генетических алгоритмах, а также в комбинаторной оптимизации (задача коммивояжёра).

Математический анализ и линейная алгебра

В определении определителя матрицы используется знак перестановки: \(\det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}\). Перестановки также применяются в теории симметрических многочленов и при изучении групп преобразований.

Интересные факты

• Число перестановок из 10 элементов (\(10! = 3\,628\,800\)) примерно равно числу секунд в 42 днях.
• Задача о беспорядках (субфакториал) — количество перестановок, в которых ни один элемент не стоит на своём месте, обозначается \(!n\) и вычисляется как \(!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}\).
• В теории групп перестановок известна теорема Кэли: любая конечная группа изоморфна подгруппе некоторой симметрической группы.
• Перестановки активно используются в криптоанализе: например, для взлома шифра простой перестановки применяется частотный анализ и метод «грубой силы» при малых \(n\).
• В русском языке термин «перестановка» в комбинаторном смысле ввёл в употребление математик Пафнутий Чебышёв в XIX веке.