§ 16. Группы подстановок. Перестановки. Транспозиции

Эти понятия играют важную роль в комбинаторике и мы напомним их.

Подстановкой называется биекция конечного множества на себя (рис. 12).

Подстановку часто изображают в виде соответствия между двумя строками:

первую строку называют «операндом», вторую — «результатом».

Рис. 12.

Порядок, в котором записывается операнд, вообще говоря, несуществен:

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

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

Произведение двух подстановок. Структура группы. Пусть — образ элемента при подстановке образ элемента у при подстановке Определим подстановку

(кликните для просмотра скана)

Например, если

то

На рис. 13 изображено это произведение. За единичную подстановку примем

Для каждой подстановки существуют симметричная ей слева и симметричная ей справа, совпадающие между собой (как на рис. 14).

Легко проверить свойство ассоциативности:

Таким образом, выполняются все групповые аксиомы. Множество подстановок элементов образует группу, называемую симметрической группой

Группа не коммутативна, так как для некоторых элементов

Прежде чем ввести понятие цикла, укажем еще одно изображение подстановки, пример которого приведен на рис. 15.

С другой стороны, подстановку можно записать с помощью перестановки, если первые строки всех подстановок взять одинаковыми. Например,

Цикл. Пусть задана биекция подмножества а на себя. Если мы проходим, следуя ей, все элементы начиная с некоторого и возвращаясь в него, то получаемую подстановку назовем циклом. Например, на рис. 16 представлен цикл, (1652734), на рис. 17 представлены циклы (1427) и (365), на рис. 18 — циклы (17), (2), (3), (456). Запишем эти подстановки с помощью циклов:

Обычно цикл записывают, начиная с наименьшего элемента (или с элемента с наименьшим индексов). Например, Часто удобно заменить символы в подстановке

на целые числа (или на элементы с целочисленными индексами)

Цикл, состоящий из элементов, называют -циклом. Например, (1652734) на рис. 16 есть -цикл; (1427) на рис. 17 есть 4-цикл; (2), (17), (456) на рис. 18 являются соответственно 1-циклом, 2-циклом, 3-циклом.

Рис. 17

Рис. 18.

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

Пример. На рис. 16 , на рис. 17 , на рис. 18 .

Будем иногда писать (0, 0, 1, 1) вместо (0, 0, 1, 1, 0, 0, 0), если это не приводит к недоразумению.

Теорема Для любого класса подстановок элементов

Это очевидно, ибо -цикл содержит элементов, а всего элементов в подстановке

Теорема II. Обозначим через число подстановок класса Тогда

где

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

Рис. 19.

Учитывая, что циклы можно переставлять между собой, получаем различных способов записи. Следовательно, любую подстановку из класса можно записать способами. Так как всего имеется возможных записей подстановок из этого класса, то получаем (16.10).

Пример. Рассмотрим класс (1,0, 1,0) при Тогда

Эти подстановки представлены на рис. 19.

Степени подстановки. Определим последовательно

Очевидно, что все эти подстановки коммутативны:

Например, если

то

Все степени некоторой подстановки можно изобразить в виде схемы, как это показано на рис. 20. Однако если подстановка обладает несколькими циклами, такая схема громоздка.

Рис. 20.

Аналогично вводятся отрицательные степени:

Порядок подстановки. Порядок подстановки есть наименьшее целое положительное число такое, что

Например, как это видно из рис. 20,

а из рис. 21 заключаем, что

Количество элементов в цикле называют порядком цикла. Например, -цикл имеет порядок

Теорема III. Порядок подстановки равен наименьшему общему кратному порядков циклов, определяющих класс эквивалентности, которому она принадлежит.

Пусть подстановка принадлежит классу Ее всегда можно представить в виде произведения подстановок (перестановочных между собой), первая из которых содержит -циклов, вторая содержит -циклов и -циклов, содержит 1-циклов и -циклов. На рис, 22 дан пример такого разложения.

