7.10. Цикловая структура групп подстановок

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

7.10.1. Цикловой индекс группы, действующей на себе

Пусть группа действует на множестве следующим образом: Если порядок элемента то все элементы различны. Группа распадается под действием на циклы одинаковой длины. Количество циклов равно где порядок группы. Цикловой индекс группы примет вид

где количество элементов с порядком Суммирование выполняется по всем делителям числа

7.10.2. Цикловой индекс циклической группы

Пусть множество вершин правильного -угольника (рис. 7.6) на плоскости. Группа циклическая группа самосовмещений. Образующий элемент группы вращение (отображение) вокруг центра на угол Следовательно, где тождественная подстановка. Если обозначить вершины многоугольника элементами группы то вращение будет эквивалентно умножению вершины на соответствующий элемент группы. Например, совмещение при вращении на угол равносильно умножению новых меток вершин -угольника на элемент а, действительно, а Таким образом, можно считать, что циклическая группа действует на себе. Согласно (7.10.1) цикловой индекс данной группы примет вид

где функция Эйлера. Действительно, если порядок элемента равен (элемент суммируется в ), то он является образующим элементом подгруппы порядка Показать, что если порядки элементов циклической группы совпадают

Рис. 7.6

то они являются образующими одной и той же подгруппы Число образующих в такой подгруппе

Найдем количество возможных раскрасок двумя цветами вершин данного (рис. 7.6) -угольника. Пусть цвета — Воспользуемся теоремой 7.9.1 Пойа. Для определения количества раскрасок положим веса цветов равными Тогда

Для треугольника число раскрасок равно

Для шестиугольника число раскрасок равно

7.10.3. Цикловой индекс симметрической группы

Пусть произвольное множество, на котором действует группа всех подстановок симметрическая группа, Рассмотрим произвольную подстановку с характеристикой где Подсчитаем количество подстановок с данной характеристикой. Для этого запишем в цикловом представлении, помещая знаки на местах, которые должны занять элементов. Так, для характеристики (3,2) следует записать Далее пробелы можно заполнять элементами множества в любом порядке. Это дает подстановок с характеристикой которые, однако, не все различные. Каждый из циклов Сможет начинаться с любого своего элемента, не изменяя исходной подстановки и уменьшая общее число различных подстановок в раз. Если имеется таких циклов, то их можно переставлять k), способами, что также не будет приводить к новым подстановкам. Все эти варианты суть

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

Рассмотрим пример определения числа раскрасок двумя цветами трех усов антенны (рис. 7.7). Усы свободно вращаются в пространстве. В этом случае на множестве действует симметрическая группа подстановок Найдем все характеристики разложения числа Ими будут: (3,0,0), (1,1,0) и (0,0,1). Цикловой индекс примет вид

Рис. 7.7

Для определения количества раскрасок положим веса цветов равными тогда Следовательно,