Перестановка
В математике перестановка набора — это , грубо говоря, расположение его членов в последовательность или линейный порядок , или, если набор уже упорядочен, перестановка его элементов. Слово «перестановка» также относится к действию или процессу изменения линейного порядка упорядоченного множества. [1]
Перестановки отличаются от комбинаций , которые представляют собой выборки некоторых элементов множества независимо от порядка. Например, записанные в виде кортежей , существует шесть перестановок множества {1, 2, 3}, а именно (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) и (3, 2, 1). Это все возможные порядки этого набора из трех элементов. Анаграммы слов с разными буквами также являются перестановками: буквы уже упорядочены в исходном слове, а анаграмма представляет собой перестановку букв. Изучение перестановок конечных множеств — важная тема в области комбинаторики и теории групп .
Перестановки используются почти во всех разделах математики и во многих других областях науки. В информатике они используются для анализа алгоритмов сортировки ; в квантовой физике для описания состояний частиц; и в биологии , для описания последовательностей РНК .
Количество перестановок n различных объектов равно n факториалу , обычно записывается как n ! , что означает произведение всех положительных целых чисел, меньших или равных n .
Технически перестановка множества S определяется как биекция из S в себя. [2] [3] То есть это функция от S до S , для которой каждый элемент встречается ровно один раз в качестве значения изображения . Это связано с перестановкой элементов S , в которой каждый элемент s заменяется соответствующим f ( s ) . Например, упомянутая выше перестановка (3, 1, 2) описывается функцией, определенной как
Совокупность всех перестановок набора образует группу , называемую симметричной группой набора. Групповая операция — это композиция (выполнение двух заданных перестановок подряд), в результате которой получается еще одна перестановка. Поскольку свойства перестановок не зависят от природы элементов множества , при изучении перестановок часто рассматриваются перестановки множества.
