4. К теории подстановок.

Как уже говорилось, подстановками называются взаимно однозначные отображения на себя конечных множеств. Будем считать, что — множество, на котором действуют подстановки. Пусть а — некоторая подстановка и — циклическая группа, порожденная подстановкой а. Множество переставляемых элементов разбивается на орбиты, и подстановка вполне определяется тем, как она действует на каждой орбите.

Пусть — один из переставляемых элементов. Обозначим через тот, который получается из «о применением подстановки о, через тот, который получается из применением (т. е. применением я к и т. д. При продолжении этого процесса в конце, концов вернемся к элементу . Таким образом, элементы орбиты, содержащей естественно располагаются в порядке в котором подстановка о переставляет элементы по кругу. Таким же образом элементы располагаются на всех орбитах. Подстановка разбивается на циклы:

Если каждый цикл рассматривать как подстановку, циклически переставляющую элементы и оставляющую все остальные элементы на своих местах, то мы можем рассматривать равенство

как разложение подстановки в произведение циклов, попарно не содержащих общих элементов.

Легко видеть, что цикл допускает такое разложение в произведение транспозиций:

откуда следует, что цикл нечетной длины является четной подстановкой, цикл четной длины — нечетной. Поэтому четность или нечетность подстановки совпадает с четностью или нечетностью количества циклов четной длины.

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

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

Тогда

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

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

Отсюда следует

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

Необходимость непосредственно следует из предложения 2. Достаточность — из того, что в симметрической группе существуют подстановки, переводящие любое расположение элементов в любое другое.

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