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

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

Так определенное множество A(x) называется стабилизатором элемента x. Нетрудно видеть, что стабилизатор является подгруппой группы A. Заметим, что всякий раз, когда элементы x и y принадлежат одной и той же орбите, множества A(x) и A(y) являются сопряженными подгруппами группы A (то есть существует такая подстановка a из A, чтои, следовательно, |A(x)| = |A(y)|.

Теорема

Для любого элемента y из орбиты Y группы A выполнятся следующее соотношение

|A| = |A(y)| · |Y|

Доказательство. Разложим группу A в объединение правых классов смежности по подгруппе A(y):

Теперь остается только указать естественноe взаимно однозначное соответствие между этими классами смежности и элементами орбиты Y. Для каждогосопоставляем классу смежности элементиз Y. Если i не равно j, тоy не равно y, так как иначе бы подстановка принадлежала подгруппе A(y) и, следовательно, подстановкаявлялась бы элементом множества A(y), что противоречит соотношению A(y) ∩A(y) = Ø. Значит, указанное соответствие является взаимно однозначным. Для всякого объекта y′ из Y при некоторой подстановке a из A выполняется равенство ay = y′. Из разложения группы A на классы смежности следует, что , если b принадлежит A(y). Следовательно,и, таким образом, каждый элемент орбиты Y соответствует некоторому классу смежности. Значит, m есть число элементов в орбите Y и формула (1.7) доказана.

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

Лемма Бернсайда

Число N(A) орбит группы A дается формулой

Доказательство. Пусть - орбиты группы A, и для каждогопусть- элемент i-й орбиты . Тогда из формулы (1.7) имеем

Мы видели, что если x и принадлежат одной и той же орбите, то. Следовательно, соотношение (1.9) можно записать так:

или, в других обозначениях,

Теперь, меняя порядок суммирования в правой части формулы (1.9) и изменяя соответствующим образом индексы суммирования, имеем Но есть в точности . Таким образом, для завершения доказательства надо обе части разделить на |A|.

Также нам нужно будет ограничивать действие группы A на некоторое подмножество Y множества X, где Y объединение каких-либо орбит группы A. Поэтому обозначим через A|Y множество подстановок, действующих на Y и получающихся с помощью ограничения на подмножество Y соответствующих подстановок группыA. Для каждой подстановки a из группы A число элементов в Y, неподвижных относительно подстановки a, обозначим через . Теперь можно сформулировать следствие леммы Бернсайда.

Ограниченная форма леммы Бернсайда

1.3 Теорема ПойаПусть A - группа подстановок с множеством объектов и пусть B - конечная группа подстановок со счетным множеством объектов Y, содержащим не менее двух элементов. Тогда степенная группа, обозначаемая , имеет в качестве множества объектов совокупностьвсех функций, действующих из X в Y. Подстановками группыявляются все упорядоченные пары подстановок a из A и b из B, записываемые в виде (a, b). Образ произвольной функции f изпри действии на нее подстановки (a, b) дается формулой

при всех x из X.

Для того, чтобы привести классическую формулу перечисления Пойа, мы возьмем B = E -

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