2.2.2. Группа подстановок

Пусть множество X состоит из n элементов , расположенных в произвольном, но фиксированном порядке.

Биекция называетсяподстановкой.

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

.

Обозначим - множество всех подстановок наA. Очевидно, что .

На множестве будем рассматривать операцию перемножения (композиции) подстановоки:

для любого .

Эта операция обладает свойствами:

1) - выполняется свойство ассоциативности;

2) существует подстановка , для которойдля каждого- выполняется аксиома существования единичного элемента;

3) для любого существуеттакое, что- выполняется аксиома существования обратного элемента.

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

,

.

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

Пример 1. Пусть .

Стационарный элемент . Подстановкаявляется циклом длиныи может быть записана в виде.

Пример 2. Пусть .

Подстановка p не является циклом, но может быть представлена в виде композиции двух циклов:

причем эти циклы являются непересекающимися, т.е. не имеют общих нестационарных элементов.

Теорема 1. Любая подстановка может быть представлена в виде композиции непересекающихся циклов длины:

.

Доказательство теоремы дает процедуру построения циклов.

Найдем в A наименьший нестационарный относительно элемент, т.е.и для каждоговыполняется условие: если, то. (Если такого элемента не существует, тоявляется тождественной подстановкой () и ее можно рассматривать как пустое произведение циклов).

Будем строить образы элемента ,до тех пор, пока не получимпри наименьшем из возможныхk (). Тогда подстановка

определяет цикл длины k внутри подстановки . Если все нестационарные элементы подстановкисодержатся в, то. В противном случае найдем- наименьший из нестационарных элементов подстановки, не входящий в цикл. Строим цикл

.

Очевидно, что и- непересекающиеся. Если все нестационарные элементы исчерпаны, то, в противном случае повторяем процесс, пока каждый нестационарный элемент не войдет в какой-либо цикл. В конечном итоге получим.

Пример. Представить в виде композиции циклов подстановку

.

, значит ;

,значит;

- стационарный элемент.

Следовательно, .

Определение. Порядком подстановки называется наименьшее натуральное числоp такое, что .

Теорема 2. Порядок подстановки равен наименьшему общему кратному порядков циклов в ее разложении на непересекающиеся циклы.

В качестве упражнения предлагается провести доказательство теоремы самостоятельно.