Свойства перестановок.

С в о й с т в о 1. Если в перестановке поменять местами любые два элемента, то ее четность изменится.

Д о к а з а т е л ь с т в о.

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

Рассмотрим случай не соседних элементов.

Пусть перестановка имеет вид . Поменяем местами . Получим перестановку . Для того, чтобы из перестановки получить перестановку , переставим в элемент на место между .Для этого нужно сделать перестановку. После этого переместим элемент на место , для чего нужно сделать . Так как при перестановке соседних элементов четность меняется, то всего перемен четности будет , т.е. четность перестановки поменяется.

С в о й с т в о 2. Для число четных и нечетных перестановок для множества равно.

Д о к а з а т е л ь с т в о.

Очевидно, что каждой четной перестановке соответствует нечетная перестановка и наоборот. Следовательно, тех и других одинаковое число.

Пример. Подобрать числа так, чтобы перестановка была четной.

Так как перестановка шестого порядка, то могут принимать значения или 2, или 6.

В случае получаем перестановку . Подсчитаем число инверсий в ней , т.е. имеем нечетную перестановку.

Остается рассмотреть случай . Тогда получаем перестановку , .

Число инверсий в можно было бы не подсчитывать, а воспользоваться тем, что из нечетности сразу следует четность перестановки в соответствии со свойством 1 .

Пример. Какое максимальное число инверсий может быть в перестановке?

Пример. В перестановке имеется инверсий. Определить число инверсий в перестановке .