Формулировка и доказательство

Лемма Бернсайда вычисляет количество орбит действия группы на множестве с помощью суммы по всем элементам группы. Она применяется в том случае, когда порядок множества X намного больше, чем порядок группы G.

Пусть G - перестановок на множестве Подмножество называется орбитой группы G, если

а) для любого и любого ; т.е. действие перестановок из G на элементы O не выводит за пределы О;

б) два элемента из О можно перевести друг в друга некоторой перестановкой из G.

Всякая группа перестановок G = { имеет орбиты.

Для доказательства выберем произвольный элемент и рассмотрим множество Оно будет орбитой группы G, так как

а) если так как

б) если и произвольные элементы из то и при этом так как G группа.

Оказывается, что орбитами подобного вида исчерпы­ваются все типы орбит. Более точно, если О орбита группы G и , то = (а). Справедливость этого утверждения вытекает непосредственно из определения орбиты группы.

Ясно, что любые две орбиты О(а) и О (b) либо совпа­дают (если b О(а)), либо не пересекаются (если b O (а)). Отсюда следует, что множество М распадается в объ­единение непересекающихся подмножеств — орбит группы G. В частности, может случиться, что единственной орбитой группы G будет само множество М. Группы с таким свойством называются транзитивными. Таким образом, группа пере­становок G на множестве М транзитивна, если любой элемент а М может быть получен из любого другого элемента b М под действием подходящим способом вы­бранной перестановки : . Все другие группы перестановок называются интранзитивными.

Пусть число неподвижных точек перестановки , число орбит группы перестановок действующей на множестве

Лемма Бернсайда: Для любой группы перестано­вок имеет место равенство

Доказательство: Рассмотрим отношение «переста­новка сохраняет неподвижным элемент m» между пере­становками группы G и элементами множества М. Сопо­ставим парам (, т), , m , вершины прямоуголь­ной сети и отметим те из них, для которых соответствующая пара (, т) находится в ука­занном отношении, т. е. m(a) = т (рис. 4). Иными словами, построим график ука­занного отношения. Число от­меченных точек (точек, принадлежащих графику) можно подсчитать двумя способами:

Согласно определению отношения на каждой вертикали отмечаются все точки, сохраняемые перестановкой , соот­ветствующей этой вертикали. Их число равно Поэтому число всех точек графика равно

С другой стороны, на каждой горизонтали отмечаются все перестановки, сохраняющие элемент m , отвечаю­щий этой горизонтали. Мы знаем, что они образуют группу G_m — стабилизатор элемента т — и их чисто равно

Поэтому при втором способе подсчета числа отмеченных точек графика рассматриваемого отношения получаем выражение

Однако если элементы i, j М содержатся в одной орбите, то и поэтому Пусть — все орбиты группы G, такие, что , и слагаемые в этом объединении не пересекаются. Разобьем сумму (1) на части так, чтобы внутри каждой из частей суммирование шло по элемен­там некоторой орбиты:

Каждое из t слагаемых в правой части этого равенства можно преобразовать следующим образом:

Поэтому

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

т.е.

Лемма доказана.

Поиск по сайту: