1.14. Обратные перестановки

Не следует путать «инверсии» перестановок с обратными перестановками. Пусть различные шары, индексы которых свяжем с номерами шаров. Тогда исходное расположение шаров однозначно определяется тождественной перестановкой Пусть произвольная перестановка номеров где номер шара на месте. Такая перестановка отвечает расположению шаров Вспомним (см. п.1.5), что перестановка может быть записана в матричном виде. Данная

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

Обратной к перестановке называется перестановка которая получается, если в исходной перестановке поменять местами строки, а затем упорядочить столбцы в возрастающем порядке по верхним элементам, т.е. Ясно, что последовательное изменение порядка шаров согласно перестановкам и обратной приводит к исходному их расположению, т.е. к тождественной перестановке Например обратной к перестановке будет перестановка так как так как

Сортированную последовательность элементов перестановки можно получить, заполнив в цикле вектор

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

Результирующий вектор будет обратной перестановкой к

Х.А. Роте впервые установил связь между обратными перестановками и инверсиями: обратная перестановка содержит ровно столько же инверсий, сколько исходная.