Читать курсовая по математике: "Практическое применение теоремы Пойа и перечисления графов" Страница 4

(Назад) (Cкачать работу)

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

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

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

Рассмотрим для примера симметрическую группу . Заметим, что тождественная подстановка (1)(2)(3) имеет три единичных цикла дающих слагаемое . Три подстановки (1)(23), (2)(13) и (3)(12) имеют каждая по единичному циклу и по одному циклу длины 2, так что получается одно слагаемое . Наконец, подстановки (123) и (132) вносят . Таким образом, имеем

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

Назовем разбиением натурального числа n его представление в виде суммы некоторых натуральных чисел. Заметим, что каждая подстановка a на n объектах может быть связана с определенным разбиением числа n, имеющим для каждоготочночастей, равных числу k. Будем задавать разбиение числа n посредством вектора , где- число частей разбиения, равных k. Итак,

Пример

4 = 1 + 1 + 1 + 1 (4, 0, 0, 0)

= 1 + 1 + 2 (2, 1, 0, 0)

= 2 + 2 (0, 2, 0, 0)

= 1 + 3 (1, 0, 1, 0)

= 4 (0, 0, 0, 1)

Пусть h(j) - число подстановок в группе , разложение которых на непересекающиеся циклы соответствует разбиению (j), в том смысле, что для каждого k выполняется . Тогда имеет место следующая лемма.

Лемма

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

Теорема

Цикловой индекс симметрической группы дается формулой

где сумма берется по всем разбиениям (j) числа n, а h(j) задается выражением(1.2).

Пример

3 = 1 + 1 + 1 (3, 0, 0) h = 3! / 3! = 1

= 1 + 2 (1, 1, 0) h = 3! / 1·1!·2·1! = 3

= 3 (0, 0, 1) h = 3! / 3·1!

Иногда удобно расматривать производящую функцию цикловых индексов и пользоваться следующим свойством.

Теорема

гдепо определению.

Часто бывает удобным выразитьчерез , где . Рекуррентная формула, следующая из (1.4), может быть представлена следующим образом.

Теорема Цикловой индекс симметрической группы удовлетворяет рекуррентному соотношению

Пример

1.2 Эквивалентность, порождаемая группой подстановок Отношение эквивалентности

Отношение эквивалентностина множестве- это бинарное отношение, для которого выполнены следующие условия:

· Рефлексивность:для любогов ,

· Симметричность: если , то ,

· Транзитивность: еслии , то .

Запись вида « » читается как « a эквивалентно b».

Пусть A - группа подстановок с множеством объектов . Элементы x и y из X называются A-эквивалентными, если существует подстановка a из A, такая, что . Нетрудно показать, что введенное нами отношение есть отношение эквивалентности. Множество X разбивается на классы эквивалентности. Эти классы называются орбитами.

Для

Похожие работы