Таким образом,

В силу коммутативности

Для того чтобы была единичной подстановкой, необходимо и достаточно, чтобы

Рис. 21.

Но наименьшее целое число для которого это свойство выполняется, есть наименьшее общее кратное тех чисел для которых

Рис. 22.

Рис. 23.

Транспозиция. Транспозиция есть подстановка из класса

Она переставляет между собой два элемента, не меняя расположения остальных. Пример транспозиции (рис. 23)

Теорема IV. Всякая подстановка разлагается в произведение транспозиций.

Способ доказательства теоремы проиллюстрируем на примере.

Пусть

и заданы транспозиции

Тогда

как видно из рис. 24.

Рис. 24.

Произведение различных транспозиций не коммутативно. Например,

но

Четность перестановки. Рассмотрим перестановку на множестве из элементов. С этим множеством свяжем неупорядоченное множество образованное парами различных элементов причем элементы в каждой паре записываются в том же порядке, что и в . Например, с перестановкой

получающейся из подстановки на рис. 25, связываем неупорядоченное множество

Рис. 26 показывает, как можно легко получить без пропусков и повторений.

С другой перестановкой

получающейся из подстановки на рис. 27, связывается множество, которое легко выписывается с помощью рис. 28.

Часть пар в совпадают, а другие отличаются порядком их элементов. Пусть число таких инверсий. Если четно, то скажем, что имеет ту же четность, что и . Сравнивая (16.34) и (16 32), видим, что имеется восемь инверсий (отмеченных на рис. 28 звездочкой), т. е. четности совпадают.

Рис. 25

Рис. 26

Рис. 27.

Рис. 28.

Отношение имеют одинаковую четность» есть отношение эквивалентности (рефлексивность, симметричность и транзитивность очевидны).

Так как всего имеется перестановок и каждый класс содержит одно и то же число элементов, то это число равно Исходная перестановка рассматривается как четная.

Четность подстановки. Подстановка сопоставляет любой перестановке перестановку . Например, если

то

или символически

По последовательности перестановок и подстановке можно выписать последовательность образов

Четности и либо все одинаковы, либо все противоположны Действительно, определим подстановку

Рассматривая как нижние строки соответствующих подстановок, имеем

Отсюда следует, что число инверсий при переходе от совпадает с числом инверсий при переходе от Таким образом, подстановки также распадаются на два класса (подстановка принадлежит четному классу). Имеется четных подстановок и столько же нечетных.

Группы и подгруппы подстановок. Рассмотрим все подстановки множества из элементов. Как было показано, они образуют группу, элементы которой можно разбить на два класса: четных и нечетных подстановок. Четные подстановки образуют подгруппу:

1) единичная подстановка четна по определению;

2) обратная к четной подстановке также четная;

3) произведение четных подстановок четно.

Сформулируем еще несколько теорем.

Теорема Всякая транспозиция есть нечетная подстановка.

Теорема очевидна в силу определения транспозиции.

Так как произведение транспозиций дает четную подстановку, а произведение транспозиций — нечетную, то справедливо следующее утверждение:

Теорема VI. Если подстановка разложена в произведению транспозиций, то число их четно или нечетно в зависимости от того, четна или нечетна Верно и обратное утверждение.

Теорема VII. Если число четных циклов четно, то подстановка четна, если это число нечетно, то подстановка нечетна.

Приведем несколько примеров.

Подстановки класса (1, 2, 0, 1, 0, 0, 0, 0, 0) нечетны, так как содержат четных циклов Подстановки класса (0, 1, 1, 1, 0, 0, 0, 0, 0) четны, так как содержат четных циклов. Подстановки класса (3,0, 1,0, 0,0) четны, так как не содержат четных циклов.

Теорема VIII (теорема Кэли). Всякая конечная группа изоморфна некоторой группе подстановок ее элементов.

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

УПРАЖНЕНИЯ

(см. скан)