АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. II. Доказательство некоторых понятий и фактов геометрии Лобачевского
  2. Анализ эмпирических показателей и формулировка выводов
  3. Вводная часть исследовательской работы. Формулировка основных научных атрибутов.
  4. Вопрос 32 Процедуры познавательной деятельности: обоснование, доказательство, объяснение, понимание
  5. Глава 18. Доказательство.
  6. Глава V. Доказательство, что един есть Бог, а не многие
  7. Глава VI. О Слове и Сыне Божием, доказательство из разума
  8. Глава VII. О Духе Святом; доказательство из разума
  9. Глава восьмая. Доказательство четвертое - предания о пантеистах.
  10. Глава пятая. Доказательство второе - хадисы о хариджитах.
  11. Глава седьмая. Доказательство третье: Хадис о къадаритах
  12. Доказательство

Лемма Бернсайда вычисляет количество орбит действия группы на множестве с помощью суммы по всем элементам группы. Она применяется в том случае, когда порядок множества 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). Иными словами, построим график ука­занного отношения. Число от­меченных точек (точек, принадлежащих графику) можно подсчитать двумя способами:

Рис. 4
оп­ределить число отмеченных точек на каждой вертикали и просуммировать полученные величины или же опреде­лить число таких точек по каждой горизонтали и затем вычистить их сумму.

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

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

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

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

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

Поэтому

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

т.е.

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

 


1 | 2 | 3 | 4 | 5 | 6 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)