PA_full (1127144), страница 19
Текст из файла (страница 19)
Найти Stab (t).Решение: Stab (t) ⇠= 3 � группа вращений на 120 вокругдиагонали куба, проходящей через данную вершину.Прикладная алгебраТеория перечисления ПойаДействие группы на множестве260 / 432СтабилизаторЛеммаДлина орбиты Orb (t) равна индексу Stab (t) в группе, т.е.| Orb (t)| = |G| : | Stab (t)|.ПримерO � группа вращений куба (группа октаэдра) и t � некотораяего вершина.
Найти Stab (t).Решение: Stab (t) ⇠= 3 � группа вращений на 120 вокругдиагонали куба, проходящей через данную вершину.УтверждениеЧисло элементов в группе вращения правильногомногогранника есть |V | · |E0 |, где |V | � число вершин, а|E0 | � число рёбер, выходящих из одной вершины.Прикладная алгебраТеория перечисления ПойаДействие группы на множествеЭто тетраэдр261 / 432А это � кубикОктаэдр двойственен кубуПрикладная алгебраТеория перечисления ПойаДействие группы на множестве262 / 432Платоновы тела � правильные 3-х мерные многогранникиПлатоновы телатетраэдркуб и октаэдрикосаэдр и додекаэдрОктаэдрГруппа симметрииTOYИкосаэдрПорядок группы4 · 3 = 128 · 3 = 2412 · 5 = 60ДодекаэдрПрикладная алгебраТеория перечисления ПойаДействие группы на множестве263 / 432ПримерДействие группы V4 на множестве T =eab abg ⇤ t t1eeab abet1aae ab bat2bb ab eabt3ab ab baeabt4{ t1 ,t2t2t1t4t3...,t3t3t4t1t2t6 }t4t4t3t2t1t5t5t6t5t6t6t6t5t6t5Прикладная алгебраТеория перечисления ПойаДействие группы на множестве264 / 432T ype(e) = h 6, 0, 0, 0, 0, 0 i ,T ype(b) = h 2, 2, 0, 0, 0, 0 i ,T ype(a) = h 0, 3, 0, 0, 0, 0 i ,T ype(ab) = h 0, 3, 0, 0, 0, 0 i .C(e) = 6 , C(a) = C(ab) = 3 , C(b) = 4 .Stab (t1 ) = Stab (t2 ) = Stab (t3 ) = Stab (t4 ) = e 6 V4 ,Stab (t5 ) = Stab (t6 ) = h e, b i 6 V4 .Fix (a) = Fix (ab) = ? , Fix (b) = { t5 , t6 } , Fix (e) = T .44| Orb (t1 )| == 4 , | Orb (t5 )| == 2.121X6+2| Fix (g)| == 2,44g2G1X4t2T| Stab (t)| =4·1+2·2= 2.4Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды265 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств266 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать267 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПростая задачаЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . . . , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.268 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПростая задачаЗадача (про слова)Составляются слова длины l > 2 из алфавитаA = { a1 , . .
. , am }. Слова считаются эквивалентными, еслиони получаются одно из другого перестановкой крайних букв.Определить число S неэквивалентных слов.РешениеT � множество слов длины l в алфавите A, N = |T | = ml .Надо представить эквивалентности как орбиты некоторогодействия подходящей группы G на T .Очевидно, g 2 = e и поэтому подходит G ⇠= 2 = { e, g }.Действие: g переставляет в слове крайние буквы.268 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПродолжение 1Число S неэквивалентных слов есть число классовэквивалентности C(G) действия 2 : T �↵|Fix (e)| = |T | = ml ,|Fix (g)| = ml 2 · m = ml 1 .1Xml + ml 1ml 1 (m + 1)S = C( 2 ) =|Fix (g)| ==.222g2GДля l = 3, m = 2 ) S =4·32= 6 (из всего 8)269 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачПродолжение 1Число S неэквивалентных слов есть число классовэквивалентности C(G) действия 2 : T �↵|Fix (e)| = |T | = ml ,|Fix (g)| = ml 2 · m = ml 1 .1Xml + ml 1ml 1 (m + 1)S = C( 2 ) =|Fix (g)| ==.222g2GДля l = 3, m = 2 ) S = 4·32 = 6 (из всего 8)Пусть A = {a, b}.
Показаны слова и классы.aaaaababaabbbaababbbabbb269 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач270 / 432Стабилизаторы сопряжённых элементов группы совпадаютЗадачаПоказать, что если элементы g и h группы G сопряжены, тоStab (g) = Stab (h).Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач270 / 432Стабилизаторы сопряжённых элементов группы совпадаютЗадачаПоказать, что если элементы g и h группы G сопряжены, тоStab (g) = Stab (h).Решениеgf = f h ) Stab (gf ) = Stab (g) \ Stab (f ) = Stab (f h) == Stab (f ) \ Stab (h) ) Stab (g) = Stab (h).Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачДействие группы O на вершины кубаЗадачаГруппа вращений куба действует на множество его вершин.Определить типы всех перестановок этой группы.271 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачДействие группы O на вершины кубаЗадачаГруппа вращений куба действует на множество его вершин.Определить типы всех перестановок этой группы.РешениеO = h t, f, r i , t4 = f 2 = r3 = e, гдеt � вращение на 90 вокруг оси,проходящей через середины двухпротивоположных граней (2�2);f � вращение на 180 вокруг оси,проходящей через середины двухпротивоположных рёбер ( � );r � вращение на 120 вокруг оси,проходящей через две противоположныевершины (M�M).271 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач272 / 432Действие группы O на вершины куба: продолжение решения2 : T ype(t) == T ype(t3 ) = h0, 0, 0, 2, 0, .
. .i,T ype(t2 ) = h0, 4, 0, . . .i;: T ype(f ) = h0, 4, 0, . . .i;M: T ype(r) = T ype(r2 ) = h2, 0, 2, 0, . . .i.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач273 / 432Цикловой индексСуществует универсальный способ вычисления числа1 PFix (g) = C( ) классов эквивалентности (орбит).|G|g2GСопоставим каждой перестановке g 2вес w(g) по правилу:T ype(g) = h⌫1 , . . . , ⌫N i ) w(g) = x⌫11 · . .
. · x⌫NN .|{z}мономПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач273 / 432Цикловой индексСуществует универсальный способ вычисления числа1 PFix (g) = C( ) классов эквивалентности (орбит).|G|g2GСопоставим каждой перестановке g 2вес w(g) по правилу:T ype(g) = h⌫1 , . . . , ⌫N i ) w(g) = x⌫11 · . . . · x⌫NN .|{z}мономОпределениеСредний вес подстановок в группе называетсяцикловым индексом действия : T :↵1 X1 X ⌫1P ( : T, x1 , . . .
, xN ) =w(g) =x1 · . . . · xN⌫N .↵|G||G|g2Gg2GПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач273 / 432Цикловой индексСуществует универсальный способ вычисления числа1 PFix (g) = C( ) классов эквивалентности (орбит).|G|g2GСопоставим каждой перестановке g 2вес w(g) по правилу:T ype(g) = h⌫1 , . . . , ⌫N i ) w(g) = x⌫11 · . . .
· x⌫NN .|{z}мономОпределениеСредний вес подстановок в группе называетсяцикловым индексом действия : T :↵1 X1 X ⌫1P ( : T, x1 , . . . , xN ) =w(g) =x1 · . . . · xN⌫N .↵|G||G|g2Gg2GДля продвинутых: это производящий полином.Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЦикловой индекс: обозначения и свойстаДругие обозначения: P (x1 , . .
. , xN ) и P , P ( ).⇠= 0 ) P = P 0 � да, если действия определеныодинаково (согласовано)P= P06)⇠=0� нет, есть контрпример274 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЦикловой индекс: обозначения и свойстаДругие обозначения: P (x1 , . . . , xN ) и P , P ( ).⇠= 0 ) P = P 0 � да, если действия определеныодинаково (согласовано)P= P06)⇠=0� нет, есть контрпримерКак применять лемму �не-Бёрнсайда?�Для применения универсального способа вычисления C( )надо представить эквивалентные элементы множества какклассы эквивалентности действия некоторой группы на этоммножестве.274 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЧисло неэквивалентных раскрасокПусть задано действие: T группы↵на множестве T .275 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачЧисло неэквивалентных раскрасокПусть задано действие: T группы↵на множестве T .Припишем каждому элементу T одно из r значений(неформально: покрасим в один из r цветов).
Всегоимеется rN раскрасок.275 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач275 / 432Число неэквивалентных раскрасокПусть задано действие: T группы↵на множестве T .Припишем каждому элементу T одно из r значений(неформально: покрасим в один из r цветов). Всегоимеется rN раскрасок.Не будем различать раскраски, если при преобразованииg : t ! t0 элемент сохраняет цвет (t раскрашен также какt0 , и каждый g-цикл раскрашен одним своим цветом).••••••••Рис.
3. Поворот на 90 (такая перестановка) не даёт новогораскрашивания вершин квадратаПрикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач275 / 432Число неэквивалентных раскрасокПусть задано действие: T группы↵на множестве T .Припишем каждому элементу T одно из r значений(неформально: покрасим в один из r цветов). Всегоимеется rN раскрасок.Не будем различать раскраски, если при преобразованииg : t ! t0 элемент сохраняет цвет (t раскрашен также какt0 , и каждый g-цикл раскрашен одним своим цветом).••••••••Рис. 3. Поворот на 90 (такая перестановка) не даёт новогораскрашивания вершин квадратаВопрос: Сколько существует неэквивалентных раскрасок �классов эквивалентности C( )?Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задачВычисление C( ) через цикловой индексКаждый класс эквивалентности это g-цикл; ихC(g) = ⌫1 + .
. . + ⌫N штук.Каждая перестановка g 2 с типом h ⌫1 , . . . , ⌫N i будетиметь rC(g) неподвижных точек.276 / 432Прикладная алгебраТеория перечисления ПойаПрименение леммы Бёрнсайда для решения комбинаторных задач276 / 432Вычисление C( ) через цикловой индексКаждый класс эквивалентности это g-цикл; ихC(g) = ⌫1 + .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
