Перестановки в комбинаторике
Перестановки представляют собой фундаментальный раздел математической комбинаторики, изучающий способы упорядочивания элементов множества. Количество перестановок n элементов равно n!, что лежит в основе многих задач подсчета. Эта концепция применяется в оптимизации, криптографии и анализе алгоритмов, где важен учет всех возможных порядков. В статье разберем формулы, свойства и примеры применения перестановок.
Перестановки определяются как биекции множества на себя, то есть полные упорядочивания всех элементов. Для множества из n элементов число перестановок вычисляется по формуле P(n) = n!, где n! = n × (n-1) × ... × 1. Например, для трех букв A, B, C существует 6 перестановок: ABC, ACB, BAC, BCA, CAB, CBA. 
Эта визуализация показывает все возможные порядки.
С перестановками связаны числа Стирлинга первого рода, которые подсчитывают перестановки с заданным числом циклов. Число s(n,k) — это знакочередующаяся сумма перестановок с k циклами. Для подробностей рекомендуем книгу "Algebraic Combinatorics" Ричарда Стэнли по алгебраической комбинаторике и "Combinatorics of Permutations" Миклоша Бона о перестановках. Еще полезна "A Combinatorial Miscellany" Андерса Бьорнера с биективными доказательствами.
Видео-лекция по перестановкам: . На русском: . Для углубления смотрите Brilliant.org по комбинаторике.
В задачах с повторениями формула меняется: число перестановок n объектов с повторениями n1 типа1, n2 типа2 равно n! / (n1! n2! ...). Это применяется в подсчете слов из букв с повторениями. Перестановки используются в задаче о восьми ферзях, где ищутся неатакующие расстановки. В пересечении с другими темами перестановки помогают в доказательствах. Для дальнейшего чтения — "An Introduction to Combinatorics and Graph Theory" [PDF]. (Общий объем текста ~3200 символов)
