E) Транспозиции
Рассмотрим теперь перестановки и подстановки специального вида – транспозиции.
Если в некоторой перестановке поменять местами какие-либо два элемента (но не обязательно стоящие рядом), а все остальные элементы оставить на месте, то получим, очевидно, новую перестановку. Такое преобразование перестановки называется транспозицией.
Подстановка, получающаяся из тождественной подстановки E при помощи одной транспозиции, производимой в её нижней строке, также называется транспозицией. Такие подстановки нечётны и имеют вид
,
(2.22)
где многоточиями заменены элементы, остающиеся на месте. Условимся обозначать эту транспозицию символом (i, j). Например, транспозицию
кратко
записывают так:
.
Применение транспозиции элементов i
и j
к нижней строке произвольной подстановки
A
равносильно умножению подстановки A
справа на подстановку (2.22), т.е. на (i,
j).
Предложение 2. Любая перестановка может быть получена из любой другой посредством нескольких транспозиций.
Применим
метод математической индукции. Для n=2
утверждение тривиально. Пусть n>2
и для перестановок n–1
элементов утверждение теоремы
справедливо. Пусть
и
– две данные перестановки. Если
,
то
и
отличаются только порядком и, в силу
индукционного предположения, посредством
нескольких транспозиций можно перейти
от
к
и, следовательно, от
к
.
Пусть
теперь
.
Тогда
при некотором i1.
Сделав в
транспозицию
,
мы придём к новой перестановке, у которой
на первом месте находится
.
В силу доказанного эта перестановка
превращается в
посредством нескольких транспозиций.
Следовательно, от
к
можно перейти посредством нескольких
транспозиций, что и требовалось доказать.
Следствие. Всякая подстановка представима в виде произведения нескольких транспозиций.
Всякую подстановку можно многими разными способами разложить в произведение транспозиций. Всегда можно, например, добавить два одинаковых множителя вида (i,j)(j,i), которые дают в произведении подстановку E, т.е. взаимно уничтожаются. Укажем менее тривиальный пример:
.
Предложение 3. Всякая транспозиция меняет чётность перестановки.
Для
доказательства этой важной теоремы
рассмотрим сначала случай, когда
транспонируемые элементы i
и j
стоят рядом, т.е. перестановка имеет
вид
,
где буквой A
обозначена группа элементов, находящихся
влево от i,
буквой B
обозначена группа элементов, находящихся
вправо от j.
После транспозиции (i,j)
получится перестановка
.
Понятно, что в обеих перестановках
каждый из элементов i
и j
составляет одни и те же инверсии с
элементами группы A
и B.
Если элементы i
и j
раньше не составляли инверсии, то в
новой перестановке появляется одна
новая инверсия, т.е. число инверсий
увеличивается на единицу; если же они
раньше составляли инверсию, то теперь
она пропадает, т.е. число инверсий на
единицу уменьшается. В обоих случаях
чётность перестановки меняется.
Пуст теперь между транспонируемыми элементами i и j расположено s элементов, т.е. перестановка имеет вид
.
(2.23)
Обозначим
через p
количество тех чисел
,
которые находились в инверсии с i,
и через q
количество тех элементов
,
которые находятся в инверсии с j.
После транспозиции (i,j)
перестановка (2.23) превратится в
.
(2.24)
Очевидно, что те элементы , которые находились в инверсии с i, уже не будут давать с i инверсию. Зато остальные s–p элементов из после транспозиции будут находиться в инверсии с i. Т.о., после транспозиции количество инверсий, возникающих среди относительно i, уменьшится на p и возрастёт на s–p, т.е. в общей сложности возрастёт на s–p–p=s–2p. Точно так же количество инверсий, возникающих среди относительно j, после транспозиции возрастёт на s–2q. Наконец, после транспозиции происходит либо потеря, либо возникновение инверсии между i и j. Отсюда в перестановке (2.23) количество инверсий после транспозиции (i,j) возрастёт на
,
т.е. изменится на нечётное число. Т.о., класс перестановок (2.23) должен быть противоположен классу перестановки (2.24).