Обратная перестановка
Обратная перестановка в комбинаторике— это перестановка, которую вы получите, вставив позицию элемента в позицию, указанную значением элемента в числовом наборе. Если к числовому ряду применить обратную перестановку π, а потом обратную к ней π-1 то в итоге получится такой результат, как если бы мы эти перестановки не применяли вообще, данное правило помогает проверить правильность выполненной перестановки.
.В чем разница между перестановкой и обратной перестановкой
Из любой таблицы инверсий d1,d2,…dn можно однозначно восстановить перестановку, которая порождает данную таблицу, путем последовательного определения относительного расположения элементов n, n-1,….,1 (в этом порядке). Например перестановку, соответствующую таблице инверсий (2,3,6,4,0,2,2,1,0) = (d1,d2,d3,d4,d5,d6,d7,d8,d9), можно построить следующим образом: выпишем число 9, так как d8=1, то 8 стоит правее 9. Поскольку d7=2, то 7 стоит правее 8 и 9. Так как d6=2, то 6 стоит правее двух уже выписанных чисел, таким образом получается расположение чисел 9,8,6,7. Припишем теперь 5 слева, потому что d5=0, помещаем 4 вслед за четырьмя уже выписных числами, 3 после 6 выписанных чисел (т.е. в правый конец) и получаем 5,9,8,6,4,7,3. Вставив аналогичным образом 2 и 1, придем к перестановке (5,9,1,8,2,6,4,7,3).
Обратные перестановки
Не следует путать «инверсии» перестановок с обратными перестановками. Пусть a1,a2,….an — различные шары, индексы которых свяжем с номерами шаров. Тогда исходное расположение шаров однозначно определяется тождественной перестановкой (e=1,2,…n)
Обратной к перестановке называется перестановка которая получается, если в исходной перестановке поменять местами строки, а затем упорядочить столбцы в возрастающем порядке по верхним элементам, т.е. Ясно, что последовательное изменение порядка шаров согласно перестановкам и обратной приводит к исходному их расположению, т.е. к тождественной перестановке.