7.7. Действие групп на множестве

• Определение. Говорят, что задано действие группы на множестве если определен гомоморфизм группы в симметрическую группу подстановок: Свойство сохранения операций для гомоморфизма: где

Далее полагаем,

• Замечание. Чаще всего бывает так, что действие на возникает естественным образом, как группа симметрий структуры, определенной на

Пример. Пусть вершины графа на рис. 7.1. Найти группу самосовмещений данного графа.

Рис. 7.1

Решение. Исходное множество элементов является связанным или структурой. Группа действующая на группа самосовмещений: где

вокруг горизонтальной оси;

вокруг вертикальной оси;

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

Таблица 7.1 (см. скан)

• Определение. Элементы называются -эквивалентными и записывают если который, действуя на множестве переводит т.е. или более короткая запись этого

Утверждение 7.7.1. Определенная -эквивалентность на множестве является отношением эквивалентности. Доказательство. Проверим свойства отношения эквивалентности.

Действительно, где единичный элемент.

Имеем тогда а значит,

Имеем, что откуда Следовательно,

Утверждение 7.7.2. Группа действуя на множестве порождает его разбиение на непересекающиеся подмножества — классы эквивалентности (рис. 7.2):

Ng - количество классов эквивалентности. Пусть тогда класс эквивалентности составят все различные элементы множества

Рис. 7.2

• Определение. Множество называется стабилизатором Элементы стабилизатора оставляют на месте.

Пример. Продолжим рассмотрение примера на рис. вершины графа на рис. 7.3. На действует группа самосовмещений где

Рис. 7.3

Найдем все классы эквивалентности.

Определим стабилизаторы для вершин графа

• Утверждение подгруппа группы Доказательство. Проверим свойства группы.

1. Замкнутость. тогда и следовательно,

2. Единичный элемент так как

3. Обратный элемент. Пусть тогда откуда следовательно,

• Утверждение в этом случае говорят, что подгруппы сопряжены.

Доказательство. Имеем следовательно, или Отсюда т.е. Получили, что Заметим, что значит, Подобным образом доказывается в обратную сторону: следовательно, Показали, что отсюда

Утверждение где

Доказательство. Пусть Из утверждения 7.7.2 следует, что однако среди выписанных элементов множества могут встречаться одинаковые. Назовем эквивалентными если они действуют на элемент одинаковым образом, т. е. Данное отношение является отношением эквивалентности. Введенная эквивалентность разбивает группу на классы, количество которых равно числу различных элементов среди выписанных т. е. равно

Пусть или следовательно, или Верно и обратное, если то Отсюда Таким образом, тогда и только тогда, когда лежат в одном правом классе смежности по стабилизатору а значит, и число элементов в равно количеству правых смежных классов в С по подгруппе Согласно теореме 7.3.1 Лагранжа,

• Лемма 7.7.1 Бернсайда. Число классов эквивалентности, на которые распадается множество под действием группы равно

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

Первая сумма Так как то где Таким образом,

Получили, что откуда

Пример. Продолжим рассмотрение примера на рис. вершины графа. На действует группа самосовмещений где

Полным перебором установили, что под действием множество распадается на три класса эквивалентности: где Установим данный факт, применяя лемму 7.7.1 Бернсайда: число классов эквивалентности.

Отсюда следует, что число классов эквивалентности

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